A novel disjoint community detection algorithm for social networks based on backbone degree and expansion

摘要

Community detection in social networks is a key point to discover the functions and structure of social networks. A great deal of work has been done for overlapping community detection and disjoint community detection, and numerous techniques such as spectral clustering, modularity maximization, random walks, differential equation, and statistical mechanics are used to identify a community in networks, but most of these work adopts pure mathematic and physical methods to discover communities from social networks, on the contrary ignoring the social and biological properties of communities and social networks. In this paper, firstly we propose the community forest model based on these social and biological properties to characterize the structure of real-world large-scale networks, secondly we mainly define a new metric named backbone degree to measure the strength of the edge and the similarity of vertices and give a new sense definition to community based on expansion, thirdly we develop a novel algorithm that based on backbone degree and expansion to discover disjoint communities from real social networks. This algorithm has better performance and effects compared with CNM and GN algorithms in computational cost and visibility. It has worked well on Email-Enron, American College Football, karate club etc. data sets.