统计与管理学院2017年学术报告第81期
【主 题】 A spectral approach to estimating network mixed memberships
【报告人】 柯峥, 助教授
University of Chicago
【时 间】 2017年12月19日（星期二）16:10-16:50
【地 点】 上海财经大学统计与管理学院大楼1208会议室
【摘 要】Consider an undirected mixed membership network with n nodes and K communities. For each node i, 1 ≤ i ≤ n, we model the membership by a Probability Mass Function (PMF) πi = (πi(1), πi(2), . . ., πi(K))′, where πi(k) is the probability that node i belongs to community k, 1 ≤ k ≤ K. We call node i “pure” if πi is degenerate (i.e., πi(k)=1 for some k) and “mixed” otherwise. The primary interest is to estimate πi, 1 ≤ i ≤ n. This problem is closely related to community detection but is more challenging.
We propose a new spectral approach called Mixed-SCORE. At the heart of our method is a (tall but very skinny) matrix of entry-wise ratios, formed by dividing by the first few eigenvectors of the network adjacency matrix over the leading eigenvector of the same matrix in an entry-wise fashion. We reveal a surprising phenomenon: Rows of the entry-wise ratio matrix form a cloud of points in a low-dimensional space with the silhouette of a simplex, where a row corresponding to a pure node falls close to one of the K vertices of the simplex, and other rows approximately fall in the interior of the simplex. With a novel Vertex Hunting algorithm, Mixed-SCORE estimates the mixed memberships directly from the entry-wise ratio matrix.
This method has been applied to 4 real networks with encouraging results. In particular, the results on two networks of statisticians (a coauthorship network and a citee network) shed light on the research patterns and topology of statisticians.
We studied the rate of convergence of Mixed-SCORE and showed that it achieves the minimax lower bound for a range of parameter settings.
(Joint work with Jiashun Jin and Shengming Luo)
