Robust and Flexible Statistical Methods for Localized Community Detection

Abstract

We consider the problem of localized community detection (LCD): given a large network and a small set of important seed vertices, identify a local community of closely linked vertices, known as the goal block. Unlike traditional community detection, which seeks to identify large-scale structure in the entire graph, LCD only requires identification of local structure relevant to the seed set. To perform this task, we analyze random walks on the graph and nominate vertices with small mean hitting times as members of the goal block. We analyze this problem under a flexible, non-parametric graphon model and establish quite general conditions on the graph structure that allow successful LCD. Notably, our results impose only minimal structure on the graph outside of the goal block, yielding a robust and flexible statistical toolkit for LCD. As part of our analysis, we develop strong concentration bounds for hitting times in random graphs sampled from arbitrary graphons that may be of independent interest.

• Department of Information Systems and Statistics, Baruch College, New York, NY USA
  [michael.weylandt@baruch.cuny.edu]

Keywords: Network Analysis – Community Detection – Seed-Set Expansion – Graphon – Non-Parametric

1 Seeded Community Detection

Consider a large, observed graph, $𝒢=(𝒱,ℰ)$. Given a small set of “seed” vertices, ${\mathrm{\Omega }}_0⊊𝒱$, localized community detection (LCD) attempts to identify a larger set of vertices, known as the goal block, $\widehat{\mathrm{\Omega }}\supset {\mathrm{\Omega }}_0$, that form a relevant community. LCD, also sometimes called seed-set expansion because several important algorithms “expand outwards” from the seed set, has found important applications in fields as varied as web search, neuroscience, and sports analytics, and forms the basis of several well-known variants of the PageRank algorithm. [Andersen et al., 2006, Gleich, 2015]

Note that LCD answers a fundamentally different question than traditional Community Detection (CD). In CD, several large-scale communities which divide the entire graph are identified and then analyzed to determine relevance to a particular scientific question. [Abbe, 2018] By contrast, LCD attempts to find only a small group of nodes most relevant to the seed set and makes no inference about the rest of the graph. For example, if CD is applied to the full (multi-lingual) Wikipedia network, the communities identified are language based (e.g., English Wiki, Spanish Wiki, etc.). By contrast, applying LCD with a seed set of recent winners of the COPSS Presidents’ Award, we hope to find a community comprised of the entries of leading statisticians. While it is theoretically possible to identify fine-grained communities by finding an enormous number of communities in CD, computation and estimation difficulties make this infeasible. [Yoder et al., 2020]

2 Analysis of Random Walk Hitting Times via Graphon Concentration

Following the proposal of Whang et al. [2013], we consider a random walk approach to LCD. For each vertex $v\notin {\mathrm{\Omega }}_0$, we compute the mean hitting time of $v$ to ${\mathrm{\Omega }}_0$: that is, the expected number of steps a random walk on $𝒢$ initialized at $v$ takes to arrive at an element of ${\mathrm{\Omega }}_0$. As noted by several authors, random walks are more adaptive to graph structure than more conventional metrics such as shortest-path distance. [Whang et al., 2013, Gleich, 2015, Su et al., 2017] In particular, random walks are able to adapt to the high degree skewness observed in real-world graphs and accurately capture the fact that relationships between nodes of different degree are highly asymmetric. As Foss et al. [2020] show, these hitting times can be computed efficiently requiring solving only a single linear system and avoiding the use of Monte Carlo techniques. This allows applications of LCD to extremely large graphs, even with only modest computational resources.

We analyze this approach under a flexible graphon model for the observed graph $𝒢$. In particular, we consider $𝒢$ as a finite-sample realization of an underlying inhomogeneous Erdös-Rènyi graph of infinite size. Building on prior analysis of Avella-Medina et al. [2020] who considered the graphon-limiting behvaior of the PageRank centrality measure, we first identify a linear integral equation (LIE) whose solution gives the expected hitting times for each vertex in $𝒢$. Additionally, we establish concentration bounds on these hitting times and show that, as the graph size grows, the hitting times in any finite realization concentrate rapidly around the graphon limit.

Analyzing this LIE, we establish conditions on the underlying graphon which guarantee that hitting-time based LCD correctly identifies the true goal block with high probability. Notably, our conditions are quite flexible, essentially only requiring that i) a goal block exists; ii) the goal block is well separated from the remainder of the graph; and iii) that non-goal block vertices all share more edges with other non-goal block vertices than with the goal block. Because this analysis does not impose strong conditions on the non-goal portion of the graph, it can be applied broadly and without assuming particular stochastic block model-type structure. Experiments demonstrate that this additional robustness yields significant improvements in several applications of interest.