Overlapping Community Detection Algorithm Based on Subgraph Structure

Abstract

Local community detection algorithms usually select seed nodes for community detection.To improve the quality of effectiveness of seed node selection,we propose an overlapping community detection algorithm based on subgraph structure(SUSBOCD).This algorithm proposes a new measure of node importance,which not only considers the number of neighbors,but also considers the degree of density between neighbors.First,SUSBOCD selects the most important node that is not visited and the most similar neighbor node,and merges the two nodes and their common neighbor nodes to form an initial seed subgraph.The process runs iteratively until all nodes have been visited.Second,the similarity is judged according to the neighborhood information of the seed subgraph.If it is similar,it is merged to form the initial community structure.The process runs iteratively until all seed subgraphs are visited.Finally,we optimize the community.If there are nodes without assigned communities,they are added to the most similar community,and then the community structure with high overlap is merged.Experiments on real and artificial networks show that SUSBOCD can improve the quality of overlapping community partition effectively in the three evaluation indexes of ONMI,EQ and Omega.

Keywords

• overlapping community detection|local expansion|seed selection|community expansion|community optimization