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

• URL: http://arxiv.org/abs/2109.07826v1
• Date: Thu, 16 Sep 2021 09:35:16 GMT
• Title: Directed degree corrected mixed membership model and estimating community memberships in directed networks
• Authors: Huan Qing
• Abstract summary: We build an efficient algorithm called DiMSC to infer the community membership vectors for both row nodes and column nodes. We show that the proposed algorithm is consistent under mild conditions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 DiMSC's 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.

Related papers

• Reliable Node Similarity Matrix Guided Contrastive Graph Clustering [51.23437296378319]
  We introduce a new framework, Reliable Node Similarity Matrix Guided Contrastive Graph Clustering (NS4GC) Our method introduces node-neighbor alignment and semantic-aware sparsification, ensuring the node similarity matrix is both accurate and efficiently sparse.
  arXiv  Detail & Related papers  (2024-08-07T13:36:03Z)
• Bias-Corrected Joint Spectral Embedding for Multilayer Networks with Invariant Subspace: Entrywise Eigenvector Perturbation and Inference [0.0]
  We propose to estimate the invariant subspace across heterogeneous multiple networks using a novel bias-corrected joint spectral embedding algorithm. The proposed algorithm calibrates the diagonal bias of the sum of squared network adjacency matrices by leveraging the closed-form bias formula. We establish a complete recipe for the entrywise subspace estimation theory for the proposed algorithm, including a sharp entrywise subspace perturbation bound.
  arXiv  Detail & Related papers  (2024-06-12T03:36:55Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Bipartite mixed membership stochastic blockmodel [1.370633147306388]
  We propose an interpretable model: bipartite mixed membership blockmodel (BiMMSB) for directed mixed membership networks. We also develop an efficient spectral algorithm called BiMPCA to estimate mixed memberships for both row nodes and column nodes in a directed network.
  arXiv  Detail & Related papers  (2021-01-07T00:21:50Z)
• Consistency of regularized spectral clustering in degree-corrected mixed membership model [1.0965065178451106]
  We propose an efficient approach called mixed regularized spectral clustering (Mixed-RSC for short) based on the regularized Laplacian matrix. Mixed-RSC is designed based on an ideal cone structure of the variant for the eigen-decomposition of the population regularized Laplacian matrix. We show that the algorithm is consistent under mild conditions by providing error bounds for the inferred membership vector of each node.
  arXiv  Detail & Related papers  (2020-11-23T02:30:53Z)
• Overlapping community detection in networks via sparse spectral decomposition [1.0660480034605242]
  We consider the problem of estimating overlapping community memberships in a network, where each node can belong to multiple communities. Our algorithm is based on sparse principal subspace estimation with iterative thresholding. We show that a fixed point of the algorithm corresponds to correct node memberships under a version of the block model.
  arXiv  Detail & Related papers  (2020-09-20T07:31:09Z)
• Spectral Algorithms for Community Detection in Directed Networks [46.91424250933143]
  The D-SCORE algorithm for directed networks was introduced to reduce this effect by taking the element-wise ratios of the singular vectors of the adjacency matrix before clustering. Meaningful results were obtained for the statistician citation network, but rigorous analysis on its performance was missing. This paper establishes theoretical guarantee for this algorithm and its variants for the directed degree-corrected block model.
  arXiv  Detail & Related papers  (2020-08-09T21:43:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.