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.
Similar content being viewed by others
References
L. Freeman, Sociometry 40, 35-41 (1977)
M.E.J. Newman, M. Girvan, Finding and evaluating community structure in networks, cond-mat/0308217 (2003)
M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. USA 99, 8271-8276 (2002)
D. Wilkinson, B.A. Huberman, Proc. Natl. Acad. Sci. USA 10, 1073 (2004)
J. Tyler, D. Wilkinson, B.A. Huberman, Email as Spectroscopy: Automated Discovery of Community Structure within Organizations, Communities and Technologies, edited by M. Huysman, E. Wegner, V. Wulf (Kluwer Academic, 2003)
B. Kernighan, S. Lin, Bell Sys. Techn. J. 29, 291-307 (1970)
C. Fiduccia, R. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th IEEE Design Automation Conference, 175-181 (1982)
A. Pothen, H. Simon, K.P. Liou, SIAM J. Matrix Anal. Appl. 11, 430-452 (1990)
M. Fiedler, Czech. Math. J. 23, 298 (1973)
M. Fiedler, Czech. Math. J. 25, 619 (1975)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to algorithms, 2nd edn. (MIT Press, 2001), p. 189, p. 168
W.W. Zachary, Anthropological Res. 33, 452 (1977)
B. Rabinovich, A. Rapoport, Graphs, Geometry and Probability, Lecture 7 (March 2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 29 October 2003, Published online: 14 May 2004
PACS:
89.75.Fb Structures and organization in complex systems - 89.75.Hc Networks and genealogical trees
Rights and permissions
About this article
Cite this article
Wu, F., Huberman, B.A. Finding communities in linear time: a physics approach. Eur. Phys. J. B 38, 331–338 (2004). https://doi.org/10.1140/epjb/e2004-00125-x
Published:
Issue Date:
DOI: https://doi.org/10.1140/epjb/e2004-00125-x