A clusterability test for directed graphs

Mario R. Guarracino, Pierre Miasnikof, Alexander Y. Shestopaloff, Houyem Demni, Cristián Bravo, Yuri Lawryshyn · 2025

Read A clusterability test for directed graphs by Mario R. Guarracino, Pierre Miasnikof, Alexander Y. Shestopaloff, Houyem Demni, Cristián Bravo, Yuri Lawryshyn (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-2506-20111.txt.

Introduction

Mario Guarracino and five co-authors extend a clustering test to directed graphs in a 2025 paper. Many networks, from money flows to web links, have one-way edges. Before clustering such a graph, an analyst should ask whether clusters exist at all: if local density is not higher than the graph's overall density, clusters say little about the whole.

Their version of the delta test samples a small share of neighborhoods, which suits huge networks where checking every node is out of reach. Even samples near one percent gave sound calls, and the test held up when its statistical assumptions bent. The paper also studies how large the sample should be, giving users a practical rule.

Catalog record

CREATORMario R. Guarracino, Pierre Miasnikof, Alexander Y. Shestopaloff, Houyem Demni, Cristián Bravo, Yuri Lawryshyn
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-20111

Browse the full library · About the Tower of Babel

Full text

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

A clusterability test for directed graphs Mario R. Guarracino, Pierre Miasnikof, Alexander Y. Shestopaloff, Houyem Demni, Cristián Bravo, Yuri Lawryshyn Abstract In this article, we extend a statistical test of graph clusterability, the δ \delta test, to directed graphs with no self loops. The δ \delta test, originally designed for undirected graphs, is based on the premise that graphs with a clustered structure display a mean local density that is statistically higher than the graph’s global density. We posit that graphs that do not meet this necessary (but not sufficient) condition for clusterability can be considered unsuited to clustering. In such cases, vertex clusters do not offer a meaningful summary of the broader graph. Additionally in this study, we aim to determine the optimal sample size (number of neighborhoods). Our test, designed for the analysis of large networks, is based on sampling subsets of neighborhoods/nodes. It is designed for cases where computing the density of every node’s neighborhood is infeasible. Our results show that the δ \delta test performs very well, even with very small samples of neighborhoods ( 1 % 1\% ). It accurately detects unclusterable graphs and is also shown to be robust to departures from the underlying assumptions of the t t test. 1 Introduction In this article, we extend a statistical test for clusterability, the \delta test [ 23 , 24 ] , to unweighted directed graphs with no self loops. The \delta test is based on the observation that clusterable graphs, graphs whose structure can be meaningfully summarized by clusters of vertices, will display high neighborhood-level densities, on average. It is designed to detect heterogeneity in connections, the presence of statistically significant pockets of high density. It can be used to answer two separate but related questions: “does graph G have a high local connectivity pattern” (i.e., meet the necessary condition) and “does graph G_{1} have a higher local connectivity pattern than graph G_{2} ” [ 23 , 24 ] . The \delta test offers two major advantages. First, it uses samples of nodes to answer these two questions, which makes it suitable for the study of large networks. Second, it offers formal statistical answers with significance levels. Graph clustering, also referred to as network community detection, is a pivotal task in the study of networks. In fact, it has even been described as a pivotal question in network analysis [ 32 ] . Clustering algorithms will always group data into clusters, regardless of the data set’s structure. However, such techniques should be used with care. If the data does not have a clustered structure, if it cannot be meaningfully summarized by grouping it into subsets of similar items, the clustering exercise is futile. Not only is it a waste of time, it leads to misleading conclusions. For this reason, clusterability tests play a key role in clustering analyses. They identify data sets (graphs in this specific case) that possess the prerequisite (necessary) conditions for being clusterable. To emphasize this fact, we cite Adolfsson et al. [ 1 ] who stated: “(…) an even more fundamental issue than algorithm selection is when clustering should, or should not, be applied” , in their work on clustering in \mathbb{R}^{n} . Currently, there is no formal generally accepted definition of (vertex) clusters or communities in undirected graphs. However, there is a quasi-universal agreement that clusters are formed by densely connected subsets of nodes that are sparsely connected to the remaining graph (e.g., [ 35 , 9 , 40 , 33 , 10 , 34 , 25 , 26 ] ). The original delta test is based on this quasi-universal agreement [ 23 , 24 ] . In the case of directed graphs, the definition of clusters is even more ambiguous. Many authors analyzing directed graphs simply ignore edge directions (e.g., [ 30 , 9 , 33 , 34 ] ). Case in point, in his seminal article, Fortunato stated “(…) it is customary to neglect the directedness of the hyperlinks and to consider the graph as undirected, for the purpose of community detection” [ 9 ] . However, many authors disagree with this simplistic treatment of directed graphs (e.g., [ 20 , 22 ] ). Nevertheless, the characterization of clusters as densely connected subsets of nodes that are sparsely connected to the remaining graph seems to be accepted even by authors who do not agree with the naïve treatment of directed graphs as undirected ones. For example, Malliaros and Vazirgiannis [ 22 ] began by stating “(…) the most common way to dealing with edge directionality during the clustering task, is simply to ignore it. (…) However, in many cases, this simplistic technique would not be satisfactory (…)” . Nevertheless, these same authors later described clusters as “(…) modules with dense connections between the nodes of the same cluster but sparser connections between different clusters” . The extension of our test to directed graphs is justified by this consensus agreement that clusters are formed by densely connected subsets of nodes that have only sparse connections to the remaining graph. In the case of directed graphs, we again posit that a local density that is, on average, significantly higher than the graph’s global density is a prerequisite condition for the presence of meaningful clusters. On the basis of this postulate, we devise a test that samples local neighborhood densities and compares them statistically to the graph’s overall density. Our test is designed to use only a small subset of all neighborhoods, which makes it very well suited as a first step in the analysis of large networks. It prevents wasted time on and misleading results from clustering graphs that are evidently unsuited for clustering. Moreover, because it only uses a small portion of the graph, it is feasible to apply it to larger data sets. The remainder of this article is organized as follows. After a very brief review of previous work on clusterability testing, we introduce our modification to the \delta test. We then examine the performance of our test on synthetic graphs with known structure and real-world networks as well. We also investigate the statistical power of our test, its sensitivity to sample size. Our results show that the \delta test performs very well. It accurately detects unclusterable graphs and is also shown to be robust to departures from the underlying assumptions of the t test, even with a very small sample of nodes/neighborhoods. 2 Previous work As in earlier work on the \delta test, the extension presented here is heavily inspired by the statistical tests presented by Gao and Lafferty [ 12 , 11 ] , as well as the follow-up work of Gao and Ma [ 13 ] . However, as shown in Miasnikof et al. [ 23 ] , the tests of Gao and Lafferty rely on restrictive assumptions, are not suited for graph comparisons and are unresponsive to graph structure. Indeed, at the core, these tests focus on the presence of very restrictive structures (triangles) as indicators of a clustered structure. Such an approach was deemed too restrictive by Yin et al. [ 41 ] , who highlight the need to examine higher order cliques. Meanwhile, the work of Gao and Ma [

Read the complete text