Effect of size heterogeneity on community identification in complex networks

Abstract

Identifying community structure can be a potent tool in the analysis and understanding of the structure of complex networks. Up to now, methods for evaluating the performance of identification algorithms use ad-hoc networks with communities of equal size. We show that inhomogeneities in community sizes can and do affect the performance of algorithms considerably, and propose an alternative method which takes these factors into account. Furthermore, we propose a simple modification of the algorithm proposed by Newman for community detection (Phys. Rev. E {\bf 69} 066133) which treats communities of different sizes on an equal footing, and show that it outperforms the original algorithm while retaining its speed.

6 pages, 4 figures

References in corpus (26)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating 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
• Cooperative Game Theory Approaches for Network Partitioning
• The diameter of the world wide web
• Hierarchical organization of modularity in metabolic networks
• Functional cartography of complex metabolic networks
• Comparing community structure identification
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• Detecting Network Communities: a new systematic and efficient algorithm
• A Method to Find Community Structures Based on Information Centrality
• A Local Method for Detecting Communities
• Community analysis in social networks
• Network Landscape from a Brownian Particle's Perspective
• Finding instabilities in the community structure of complex networks

Cited by in corpus (26)

• Community detection in graphs
• Characterization of complex networks: A survey of measurements
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Community Discovery in Dynamic Networks: a Survey
• Module identification in bipartite and directed networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Multiresolution community detection for megascale networks by information-based replica correlations
• Local resolution-limit-free Potts model for community detection
• Efficiently inferring community structure in bipartite networks
• Combining complex networks and data mining: why and how
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• The stability of a graph partition: A dynamics-based framework for community detection
• Bloggers Behavior and Emergent Communities in Blog Space
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Significant communities in large sparse networks
• Information content: assessing meso-scale structures in complex networks
• Combinatorial approach to Modularity
• Discovering Network Structure Beyond Communities
• Multi-attribute community detection in International Trade Network
• Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
• Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection
• Resampling effects on significance analysis of network clustering and ranking
• Outlier Edge Detection Using Random Graph Generation Models and Applications
• Detecting hierarchical and overlapping network communities using locally optimal modularity changes
• Limited Random Walk Algorithm for Big Graph Data Clustering
• A new measure of modularity density for community detection