Clustering without geometry in sparse networks with independent edges

Alessio Catanzaro 1,2,3, Remco van der Hofstad 4, Diego Garlaschelli 1,2 · 2026

Read Clustering without geometry in sparse networks with independent edges by Alessio Catanzaro 1,2,3, Remco van der Hofstad 4, Diego Garlaschelli 1,2 (2026) 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-2603-13159.txt.

Introduction

Alessio Catanzaro and co-authors prove that sparse random graphs with independent edges can cluster, with no geometry at all. Real networks are both sparse and rich in triangles, a pairing once thought to need latent distances. Their model, invariant under node aggregation, yields finite clustering by proof and by numerics. What drives it is a node fitness with infinite mean, which also gives a power-law degree spread. Self-averaging of network traits also breaks down in this model, a new effect they pin down.

Catalog record

CREATORAlessio Catanzaro 1,2,3, Remco van der Hofstad 4, Diego Garlaschelli 1,2
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62943
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13159

Browse the full library · About the Tower of Babel

Full text

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

Clustering without geometry in sparse networks with independent edges Alessio Catanzaro 1,2,3, Remco van der Hofstad 4, Diego Garlaschelli 1,2 Abstract The coexistence of sparsity and clustering (non-vanishing average fraction of triangles per node) is one of the few structural features that, irrespective of finer details, are ubiquitously observed across large real-world networks. This fact calls for generic models producing sparse clustered graphs. Earlier results suggested that sparse random graphs with independent edges fail to reproduce clustering, unless edge probabilities are assumed to depend on underlying metric distances that, thanks to the triangle inequality, naturally favour triadic closure. This observation has opened a debate on whether clustering implies (latent) geometry in real-world networks. Alternatively, recent models of higher-order networks can replicate clustering by abandoning edge independence. In this paper, we mathematically prove, and numerically confirm, that a sparse random graph with independent edges, recently identified in the context of network renormalization as an invariant model under node aggregation, produces finite clustering without any geometric or higher-order constraint. The underlying mechanism is an infinite-mean node fitness, which also implies a power-law degree distribution. Further, as a novel phenomenon that we characterize rigorously, we observe the breakdown of self-averaging of various network properties. Therefore, as an alternative to geometry or higher-order dependencies, node aggregation invariance emerges as a basic route to realistic network properties. Introduction: clustering versus geometry. While real-world networks differ in various structural details, the vast majority of them are characterized by virtually ubiquitous features, the most popular of which are the broad (i.e., infinite-variance) distribution of node degrees (numbers of links per node), the (ultra)small-world property (i.e., average shortest path length growing (at most) logarithmically with the number of nodes), and the coexistence of sparsity (i.e., vanishing link density) and local clustering (i.e., finite average density of triangles around nodes) in the limit of infinitely large networks 16 ; 31 . While several models based on different generic mechanisms can successfully replicate broad degree distributions and short path lengths 31 ; 41 , the coexistence of sparsity and local clustering is much more difficult to replicate – and hence more informative, as it requires specific mechanisms that can discriminate models at a finer level. The prototypical example of this difficulty is illustrated by random graph models with independent edges , where different pairs of nodes are independently connected. In the Erdős-Rényi (ER) model 19 , where edges are independent and identically distributed (i.i.d.) with the same connection probability p , it is easy to show that the link density (expected fraction of realized links) and the local clustering coefficient (defined as the fraction of triangles around a node, averaged over all nodes) have the same expected value p for networks with a large number n of nodes. This automatically implies that, as n diverges, one cannot simultaneously produce finite local clustering and vanishing link density. To overcome this limitation of the ER model, two main routes have been explored. One route introduces dependencies between edges. This can happen via the addition of explicit triadic interactions in an Exponential Random Graph setting 29 ; 30 (which may however still lead to comparable levels of density and clustering), the random superposition of small subgraphs 14 or the monopartite projection 1 1 1 In monopartite projections of bipartite networks, the original nodes are first initially connected (possibly independently of each other) to ‘auxiliary’ nodes of a different type (representing for instance the possibile affiliations or memberships of the original nodes), and the auxiliary nodes are then eliminated while connecting the original nodes to each other, if they share connections to the same auxiliary nodes. of random bipartite networks 28 – both producing networks of overlapping cliques (the edges of which are all mutually dependent) where local clustering can remain very large even for vanishing density. More recent attempts generalize these ideas to higher-order networks such as simplicial complexes and hypergraphs 6 ; 8 , where edges belonging to the same simplex or hyperedge are mutually dependent. While these more complicated settings can realize the coexistence of sparsity and clustering at the expense of introducing higher-order dependencies, whether that coexistence can be achieved for more parsimonious models with independent edges remains an open question. The second route explores that question explicitly by preserving edge independence while introducing heterogeneity. More precisely, one can turn the unconditional link independence of the ER model into a conditional one, by replacing, for each specific pair of nodes i and j ( i,j=1,\dots,n ), the constant connection probability p with a probability p_{ij} that is a function f(w_{i},w_{j}) of the realized values w_{i} , w_{j} of a certain node-specific variable w (called fitness or weight, hidden variable, latent variable, Lagrange multiplier, etc.) that is preliminarily assigned to vertices via an i.i.d. draw from a certain probability density function (pdf) \rho(w) 15 ; 41 ; 12 ; 38 . Typical choices of f(w_{i},w_{j}) are monotonically increasing in both arguments (and necessarily symmetric for undirected graphs) -- implementing the idea that, the larger the fitness, the larger the probability that a node connects to other nodes 2 2 2 Some popular examples are f(w_{i},w_{j})=zw_{i}w_{j} , f(w_{i},w_{j})=\Theta(w_{i}+w_{j}-z) , f(w_{i},w_{j})=zw_{i}w_{j}/(1+zw_{i}w_{j}) , and f(w_{i},w_{j})=1-\mathrm{e}^{-zw_{i}w_{j}} , where z>0 is a global parameter controlling for the overall link density and w_{i}\geq 0 \forall i . . In the studies carried out so far, it turned out that, while several combinations of f and \rho can generate sparse small-world networks with a broad degree distribution 15 ; 41 ; 12 ; 38 , they systematically fail to generate (positive) clustering, casting doubts on whether models with independent edges can replicate local clustering. The only exception that has become popular is that of random geometric graphs , where the fitness w acquires the role of a node coordinate (which, more generally, can be a D -dimensional vector), and the connection function f depends on w_{i} and w_{j} through some metric distance d_{ij}=d(w_{i},w_{j}) (in which case, f generally loses the property of being monotonic in w_{i} 3 3 3 For instance, if w_{i} and w_{j} are scalar (one-dimensional) coordinates and their distance is defined as d_{ij}=|w_{i}-w_{j}| , then w_{i} and w_{j} can simultaneously increase while keeping d_{ij} (and hence p_{ij} ) unchanged. ). A remarkable example of this success is the hyperbolic model 24 ; 1 ; 36 ; 37 ; 9 ; 30 ; 23 ; 27 , which assumes that nodes are sprinkled uniformly at random in a D -dimensional hyperbolic space and links are formed with a probability that is a certain decreasing function of the geodesic distance between nodes. In this setting, the triangle inequality ( d_{ij}\leq d_{ik}+d_{jk} \forall i,j,k ) guarantees that pairs of nodes i,j that successfully connect to a third node k are very likely to connect to each other ( triadic closure ), provably leading to positive clustering 2 ; 17 . Additionally, hyperbolicity ensures that other desirable properties such as power-law degree distributions emerge 23 . These investigations have convincingly concluded that, in random graphs with conditionally independent edges and distance-dependent connection probabilities, geometry implies clustering . On the other hand, the potential reverse (non-obvious) implication that clustering implies geometry , i.e., that the presence of finite clustering could

Read the complete text