Searching for a Single Community in a Graph
This addresses the problem of efficiently identifying specific communities in graphs for applications like social network analysis, though it is incremental as it builds on existing community detection with side information.
The paper tackles the problem of finding a single target community in a graph using side information, such as node weights, and develops a method of moments variant that improves reliability and reduces computation compared to generic community detection methods, with empirical results showing significant gains in runtime and accuracy.
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.