EC-SBM Synthetic Network Generator

The-Anh Vu-Le, Lahari Anne, George Chacko, Tandy Warnow · 2025

Read EC-SBM Synthetic Network Generator by The-Anh Vu-Le, Lahari Anne, George Chacko, Tandy Warnow (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-03662.txt.

Introduction

The-Anh Vu-Le and co-authors present a generator for fake networks with realistic group structure, in this 2025 paper. Such fakes are needed to test tools that find communities in networks. Their generator takes a real grouped network and builds a twin that matches it on network and group measures.

The key aim is to copy how densely each group links inside itself. Tests on large real networks showed high accuracy on both kinds of measures, beating current rivals in most cases. The tool is also fast enough for networks with millions of nodes. The authors offer it as a benchmark base for community-finding research.

Catalog record

CREATORThe-Anh Vu-Le, Lahari Anne, George Chacko, Tandy Warnow
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-03662

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

EC-SBM Synthetic Network Generator The-Anh Vu-Le, Lahari Anne, George Chacko, Tandy Warnow Abstract Generating high-quality synthetic networks with realistic community structure is vital to effectively evaluate community detection algorithms. In this study, we propose a new synthetic network generator called the Edge-Connected Stochastic Block Model (EC-SBM). The goal of EC-SBM is to take a given clustered real-world network and produce a synthetic network that resembles the clustered real-world network with respect to both network and community-specific criteria. In particular, we focus on simulating the internal edge connectivity of the clusters in the reference clustered network. Our extensive performance study on large real-world networks shows that EC-SBM has high accuracy in both network and community-specific criteria, and is generally more accurate than current alternative approaches for this problem. Furthermore, EC-SBM is fast enough to scale to real-world networks with millions of nodes. keywords synthetic network generation, community detection, network science 1 Introduction Models for synthetic network generation are in wide use, with applications that vary from proposing null models Erdös and Rényi (1959) ; Chung and Lu (2006) ; Newman and Girvan (2004) ; Fosdick et al. (2018) to evaluating graph analysis techniques such as community detection Lancichinetti et al. (2008) ; Danon et al. (2005) ; Orman et al. (2011) ; Orman et al. (2012) ; Orman et al. (2013) ; Hric et al. (2014) ; Yang et al. (2016) ; Kamiński et al. (2021) ; Kamiński et al. (2023) or community structure testing Lancichinetti et al. (2010) ; Bickel and Sarkar (2015) ; Miasnikof et al. (2020) ; Miasnikof et al. (2023) ; Yanchenko and Sengupta (2024) ; He et al. (2025) . Several of the early approaches do not incorporate community structure into the generated network. The Erdős–Rényi model Erdös and Rényi (1959) connects nodes in an independently and identically distributed manner. The Barabási–Albert model Albert and Barabási (2002) captures the power-law degree distribution often observed in real-world networks. The Chung-Lu model Chung and Lu (2006) and the configuration model Bollobás (1980) ; Fosdick et al. (2018) enforce specific degree distribution, either in expectation or in reality. These models are usually simple and only focus on a specific property; however, they provide the foundation for much future research. Later models have incorporated community structure, including Stochastic Block Models (SBMs) Holland et al. (1983) ; Peixoto (2019) , the Lancichinetti–Fortunato–Radicchi (LFR) benchmark Lancichinetti et al. (2008) , Artificial Benchmark for Community Detection (ABCD) Kamiński et al. (2021) , and the extension of ABCD called ABCD+o to handle outliers Kamiński et al. (2023) , i.e., nodes that are not in any cluster. The nonuniform Popularity-Similarity Optimization (nPSO) Muscoloni and Cannistraci (2018) model incorporates parameters not directly estimated from the reference graph but indirectly influencing other network and cluster properties of interest. Many of these approaches can take as input various parameters for a clustered network, such as the degree sequence, the number of edges and vertices in each cluster, the mixing parameter, etc. Furthermore, SBMs can take as input the assignment of nodes to clusters. More recently, over-parameterized models have emerged, such as the exponential family random graph models (ERGM) Frank and Strauss (1986) ; Holland and Leinhardt (1981) , GraphRNN You et al. (2018) , and other deep graph generative models Zhu et al. (2022) ; Guo and Zhao (2023) . These models utilize parameters that are not directly tied to graph properties, like degree or edge counts, but serve as coefficients in complex models. Moreover, these parameters can be “learned” from a set of reference networks. While these approaches can capture more intricate network properties, including communities, they face challenges in scalability and scarcity of large-network data, limiting their applicability to smaller graphs. For example, the study done by Jang et al. (2024) showed GraphRNN and other deep generative techniques do not scale to networks with 5000 nodes where they ran into out-of-memory errors. Here we ask how well a given network generator is able to produce synthetic networks that resemble a given real-world network. This question was partially addressed by Vaca-Ramirez and Peixoto Vaca-Ramírez and Peixoto (2022) , who examined the graph-tool software Peixoto (2014) for generating SBMs with respect to its accuracy in reproducing network features. . Vaca-Ramirez and Peixoto Vaca-Ramírez and Peixoto (2022) took a large number of real-world networks, computed a clustering of the network by finding a best-fitting SBM for the network, and then used that SBM to generate synthetic networks. That study then established that their SBM software produced synthetic networks that came closer to the real-world network in terms of various properties, such as degree sequence, diameter, local and global clustering coefficients, etc., than a configuration model. Despite that positive result, Vaca-Ramírez and Peixoto (2022) did not examine whether the SBMs produced by graph-tool had ground-truth communities that were similar to the communities in the clustered real-world network. Very recently, Anne et al. Anne et al. (2025) examined the question of how well the clusters produced by graph-tool resembled the clusters in the input clustered network. Their study, which examined a large number of networks clustered using the Leiden software Traag (2019) optimizing either modularity or the Constant Potts model Traag et al. (2019) , established that the SBMs produced by graph-tool often had disconnected ground truth clusters. Anne et al. also presented a new simulator to address this problem, REalistic Cluster Connectivity Simulator (RECCS). Given the parameters from a clustered real-world network, RECCS creates an initial SBM using graph-tool and then modifies it to come close to the parameters in the input. As shown in Anne et al. (2025) , RECCS produces synthetic networks and ground truth clusterings that have network and cluster properties similar to that of the input clustered real-world network and is especially good with respect to edge-connectivity (i.e., the size of a minimum edge cut) for each cluster. Furthermore, in comparison to SBMs computed using graph-tool , RECCS improves the accuracy for edge-connectivity values and matches the network parameter values. Here, we present a new method, Edge-Connected SBM (EC-SBM), for generating synthetic networks that aims to achieve even higher fidelity than RECCS. The design of EC-SBM has a different structure than RECCS in two major ways: while RECCS begins by creating an SBM synthetic network and then modifying it, EC-SBM begins by establishing some of the edges for the clusters that suffice to guarantee achieving edge connectivity that is at least that in the input parameters. Then EC-SBM uses graph-tool SBM construction to augment the edge set and afterward further modifies the network to improve the fit to the input values. Our study, using a large corpus of real-world networks, also examines the question of which clusterings of real-world networks produce the closest fit to the real-world network. We find distinct differences in final synthetic network quality (as measured using the fit between the synthetic network and the given real-world network) between clustering methods, with two specific clustering methods providing the best fit. Thus, in this paper, we provide some advances in the development of protocols and software to produce realistic synthetic networks that resemble given real-world networks. The rest of the paper is organized as follows. In Section 2 , we begin with our preliminary

Read the complete text