Self-similarity of Communities of the ABCD Model
- URL: http://arxiv.org/abs/2312.00238v1
- Date: Thu, 30 Nov 2023 22:52:39 GMT
- Title: Self-similarity of Communities of the ABCD Model
- Authors: Jordan Barrett, Bogumil Kaminski, Pawel Pralat, Francois Theberge
- Abstract summary: The Artificial Benchmark for Community Detection (ABCD) graph is a random graph model with community structure and power-law distribution for both degrees and community sizes.
We show that the ABCD model exhibits some interesting self-similar behaviour.
- Score: 0.5461938536945723
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Artificial Benchmark for Community Detection (ABCD) graph is a random
graph model with community structure and power-law distribution for both
degrees and community sizes. The model generates graphs similar to the
well-known LFR model but it is faster and can be investigated analytically.
In this paper, we show that the ABCD model exhibits some interesting
self-similar behaviour, namely, the degree distribution of ground-truth
communities is asymptotically the same as the degree distribution of the whole
graph (appropriately normalized based on their sizes). As a result, we can not
only estimate the number of edges induced by each community but also the number
of self-loops and multi-edges generated during the process. Understanding these
quantities is important as (a) rewiring self-loops and multi-edges to keep the
graph simple is an expensive part of the algorithm, and (b) every rewiring
causes the underlying configuration models to deviate slightly from uniform
simple graphs on their corresponding degree sequences.
Related papers
- IFH: a Diffusion Framework for Flexible Design of Graph Generative Models [53.219279193440734]
Graph generative models can be classified into two prominent families: one-shot models, which generate a graph in one go, and sequential models, which generate a graph by successive additions of nodes and edges.
This paper proposes a graph generative model, called Insert-Fill-Halt (IFH), that supports the specification of a sequentiality degree.
arXiv Detail & Related papers (2024-08-23T16:24:40Z) - Advancing Graph Generation through Beta Diffusion [49.49740940068255]
Graph Beta Diffusion (GBD) is a generative model specifically designed to handle the diverse nature of graph data.
We propose a modulation technique that enhances the realism of generated graphs by stabilizing critical graph topology.
arXiv Detail & Related papers (2024-06-13T17:42:57Z) - Graph Out-of-Distribution Generalization with Controllable Data
Augmentation [51.17476258673232]
Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties.
Due to the selection bias of training and testing data, distribution deviation is widespread.
We propose OOD calibration to measure the distribution deviation of virtual samples.
arXiv Detail & Related papers (2023-08-16T13:10:27Z) - Hypergraph Artificial Benchmark for Community Detection (h-ABCD) [5.8010446129208155]
h-ABCD produces random hypergraphs with distributions of ground-truth community sizes and degrees following power-law.
As in the original ABCD, the new model h-ABCD can produce hypergraphs with various levels of noise.
arXiv Detail & Related papers (2022-10-26T20:06:56Z) - Modularity of the ABCD Random Graph Model with Community Structure [2.580765958706854]
The ABCD graph is a random graph model with community structure and power-law distribution for both degrees and community sizes.
We analyze the modularity function, arguably the most important graph property of networks in the context of community detection.
It is also used as a quality function in many community detection algorithms, including the widely used Louvain algorithm.
arXiv Detail & Related papers (2022-03-03T01:49:46Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
We propose a novel score-based generative model for graphs with a continuous-time framework.
We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
arXiv Detail & Related papers (2022-02-05T08:21:04Z) - Generalization of graph network inferences in higher-order graphical
models [5.33024001730262]
Probabilistic graphical models provide a powerful tool to describe complex statistical structure.
inferences such as marginalization are intractable for general graphs.
We define the Recurrent Factor Graph Neural Network (RF-GNN) to achieve fast approximate inference on graphical models that involve many-variable interactions.
arXiv Detail & Related papers (2021-07-12T20:51:27Z) - Generating the Graph Gestalt: Kernel-Regularized Graph Representation
Learning [47.506013386710954]
A complete scientific understanding of graph data should address both global and local structure.
We propose a joint model for both as complementary objectives in a graph VAE framework.
Our experiments demonstrate a significant improvement in the realism of the generated graph structures, typically by 1-2 orders of magnitude of graph structure metrics.
arXiv Detail & Related papers (2021-06-29T10:48:28Z) - Auto-decoding Graphs [91.3755431537592]
The generative model is an auto-decoder that learns to synthesize graphs from latent codes.
Graphs are synthesized using self-attention modules that are trained to identify likely connectivity patterns.
arXiv Detail & Related papers (2020-06-04T14:23:01Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z)
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.