Community Detection For Large Scale Social Networks Based On Structure And Theme

Community detection is an important method of complex network. Recently, more and more researchers apply it to social network analysis, web service, network visualization and other specific issues. Up to now, a lot of community detection algorithms are time-consuming and difficult to deal with large-scale networks. In this thesis, we use Graphlab to implement community detection algorithms for large-scale of networks.This thesis mainly focuses on the following three parts.(1) This thesis proposes an improved Label Propagation Algorithm(LPA) based on the initial community and credibility. Traditional LPA on Graphlab has the problems of misconvergence and unstable division. In order to solve these problems, this thesis improves the LPA in terms of the following two aspects: first, choose part of nodes as the center and initialize the center node’ neighbor to same community, so as to greatly reduce the number of initial community of LPA; second, define a credibility for each edge on the network. The higher the credibility is, the more credible the label of neighbor node is, so as to change the random selection strategy of LPA according to the credibility. This thesis tests the improved LPA on artificial networks and real networks. The results show that the improved LPA algorithm is more stable and accurate.(2) On the basis of BIGCLAM algorithm, this thesis proposes a generative model of community on the combination of network topology and user’s theme information. Web 2.0 technology has given rise to many networks of which users generated content, such as Facebook, Twitter, GooglePlus. The users leave a large number of theme information on the network. And this thesis introduces these information to community detection. The generative model assumes that the community generates the network edge and node theme. And then, a likelihood function is built on the network. Maximize the likelihood function by using adjacency matrix and node theme. As a result, a community belonging to the node is generated. Testing generative model on the thematic social network, the experimental results show that the introduction of theme information improves the division performance.(3) Employing a Graphlab cluster which is composed of 4 sets of ordinary PC to implement the proposed algorithms in this thesis. And this thesis comparatively analyzes the performance of the proposed algorithms on the Graphlab cluster. The experimental results show that the proposed algorithms gets high speed-up ratio on Graphlab.In this thesis, the input parameter of the generative model is the number of community on the network, and the number of community is often unknown. Although the number can be obtained through continuous iteration, the computational cost is very large. So transforming the generative model to a non-parametric algorithm is the next work needs to be done.