Context-Sensitive Detection of Local Community Structure

Local methods for detecting community structure are necessary when a graph's size or node-expansion cost make global community-detection methods infeasible. Various algorithms for local community detection have been proposed, but there has been little analysis of the circumstances under which one approach is preferable to another. This paper describes an evaluation comparing the accuracy of five alternative local community-detection algorithms in detecting two distinct types of community structures—vertex partitions that maximize modularity, and link clusters that maximize partition density—in a variety of graphs. In this evaluation, the algorithm that most accurately identified modularity-maximizing community structure in a given graph depended on how closely the graph's degree distribution approximated a power-law distribution. When the target community structure was partition-density maximization, however, an algorithm based on spreading activation generally performed best, regardless of degree distribution.