Global community detection using individual-centered partial information networks

The Spring 2022 SDS Seminar Series continues on Friday, April 15 from 2:00 p.m. to 3:00 p.m. with Dr. Rachel Wang (Senior Lecturer in the School of Mathematics and Statistics at the University of Sydney). This event is in-person, but a virtual option will be available as well. 

Title: Global community detection using individual-centered partial information networks

Abstract: In statistical network modeling and inference, we often assume either the full network is available or multiple subgraphs can be sampled to estimate various global properties of the full network. However, in a real social network, people frequently make decisions based on their local view of the network alone. In this talk, we consider a partial information framework that characterizes the local network centered at a given individual by path length (or knowledge depth $L$) and gives rise to a partial adjacency matrix. Under $L=2$, we focus on the problem of (global) community detection using the popular stochastic block model (SBM) and its degree-corrected variant (DCSBM). We derive general properties of the eigenvalues and eigenvectors from the major term of the partial adjacency matrix and propose new spectral-based community detection algorithms for these two types of models, which can achieve almost exact recovery under appropriate conditions. Our settings in the DCSBM also allow us to interpret the efficiency of clustering using neighborhood features of the central node. Using simulated and real networks, we demonstrate the performance of our algorithms in inferring global community memberships using a partial network. More importantly, we show that the clustering accuracy indicates different global structure is visible to different individuals.