A0792
Title: Community estimation on non-binary networks
Authors: Min Xu - Rutgers University (United States) [presenting]
Abstract: Community identification in a network is an important problem in fields such as social science, neuroscience, and genetics. Over the past decade, stochastic block models (SBMs) have emerged as a popular statistical framework for this problem. However, SBMs have an important limitation in that they are suited only for networks with binary edges. Network edges often carry additional information such as weights; disregarding such edge information may result in deteriorated performance in various scientific applications. We study a generalization of the SBM, in which a network is represented in the form of a non-binary adjacency array and the observation that correspond to each edge is generated independently from an unknown probability distribution determined by the community membership of its endpoints. In the case where the observations are real-valued, we characterize the optimal rate of misclustering error of the weighted SBM in terms of the Renyi divergence of order 1/2 between the distributions of within-community and between-community edges, substantially generalizing existing results for SBMs. Furthermore, we present a computationally tractable algorithm based on discretization that achieves the optimal error rate. Our method is adaptive in the sense that the algorithm, without assuming knowledge of the edge distributions, performs as well as the best algorithm that knows the edge distribution.
