Defining and identifying communities in networks

Abstract

The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic, cellular or protein networks) or technological problems (optimization of large infrastructures). Several types of algorithm exist for revealing the community structure in networks, but a general and quantitative definition of community is still lacking, leading to an intrinsic difficulty in the interpretation of the results of the algorithms without any additional non-topological information. In this paper we face this problem by introducing two quantitative definitions of community and by showing how they are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a new local algorithm to detect communities which outperforms the existing algorithms with respect to the computational cost, keeping the same level of reliability. The new algorithm is tested on artificial and real-world graphs. In particular we show the application of the new algorithm to a network of scientific collaborations, which, for its size, can not be attacked with the usual methods. This new class of local algorithms could open the way to applications to large-scale technological and biological applications.

Revtex, final form, 14 pages, 6 figures

References in corpus (15)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Epidemic spreading in scale-free networks
• The structure of scientific collaboration networks
• The diameter of the world wide web
• Hierarchical organization of modularity in metabolic networks
• The large-scale organization of metabolic networks
• Self-similar community structure in organisations
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Why social networks are different from other types of networks
• Epidemics and percolation in small-world networks
• Subnetwork hierarchies of biochemical pathways
• Robust Patterns in Food Web Structure
• On the Widespread Occurrence of the Inverse Square Distribution in Social Sciences and Taxonomy

