Finding Communities in Linear Time: A Physics Approach

Preprint

26 October 2003

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.cond-mat/0310600

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.

Keywords

FINDING COMMUNITIES
PHYSICS APPROACH
LINEAR TIME
AVOIDS EDGE
INTUITIVE
DISCOVERY
ALGORITHM
EXTRACT
GRAPH

All Related Versions

Version 1, 2003-10-26, ArXiv
Published version: Zeitschrift für Physik B Condensed Matter, 38 (2), 331.

This publication has 0 references indexed in Scilit: