Approximation of source-oriented centrality in large networks and community detection

Social networks are nowadays a key factor shaping the way people interacting with each other. Therefore it is of great interest for researchers in industry and academia to study social networks. Among various methods, centrality measure and community detection are the two core approaches to uncover and understand the structure of networks. In this thesis, we propose a new centrality measure which emphasizes on locality. We develop a straightforward method for computing the centrality values of the nodes in a network. In order to apply to large datasets, we then present an efficient algorithm with guaranteed error bound for approximating the centrality values. Later in the thesis, we adopt the results on our new centrality measure to explore communities in a network. We evaluate our algorithms on several datasets. The results show that our approaches work surprisingly well on real world networks.