Identifying overlapping communities in social networks using multi-scale local information expansion

Abstract

Most existing approaches for community detection require complete information of the graph in a specific scale, which is impractical for many social networks. We propose a novel algorithm that does not embrace the universal approach but instead of trying to focus on local social ties and modeling multi-scales of social interactions occurring in those networks. Our method for the first time optimizes the topological entropy of a network and uncovers communities through a novel dynamic system converging to a local minimum by simply updating the membership vector with very low computational complexity. It naturally supports overlapping communities through associating each node with a membership vector which describes node's involvement in each community. This way, in addition to uncover overlapping communities, we can also describe different multi-scale partitions by tuning the characteristic size of modules from the optimal partition. Because of the high efficiency and accuracy of the algorithm, it is feasible to be used for the accurate detection of community structure in real networks.

15 pages, 8 figures. arXiv admin note: text overlap with arXiv:1004.4268, arXiv:cond-mat/0308217 by other authors; text overlap with arXiv:1104.5247 by other authors without attribution

References in corpus (22)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• The diameter of the world wide web
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical Organization in Complex Networks
• Quantifying social group evolution
• The Web of Human Sexual Contacts
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Assessing the relevance of node features for network structure
• Line Graphs of Weighted Networks for Overlapping Communities
• Finding instabilities in the community structure of complex networks
• Complex earthquake networks: Hierarchical organization and assortative mixing