Title: Searching for a Single Community in a Graph,
Abstract: In standard graph clustering/community detection, one is interested in
partitioning the graph into more densely connected subsets of nodes. In
contrast, the "search" problem of this paper aims to only find the nodes in a
"single" such community, the target, out of the many communities that may
exist. To do so , we are given suitable side information about the target; for
example, a very small number of nodes from the target are labeled as such.
We consider a general yet simple notion of side information: all nodes are
assumed to have random weights, with nodes in the target having higher weights
on average. Given these weights and the graph, we develop a variant of the
method of moments that identifies nodes in the target more reliably, and with
lower computation, than generic community detection methods that do not use
side information and partition the entire graph. Our empirical results show
significant gains in runtime, and also gains in accuracy over other graph
clustering algorithms.