Overlapping Community Detection Based On Core Region Expansion

Community structure is one of the most common properties of complex networks, consisting of a group of vertices that connect each other densely and have fewer connections with other vertices outside the community. Researchers can deeply understand the complex system through studying the community structure of its corresponding network, because community structure reveals the organizations. At the same time, community structure has extensive applications in real world. So the research on community detection in complex networks is of significance.A method to measure the centrality of a vertex is proposed. Further, based on core score and local expansion framework, a new overlapping community detection algorithm is proposed and some hub vertices can be detected at the same time. The algorithm consists of four steps. Firstly, vertices are ranked in descending order according to their core scores to form a seeds priority list. Secondly, the topmost vertex on the list is used to detect the core region of a community. Thirdly, the core region is expanded until a community or a hub vertex is detected. The second and the third steps are iteratively run until all communities are found. Finally, the hubs are assigned into communities where their most neighbors appear. Experiments in extensive datas show the effectiveness of the algorithm.Given the fact that most existing community detection algorithms can not effectively deal with mass data, a new parallel algorithm based on local expansion is proposed and is further implement by utilizing Spark. The algorithm consists of four steps. Firstly, a group of irrelevant central vertices are selected and their corresponding egonets are used as seeds. Secondly, the algorithm filters the selected seeds by removing those whose vertices are weakly connected. Thirdly, the algorithm adopts a batched expansion strategy to expand seeds, by adding a group of neighboring vertices to the local community or removing a group of vertices from the local community. Finally, similar communities are merged. Experiments in extensive datas show the effectiveness of the algorithm.