|
Context-Sensitive Detection of Local Community Structure
April 2011
L. Karl Branting, The MITRE Corporation
ABSTRACT
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.
Additional Search Keywords
n/a
|
