Ubiquitousness of link-density and link-pattern communities in real-world networks
arXiv:1104.3162 · doi:10.1140/epjb/e2011-20448-7
Abstract
Community structure appears to be an intrinsic property of many complex real-world networks. However, recent work shows that real-world networks reveal even more sophisticated modules than classical cohesive (link-density) communities. In particular, networks can also be naturally partitioned according to similar patterns of connectedness among the nodes, revealing link-pattern communities. We here propose a propagation based algorithm that can extract both link-density and link-pattern communities, without any prior knowledge of the true structure. The algorithm was first validated on different classes of synthetic benchmark networks with community structure, and also on random networks. We have further applied the algorithm to different social, information, technological and biological networks, where it indeed reveals meaningful (composites of) link-density and link-pattern communities. The results thus seem to imply that, similarly as link-density counterparts, link-pattern communities appear ubiquitous in nature and design.
References in corpus (37)
- Community structure in social and biological networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Assortative mixing in networks
- Cooperative Game Theory Approaches for Network Partitioning
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Mixing patterns in networks
- Resolution limit in community detection
- Comparing community structure identification
- Defining and identifying communities in networks
- Hierarchical structure and the prediction of missing links in networks
- Hierarchical Organization in Complex Networks
- Stochastic blockmodels and community structure in networks
- Why social networks are different from other types of networks
- Community Structure in Jazz
- Synchronization reveals topological scales in complex networks
- An information-theoretic framework for resolving community structure in complex networks
- Finding overlapping communities in networks by label propagation
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Mixture models and exploratory analysis in networks
- Finding Communities in Linear Time: A Physics Approach
- Phase transition in the detection of modules in sparse networks
- Detecting network communities by propagating labels under constraints
- Modularity-Maximizing Network Communities via Mathematical Programming
- Towards real-time community detection in large networks
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Robust network community detection using balanced propagation
- Community extraction for social networks
- Line Graphs of Weighted Networks for Overlapping Communities
- Overlapping stochastic block models with application to the French political blogosphere
- Community structure of complex software systems: Analysis and applications
- Clustering Drives Assortativity and Community Structure in Ensembles of Networks
- Note on the equivalence of the label propagation method of community detection and a Potts model approach
- Protein-Interaction-Networks: More than mere modules
- Topologically biased random walk with application for community finding in networks
- Random field Ising model and community structure in complex networks
Cited by in corpus (7)
- Clustering and Community Detection in Directed Networks: A Survey
- Software systems through complex networks science: Review, analysis and applications
- Network-based statistical comparison of citation topology of bibliographic databases
- Group detection in complex networks: An algorithm and comparison of the state of the art
- Sampling promotes community structure in social and information networks
- Label propagation for clustering
- Node mixing and group structure of complex software networks