Local Betweenness for Finding Communities in Networks

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.