Finding communities in linear time: a physics approach

By Fang Wu, Bernardo A. Huberman. 2003

1,794 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Prioritizing network communities (2018, neutral): “Proceedings of the National Academy of Sciences 111, 6131–6138 (2014).”
Community detection in graphs (2009, methodology): “Modularity can be easily extended to graphs with weighted edges (Newman, 2004).”
Modularity and community structure in networks. (2006, neutral): “Modularity and community structure in networks”
The Economic Consequences of Social Network Structure (2017, background): “Beyond detecting such type-based communities, there is a large literature on trying to detect communities within networks (whether based on types or not) and many algorithms for doing so (see Newman (2004) for an early survey).”
The Economics of Social Networks (2005, methodology): “They developed a model that mixes purely random 40See Park and Newman (2004) for some derivations of clustering probabilities for this example.”
Graph theory and networks in Biology. (2006, background): “The detection of communities and modules in complex networks has been a subject of interest for some time in disciplines such as sociology, communications, and power systems, and a variety of techniques known collectively as hierarchical clustering have been developed for this problem [97, 167].”
A Survey of Statistical Network Models (2009, background): “A related question is functional clustering, where the goal is not to statistically cluster the network, but to discover members of dynamic communities with similar functions based on existing network connectivity [122; 232; 234; 266].”
Analysis of Public Bus Transportation of a Brazilian City Based on the Theory of Complex Networks Using the P-Space (2016, background): “It is possible to find communities in V-edges complex networks with few edges between the communities themselves [34].”
Method to find community structures based on information centrality. (2004, background): “[26] based on the notion of voltage drops across the network and running in time O ( K + N ).”