Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian

• URL: http://arxiv.org/abs/2006.04510v2
• Date: Mon, 26 Oct 2020 09:17:16 GMT
• Title: Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Authors: Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
• Abstract summary: This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is proposed, which benefits from the positive correlation in the class labels and in their temporal evolution.
• Score: 47.82639003096941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is proposed, which benefits from the positive correlation in the class labels and in their temporal evolution and is designed to be applicable to any dynamical graph with a community structure. Under the dynamical degree-corrected stochastic block model, in the case of two classes of equal size, we demonstrate and support with extensive simulations that our proposed algorithm is capable of making non-trivial community reconstruction as soon as theoretically possible, thereby reaching the optimal detectability threshold and provably outperforming competing spectral methods.

Related papers

• MNTD: An Efficient Dynamic Community Detector Based on Nonnegative Tensor Decomposition [3.714657619100999]
  This paper proposes a Modularity-ind Nonnegative RESCAL Decomposition (MNTD) model for dynamic community detection. The MNTD is superior to state-of-the-art dynamic community detection methods in the accuracy of community detection.
  arXiv  Detail & Related papers  (2024-07-26T16:17:53Z)
• Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian [0.8643517734716606]
  We generalize existing spectral algorithms to identify and analyze communities in time-varying graph structures. We show that thetemporal-directed graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected clusters.
  arXiv  Detail & Related papers  (2024-07-12T14:31:54Z)
• Simultaneous Identification of Sparse Structures and Communities in Heterogeneous Graphical Models [8.54401530955314]
  We introduce a novel decomposition of the underlying graphical structure into a sparse part and low-rank diagonal blocks. We propose a three-stage estimation procedure with a fast and efficient algorithm for the identification of the sparse structure and communities.
  arXiv  Detail & Related papers  (2024-05-16T06:38:28Z)
• Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis [2.615648035076649]
  We propose a novel deep graph clustering framework with temporal consistency regularization on inter-community structures. MFC is a matrix factorization-based deep graph clustering algorithm that preserves node embedding. TopoReg is introduced to ensure the preservation of topological similarity between inter-community structures over time intervals.
  arXiv  Detail & Related papers  (2024-01-06T11:29:19Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• 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)
• Amortized Probabilistic Detection of Communities in Graphs [39.56798207634738]
  We propose a simple framework for amortized community detection. We combine the expressive power of GNNs with recent methods for amortized clustering. We evaluate several models from our framework on synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-10-29T16:18:48Z)
• A unified framework for spectral clustering in sparse graphs [47.82639003096941]
  We show that a conveniently parametrized form of regularized Laplacian matrix can be used to perform spectral clustering in sparse networks. We also exhibit important connections between this proposed matrix and the now popular non-backtracking matrix, the Bethe-Hessian matrix.
  arXiv  Detail & Related papers  (2020-03-20T10:58:37Z)

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.