Distribution-Free Models for Community Detection

• URL: http://arxiv.org/abs/2111.07495v1
• Date: Mon, 15 Nov 2021 02:10:52 GMT
• Title: Distribution-Free Models for Community Detection
• Authors: Huan Qing
• Abstract summary: A Distribution-Free Models (DFM) is proposed for networks in which nodes are partitioned into different communities. DFM is a general, interpretable and identifiable model for both un-weighted networks and weighted networks. By introducing a noise matrix, we build the theoretic framework on perturbation analysis to show that the proposed algorithm stably yields consistent community detection.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection for un-weighted networks has been widely studied in network analysis, but the case of weighted networks remains a challenge. In this paper, a Distribution-Free Models (DFM) is proposed for networks in which nodes are partitioned into different communities. DFM is a general, interpretable and identifiable model for both un-weighted networks and weighted networks. The proposed model does not require prior knowledge on a specific distribution for elements of adjacency matrix but only the expected value. The distribution-free property of DFM even allows adjacency matrix to have negative elements. We develop an efficient spectral algorithm to fit DFM. By introducing a noise matrix, we build a theoretic framework on perturbation analysis to show that the proposed algorithm stably yields consistent community detection under DFM. Numerical experiments on both synthetic networks and two social networks from literature are used to illustrate the algorithm.

Related papers

• A pseudo-likelihood approach to community detection in weighted networks [4.111899441919165]
  We propose a pseudo-likelihood community estimation algorithm for networks with normally distributed edge weights. We prove that the estimates obtained by the proposed method are consistent under the assumption of homogeneous networks. We illustrate the method on simulated networks and on a fMRI dataset, where edge weights represent connectivity between brain regions.
  arXiv  Detail & Related papers  (2023-03-10T13:36:10Z)
• Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy [52.40331776572531]
  We show that learning depth-$3$ ReLU networks under the Gaussian input distribution is hard even in the smoothed-analysis framework. Our results are under a well-studied assumption on the existence of local pseudorandom generators.
  arXiv  Detail & Related papers  (2023-02-15T02:00:26Z)
• Leveraging a Probabilistic PCA Model to Understand the Multivariate Statistical Network Monitoring Framework for Network Security Anomaly Detection [64.1680666036655]
  We revisit anomaly detection techniques based on PCA from a probabilistic generative model point of view. We have evaluated the mathematical model using two different datasets.
  arXiv  Detail & Related papers  (2023-02-02T13:41:18Z)
• Signed Network Embedding with Application to Simultaneous Detection of Communities and Anomalies [25.541992448747695]
  This paper develops a unified embedding model for signed networks to disentangle the intertwined balance structure and anomaly effect. The proposed model captures both balance structure and anomaly effect through a low rank plus sparse matrix decomposition. The advantage of the proposed embedding model is also demonstrated through extensive numerical experiments on both synthetic networks and an international relation network.
  arXiv  Detail & Related papers  (2022-07-08T03:58:56Z)
• Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
  In Bayesian structure learning, we are interested in inferring a distribution over the directed acyclic graph (DAG) from data. Recently, a class of probabilistic models, called Generative Flow Networks (GFlowNets), have been introduced as a general framework for generative modeling. We show that our approach, called DAG-GFlowNet, provides an accurate approximation of the posterior over DAGs.
  arXiv  Detail & Related papers  (2022-02-28T15:53:10Z)
• Equilibrated Zeroth-Order Unrolled Deep Networks for Accelerated MRI [14.586911990418624]
  Recently, model-driven deep learning unrolls a certain iterative algorithm of a regularization model into a cascade network. In theory, there is not necessarily such a functional regularizer whose first-order information matches the replaced network module. This paper propose to present a safeguarded methodology on network unrolling.
  arXiv  Detail & Related papers  (2021-12-18T09:47:19Z)
• Mixed membership distribution-free model [0.4972323953932129]
  We consider the problem of community detection in overlapping weighted networks, where nodes can belong to multiple communities and edge weights can be finite real numbers. To model such complex networks, we propose a general framework - the mixed membership distribution-free (MMDF) model. We use an efficient spectral algorithm with a theoretical guarantee of convergence rate to estimate community memberships under the model.
  arXiv  Detail & Related papers  (2021-12-04T18:21:02Z)
• Community detection for weighted bipartite networks [1.0965065178451106]
  citerohe2016co proposed co-Blockmodel (ScBM) as a tool for detecting community structure of binary bipartite graph data in network studies. Here, to model a weighted bipartite network, we introduce a Bipartite Distribution-Free model by releasing ScBM's distribution restriction. Our models do not require a specific distribution on generating elements of the adjacency matrix but only a block structure on the expected adjacency matrix.
  arXiv  Detail & Related papers  (2021-09-21T17:01:36Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• 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)
• A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network Representation Learning [52.83948119677194]
  We propose a multi-semantic metapath (MSM) model for large scale heterogeneous representation learning. Specifically, we generate multi-semantic metapath-based random walks to construct the heterogeneous neighborhood to handle the unbalanced distributions. We conduct systematical evaluations for the proposed framework on two challenging datasets: Amazon and Alibaba.
  arXiv  Detail & Related papers  (2020-07-19T22:50:20Z)

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.