Directed degree corrected mixed membership model and estimating community memberships in directed networks

This paper considers the problem of modeling and estimating community memberships of nodes in a directed network where every row (column) node is associated with a vector determining its membership in each row (column) community. To model such directed network, we propose directed degree corrected mixed membership (DiDCMM) model by considering degree heterogeneity. DiDCMM is identifiable under popular conditions for mixed membership network when considering degree heterogeneity. Based on the cone structure inherent in the normalized version of the left singular vectors and the simplex structure inherent in the right singular vectors of the population adjacency matrix, we build an efficient algorithm called DiMSC to infer the community membership vectors for both row nodes and column nodes. By taking the advantage of DiMSCs equivalence algorithm which returns same estimations as DiMSC and the recent development on row-wise singular vector deviation, we show that the proposed algorithm is asymptotically consistent under mild conditions by providing error bounds for the inferred membership vectors of each row node and each column node under DiDCMM. The theory is supplemented by a simulation study.

Bipartite mixed membership stochastic blockmodel

Mixed membership problem for undirected network has been well studied in network analysis recent years. However, the more general case of mixed membership for directed network remains a challenge. Here, we propose an interpretable model: bipartite mixed membership stochastic blockmodel (BiMMSB for short) for directed mixed membership networks. BiMMSB allows that row nodes and column nodes of the adjacency matrix can be different and these nodes may have distinct community structure in a directed network. We also develop an efficient spectral algorithm called BiMPCA to estimate the mixed memberships for both row nodes and column nodes in a directed network. We show that the approach is asymptotically consistent under BiMMSB. We demonstrate the advantages of BiMMSB with applications to a small-scale simulation study, the directed Political blogs network and the Papers Citations network.

Estimating mixed-memberships using the Symmetric Laplacian Inverse Matrix

Community detection has been well studied in network analysis, and one popular technique is spectral clustering which is fast and statistically analyzable for detect-ing clusters for given networks. But the more realistic case of mixed membership community detection remains a challenge. In this paper, we propose a new spectral clustering method Mixed-SLIM for mixed membership community detection. Mixed-SLIM is designed based on the symmetrized Laplacian inverse matrix (SLIM) (Jing et al. 2021) under the degree-corrected mixed membership (DCMM) model. We show that this algorithm and its regularized version Mixed-SLIM {tau} are asymptotically consistent under mild conditions. Meanwhile, we provide Mixed-SLIM appro and its regularized version Mixed-SLIM {tau}appro by approximating the SLIM matrix when dealing with large networks in practice. These four Mixed-SLIM methods outperform state-of-art methods in simulations and substantial empirical datasets for both community detection and mixed membership community detection problems.

An improved spectral clustering method for mixed membership community detection

Community detection has been well studied recent years, but the more realistic case of mixed membership community detection remains a challenge. Here, we develop an efficient spectral algorithm Mixed-ISC based on applying more than K eigenvectors for clustering given K communities for estimating the community memberships under the degree-corrected mixed membership (DCMM) model. We show that the algorithm is asymptotically consistent. Numerical experiments on both simulated networks and many empirical networks demonstrate that Mixed-ISC performs well compared to a number of benchmark methods for mixed membership community detection. Especially, Mixed-ISC provides satisfactory performances on weak signal networks.

An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel

For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochastic block model (DCSBM). ISC is designed based on the k-means clustering algorithm on the weighted leading K + 1 eigenvectors of a regularized Laplacian matrix where the weights are their corresponding eigenvalues. Theoretical analysis of ISC shows that under mild conditions the ISC yields stable consistent community detection. Numerical results show that ISC outperforms classical spectral clustering methods for community detection on both simulated and eight empirical networks. Especially, ISC provides a significant improvement on two weak signal networks Simmons and Caltech, with error rates of 121/1137 and 96/590, respectively.