Cited by in corpus (274)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Analysis of weighted networks
• Characterization of complex networks: A survey of measurements
• Community detection algorithms: a comparative analysis
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Quantifying social group evolution
• Community detection in complex networks using Extremal Optimization
• Scale-free brain functional networks
• Finding statistically significant communities in networks
• Vertex similarity in networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Consensus clustering in complex networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• An information-theoretic framework for resolving community structure in complex networks
• Finding local community structure in networks
• Communicability in complex networks
• Detect overlapping and hierarchical community structure in networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Clique percolation in random networks
• Limits of modularity maximization in community detection
• Community Discovery in Dynamic Networks: a Survey
• Generalized Louvain Method for Community Detection in Large Networks
• Structure and dynamics of core-periphery networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Robustness of community structure in networks
• Analysis of a large-scale weighted network of one-to-one human communication
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Complex Networks as Hypergraphs
• A Classification for Community Discovery Methods in Complex Networks
• Towards real-time community detection in large networks
• A Local Method for Detecting Communities
• Community Detection in Complex Networks Using Genetic Algorithms
• Detecting highly overlapping community structure by greedy clique expansion
• Triadic closure as a basic generating mechanism of communities in complex networks
• Characterizing the community structure of complex networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Dynamical Patterns of Cattle Trade Movements
• A sequential algorithm for fast clique percolation
• The clustering coefficient and community structure of bipartite networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Finding Community Structure in Mega-scale Social Networks
• Robust network community detection using balanced propagation
• Local resolution-limit-free Potts model for community detection
• Evaluating Local Community Methods in Networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Identifying network communities with a high resolution
• Enhancing network robustness for malicious attacks
• Exploring the Free Energy Landscape: From Dynamics to Networks and Back
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Local modularity measure for network clusterizations
• Identifying "communities" within energy landscapes
• Clustering in complex networks. I. General formalism
• Structural Inference of Hierarchies in Networks
• Tuning clustering in random networks with arbitrary degree distributions
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Quantifying and identifying the overlapping community structure in networks
• Clustering coefficients for correlation networks
• Improved community structure detection using a modified fine tuning strategy
• Finding instabilities in the community structure of complex networks
• Clustering in complex networks. II. Percolation properties
• Statistical significance of communities in networks
• Networks of strong ties
• Community structure and ethnic preferences in school friendship networks
• When are networks truly modular?
• Computing communities in large networks using random walks (long version)
• Empirical Comparison of Algorithms for Network Community Detection
• Synchronization interfaces and overlapping communities in complex networks
• Evolving Clustered Random Networks
• Spectral methods for the detection of network community structure: a comparative analysis
• A network-based prediction of retail stores commercial categories and optimal locations
• Z-score-based modularity for community detection in networks
• Community Detecting By Signaling on Complex Networks
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Clustering implies geometry in networks
• Community structure of complex software systems: Analysis and applications
• A Review of Modularization Techniques in Artificial Neural Networks
• The Organization of Strong Links in Complex Networks
• A New Approach to Analyzing Patterns of Collaboration in Co-authorship Networks - Mesoscopic Analysis and Interpretation
• Synchronization on community networks
• Deciphering the global organization of clustering in real complex networks
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Exploring the structural regularities in networks
• Preferential attachment of communities: the same principle, but a higher level
• Finding and testing network communities by lumped Markov chains
• Fundamental statistical features and self-similar properties of tagged networks
• Comparison of Communities Detection Algorithms for Multiplex
• Community structure: A comparative evaluation of community detection methods
• Detectability of communities in heterogeneous networks
• The networked seceder model: Group formation in social and economic systems
• Inhibiting failure spreading in complex networks
• Deep Community Detection
• Coexistence of opposite opinions in a network with communities
• Random Sierpinski network with scale-free small-world and modular structure
• Covariance, correlation matrix and the multi-scale community structure of networks
• Trading strategies in the Italian interbank market
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Collectively optimal routing for congested traffic limited by link capacity
• Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
• Large network community detection by fast label propagation
• Community Detection in Complex Networks Using Density-based Clustering Algorithm
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Lurking in Social Networks: Topology-based Analysis and Ranking Methods
• Modular networks emerge from multiconstraint optimization
• Random field Ising model and community structure in complex networks
• Unveiling community structures in weighted networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• A comparative analysis of the statistical properties of large mobile phone calling networks
• Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
• Limitation of multi-resolution methods in community detection
• Inversion method for content-based networks
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Soft communities in similarity space
• Efficient community-based control strategies in adaptive networks
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Discrete-time quantum walk on complex networks for community detection
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Broad lifetime distributions for ordering dynamics in complex networks
• Community detection using boundary nodes in complex networks
• Bridge Bounding: A Local Approach for Efficient Community Discovery in Complex Networks
• Significant communities in large sparse networks
• Detecting community structure in networks using edge prediction methods
• A paradox in community detection
• Cross-validation estimate of the number of clusters in a network
• Spectral transitions in networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Epistemic communities: description and hierarchic categorization
• Growing Story Forest Online from Massive Breaking News
• Synwalk -- Community Detection via Random Walk Modelling
• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Using shortest path to discover criminal community
• Combinatorial approach to Modularity
• A novel metric for community detection
• Enhancing community detection by local structural information
• Classical Information Theory of Networks
• Detecting problematic transactions in a consumer-to-consumer e-commerce network
• Alternative approach to community detection in networks
• Gene communities in co-expression networks across different tissues
• Sampling promotes community structure in social and information networks
• Artificial Benchmark for Community Detection with Outliers (ABCD+o)
• Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
• Organization of networks with tagged nodes and biased links: a priori distinct communities. The case of Intelligent Design Proponents and Darwinian Evolution Defenders
• Scaling in the structure of directory trees in a computer cluster
• On Accuracy of Community Structure Discovery Algorithms
• Discovering Network Structure Beyond Communities
• Mapping weblog communities
• Community detection using preference networks
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Community detection by spectral methods in multi-layer networks
• Power-law relations in random networks with communities
• Seeding for pervasively overlapping communities
• Fast Heuristic Algorithm for Multi-scale Hierarchical Community Detection
• Network clustering and community detection using modulus of families of loops
• Local degree blocking model for link prediction in complex networks
• Emergence of Blind Areas in Information Spreading
• Multi-resolution community detection in massive networks
• Label propagation for clustering
• Systems Applications of Social Networks
• Inference for graphs and networks: Extending classical tools to modern data
• Networking genetic regulation and neural computation: Directed network topology and its effect on the dynamics
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• Community detection based on first passage probabilities
• Finding overlapping communities in networks using evolutionary method
• The stability to instability transition in the structure of large scale networks
• Collective effects of link failures in linear flow networks
• Resampling effects on significance analysis of network clustering and ranking
• Temporal prediction of epidemic patterns in community networks
• Communities and classes in symmetric fractals
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• Topics as Clusters of Citation Links to Highly Cited Sources: The Case of Research on International Relations
• Detecting the optimal number of communities in complex networks
• Community Detection in Complex Networks Using Agents
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Modeling the Co-occurrence Principles of the Consonant Inventories: A Complex Network Approach
• Critical field-exponents for secure message-passing in modular networks
• Heterogeneous Network Motifs
• Hierarchical community detection by recursive partitioning
• Consistent Community Identification in Complex Networks
• An Exact No Free Lunch Theorem for Community Detection
• Emergence of Clustering in an Acquaintance Model without Homophily
• Measures and Optimization for Robustness and Vulnerability in Disconnected Networks
• Detecting Rare and Weak Spikes in Large Covariance Matrices
• Minimal paths between communities induced by geographical networks
• Eigenvector localization as a tool to study small communities in online social networks
• Discovery and analysis of biochemical subnetwork hierarchies
• Fast Community Identification by Hierarchical Growth
• Decoding communities in networks
• Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Dual communities in spatial networks
• Criterions for locally dense subgraphs
• The Community Structure of Econophysicist Collaboration Networks
• Opinion dynamics on a group structured adaptive network
• Emergence of Long-Range Correlations in Random Networks
• Metrics matter in community detection
• Obtaining Communities with a Fitness Growth Process
• Asymmetry of social interactions and its role in link predictability: the case of coauthorship networks
• Exploring triad-rich substructures by graph-theoretic characterizations in complex networks
• Network Community Detection on Metric Space
• An Introduction to Community Detection in Multi-layered Social Network
• Overlapping Communities in Social Networks
• Emergent poverty traps and inequality at multiple levels impedes social mobility
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• Local multiresolution order in community detection
• Identifying robust features of community structure in complex networks
• Decision Predicate Graphs: Enhancing Interpretability in Tree Ensembles
• Self-Organizing Maps of Unbiased Ligand-Target Binding Pathways and Kinetics
• A mixed clustering coefficient centrality for identifying essential proteins
• Unsupervised Network Embedding for Graph Visualization, Clustering and Classification
• Community Structure Characterization
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Detecting Statistically Significant Communities
• Community detection by resistance distance: automation and benchmark testing
• The Atlas for the Aspiring Network Scientist
• Graph Theoretical Analysis of local ultraluminous infrared galaxies and quasars
• Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
• A multilevel clustering technique for community detection
• Metrics for Community Analysis: A Survey
• Environmental versatility promotes modularity in genome-scale metabolic networks
• Transforming complex network to the acyclic one
• On Finding the Community with Maximum Persistence Probability
• The spark of synchronization in heterogeneous networks of chaotic maps
• A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
• Router-level community structure of the Internet Autonomous Systems
• A Systematic Survey on Multi-relational Community Detection
• Homophilic Clustering by Locally Asymmetric Geometry
• AOT: Pushing the Efficiency Boundary of Main-memory Triangle Listing
• Clustering evolving data using kernel-based methods
• The Development of Visualization Psychology Analysis Tools to Account for Trust
• Towards Modularity Optimization Using Reinforcement Learning to Community Detection in Dynamic Social Networks
• Weighted Label Propagation Algorithm based on Local Edge Betweenness
• A new method for quantifying network cyclic structure to improve community detection
• A Continuous Opinion Dynamic Model in Co-evolving Networks--A Novel Group Decision Approach
• Symmetrical SyncMap for Imbalanced General Chunking Problems
• Emergence of network communities driven by local rules
• Detecting overlapping communities in linear time with P&A algorithm
• When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
• Two new methods for identifying proteins based on the domain protein complexes and topological properties
• On the Topology Maintenance of Dynamic P2P Overlays through Self-Healing Local Interactions
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Homophyly Networks -- A Structural Theory of Networks
• The attack tolerance of community structure in complex networks
• Analysis of Clustering and Degree Index in Random Graphs and Complex Networks
• Overlapping community detection in weighted networks
• Absence of a resolution limit in in-block nestedness
• A High-Performance Evolutionary Multiobjective Community Detection Algorithm
• Identification of Community Structures in Networks Employing a Modified Divisive Algorithm
• A Dynamic Vulnerability Map to Assess the Risk of Road Network Traffic Utilization
• Streaming Belief Propagation for Community Detection
• Self-Healing Protocols for Connectivity Maintenance in Unstructured Overlays
• Flow approaches to community detection in complex network systems
• Graph Metrics for Internet Robustness -- A Survey
• Detección de comunidades en redes: Algoritmos y aplicaciones
• Developing Effective Community Network Analysis Tools According to Visualization Psychology
• A two-layer team-assembly model for invention networks
• Analysis of Social Group Dynamics
• Ground state energy of $q$-state Potts model: the minimum modularity
• Overlapping Communities in Complex Networks