Abstract:

Mixed membership estimation is a problem of great interest in social network analysis. Consider an undirected network with n nodes and K unknown communities. Each node i is associated with a Probability Mass Function pi_i = (pi_i(1), pi_i(2), ..., pi_i(K))', where pi_i(k) is the “weight” that node i puts on community k. Our goal is to estimate these vectors pi_1, pi_2,..., pi_n. This problem is related to community detection but is more challenging. We adopt a Degree-Corrected Mixed-Membership (DCMM) model and propose a spectral approach called Mixed-SCORE for estimating mixed memberships. The key ideas behind Mixed-SCORE include: (1) A post-PCA normalization on the eigenvectors of the adjacency matrix; this normalization was proposed by Jin (2015) to help remove the effects of severe degree-heterogeneity. (2) A low-dimensional simplex structure associated with the eigenvectors (our main discovery). Aided by this simplex geometry, we obtain simple and explicit operations to convert eigenvectors to targeting membership vectors. Numerical comparison of Mixed-SCORE with state-of-art methods suggests the computational advantage of our method. We have also derived the rate of convergence of Mixed-SCORE and shown it achieves the minimax rate in a variety of settings. We applied Mixed-SCORE and obtained encouraging results on 4 data sets, a political book network, a college football network, and two networks of statisticians (Ji and Jin, 2016). The mixed-memberships on two statisticians’ networks reveal interesting collaboration and citation patterns in the statistics community. (Joint work with Jiashun Jin and Shengming Luo)