Research Of Overlapping Community Detection Based On Graph Compression

In recent years, finding community structure in complex networks has been a hot area of research and therefore community detection has become a hot issue in the field of complex networks. Social communities in reality are not mostly independent of one another, but overlapping each other. Since overlapping community can reflect the network structure more realistic, overlapping community detection has become the research focus of complex networks.In this thesis, we first introduce the basic theories and knowledge of community detection such as the concept of community structure, and then we summarize the research achievement about community structure in social networks in recent years. We also introduce some existing mainly important overlapping community detection algorithms and analyze their advantages and disadvantages. Considering the problem of low efficiency of the existing algorithms for large scale networks, the thesis proposes a new overlapping community detection algorithm based on graph compression, which can improve the network scale processed on a single machine by orders of magnitude without impacting the accuracy, to find overlapping communities. First we propose a representation model to find community structure based on graph compression —— agglomerative graph, which is a lossless compression to the original network. Then we apply the "seed iteration idea" to the agglomerative graph, expanding the seed by optimizing the community fitness function constantly. When the community fitness function of the seed reaches the maximum, the seed turns into a community. We get the final result of overlapping communities by merging communities with high similarities. Because of the significant reduction of the network complexity and computation by the agglomerative graph, the method proposed in this thesis can greatly improve the efficiency.Extensive experiments are conducted to analyze and verify the proposed algorithm from the respect of accuracy, efficiency and overlapping quality. The results show that our algorithm not only can achieve the high accuracy, but also can greatly improve the network scale processed on a single machine, making the issue of finding overlapping communities efficiently on large scale networks possible.