Finding Communities in Linear Time: A Physics Approach

Abstract

We present a method that allows for the discovery of communities within graphs of arbitrary size in times that scale linearly with their size. This method avoids edge cutting and is based on notions of voltage drops across networks that are both intuitive and easy to solve regardless of the complexity of the graph involved. We additionally show how this algorithm allows for the swift discovery of the community surrounding a given node without having to extract all the communities out of a graph.

References in corpus (3)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning

Cited by in corpus (64)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Near linear time algorithm to detect community structures in large-scale networks
• Comparing community structure identification
• Analysis of weighted networks
• Characterization of complex networks: A survey of measurements
• Statistical Mechanics of Community Detection
• Finding local community structure in networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Robustness of community structure in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Classification for Community Discovery Methods in Complex Networks
• A Method to Find Community Structures Based on Information Centrality
• Finding Community Structure in Mega-scale Social Networks
• Robust network community detection using balanced propagation
• Exploring the Free Energy Landscape: From Dynamics to Networks and Back
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Identifying "communities" within energy landscapes
• Improved community structure detection using a modified fine tuning strategy
• Social significance of community structure: Statistical view
• Computing communities in large networks using random walks (long version)
• The Naming Game in Social Networks: Community Formation and Consensus Engineering
• A Large-Scale Community Structure Analysis In Facebook
• Anomalous Transport in Complex Networks
• Community Detecting By Signaling on Complex Networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Coexistence of opposite opinions in a network with communities
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Communities in Networks
• Unveiling community structures in weighted networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Random field Ising model and community structure in complex networks
• Scaling in Small-World Resistor Networks
• Limitation of multi-resolution methods in community detection
• Measuring Significance of Community Structure in Complex Networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Bridge Bounding: A Local Approach for Efficient Community Discovery in Complex Networks
• Revealing structure-function relationships in functional flow networks via persistent homology
• Balancer effects in opinion dynamics
• Effect of size heterogeneity on community identification in complex networks
• Sampling promotes community structure in social and information networks
• Thermodynamic approach for community discovering within the complex networks: LiveJournal study
• Partition of Networks into Basins of Attraction
• Communities and classes in symmetric fractals
• Locally computable approximations for spectral clustering and absorption times of random walks
• Community Detection in Complex Networks Using Agents
• Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks
• The Community Structure of Econophysicist Collaboration Networks
• Statistical Characteristics and Community analysis of Urban Road Networks
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• Network Community Detection on Metric Space
• A Modular Multiscale Approach to Overlapping Community Detection
• How to Measure Significance of Community Structure in Complex Networks
• Transforming complex network to the acyclic one
• Detecting overlapping communities in linear time with P&A algorithm
• Nearest Neighbor search in Complex Network for Community Detection
• Ground state energy of $q$-state Potts model: the minimum modularity
• Estimating Thematic Similarity of Scholarly Papers with Their Resistance Distance in an Electric Network Model