Incremental Detection of Local Community Structure

Incremental methods for detecting community structure are necessary when a graph's size or node-expansion cost makes global community-detection methods infeasible. Previous approaches to local community detection, which conflate edges between vertices in the immediate neighborhood of a partially-known community with edges to more distant vertices, often select vertices in an order that is suboptimal with respect to the actual community structure. This paper describes two new algorithms--MaxActivation and MaxDensity--whose vertex-selection policies focus on edges among the vertices in the partially-known community and its immediate neighborhood, ignoring edges to more distant vertices. In an empirical evaluation on a collection of natural and artificial graphs of varying degrees of community cohesion, the relative performance of alternative algorithms depended upon the degree distribution of each graph. These results demonstrate that the selection of an algorithm for incremental community detection should be guided by the characteristics of the graph to which it will be applied.