Local Betweenness for Finding Communities in Networks

Steve Gregory

Research output: Working paperWorking paper and Preprints

Abstract

The betweenness centrality measure has been widely used for detecting community structure in networks, in particular in the "GN" algorithm due to Girvan and Newman. This suffers from low speed because the betweenness measure is computed from the entire network, and it has been largely supplanted by faster algorithms that can detect community structure using more local methods in place of betweenness. In contrast, we propose an algorithm (a variant of GN) based on a local form of betweenness, which yields good results and is much faster. The algorithm can be used with a single parameter: the average diameter of the communities to be found. It is especially effective in detecting small-diameter communities in large networks, with a time complexity of only O(n log n) for sparse networks.
Translated title of the contributionLocal Betweenness for Finding Communities in Networks
Original languageEnglish
PublisherDepartment of Computer Science, University of Bristol
Publication statusPublished - 2008

Bibliographical note

Other page information: -
Other identifier: 2000856

Cite this