November 9, 2023
Triadic closure, the formation of a connection between two nodes in a network sharing a common neighbor, is considered a fundamental mechanism determining the clustered nature of many real-world topologies. In this work we define a static triadic closure (STC) model for clustered networks, whereby starting from an arbitrary fixed backbone network, each triad is closed independently with a given probability. Assuming a locally treelike backbone we derive exact expressions for the expected number of various small, loopy motifs (triangles, four-loops, diamonds and four-cliques) as a function of moments of the backbone degree distribution. In this way we determine how transitivity and its suitably defined generalizations for higher-order motifs depend on the heterogeneity of the original network, revealing the existence of transitions due to the interplay between topologically inequivalent triads in the network. Furthermore, under reasonable assumptions for the moments of the backbone network, we establish approximate relationships between motif densities, which we test in a large dataset of real-world networks. We find a good agreement, indicating that STC is a realistic mechanism for the generation of clustered networks, while remaining simple enough to be amenable to analytical treatment.
Similar papers 1
April 10, 2013
Conventionally, pairwise relationships between nodes are considered to be the fundamental building blocks of complex networks. However, over the last decade the overabundance of certain sub-network patterns, so called motifs, has attracted high attention. It has been hypothesized, these motifs, instead of links, serve as the building blocks of network structures. Although the relation between a network's topology and the general properties of the system, such as its functio...
September 27, 2017
A wide variety of complex networks (social, biological, information etc.) exhibit local clustering with substantial variation in the clustering coefficient (the probability of neighbors being connected). Existing models of large graphs capture power law degree distributions (Barab\'asi-Albert) and small-world properties (Watts-Strogatz), but only limited clustering behavior. We introduce a generalization of the classical Erd\H{o}s-R\'enyi model of random graphs which provably...
March 24, 2009
We offer a solution to a long-standing problem in the physics of networks, the creation of a plausible, solvable model of a network that displays clustering or transitivity -- the propensity for two neighbors of a network node also to be neighbors of one another. We show how standard random graph models can be generalized to incorporate clustering and give exact solutions for various properties of the resulting networks, including sizes of network components, size of the gian...
October 10, 2003
This paper is a step towards a systematic theory of the transitivity (clustering) phenomenon in random networks. A static framework is used, with adjacency matrix playing the role of the dynamical variable. Hence, our model is a matrix model, where matrices are random, but their elements take values 0 and 1 only. Confusion present in some papers where earlier attempts to incorporate transitivity in a similar framework have been made is hopefully dissipated. Inspired by more c...
May 17, 2004
We present an algorithm for generating random networks with arbitrary degree distribution and Clustering (frequency of triadic closure). We use this algorithm to generate networks with exponential, power law, and poisson degree distributions with variable levels of clustering. Such networks may be used as models of social networks and as a testable null hypothesis about network structure. Finally, we explore the effects of clustering on the point of the phase transition where...
May 13, 2016
A determinant property of the structure of a biological network is the distribution of local connectivity patterns, i.e., network motifs. In this work, a method for creating directed, unweighted networks while promoting a certain combination of motifs is presented. This motif-based network algorithm starts with an empty graph and randomly connects the nodes by advancing or discouraging the formation of chosen motifs. The in- or out-degree distribution of the generated network...
November 4, 2014
An important source of high clustering coefficient in real-world networks is transitivity. However, existing approaches for modeling transitivity suffer from at least one of the following problems: i) they produce graphs from a specific class like bipartite graphs, ii) they do not give an analytical argument for the high clustering coefficient of the model, and iii) their clustering coefficient is still significantly lower than real-world networks. In this paper, we propose a...
August 8, 2009
Network motifs are small building blocks of complex networks. Statistically significant motifs often perform network-specific functions. However, the precise nature of the connection between motifs and the global structure and function of networks remains elusive. Here we show that the global structure of some real networks is statistically determined by the probability of connections within motifs of size at most 3, once this probability accounts for node degrees. The connec...
August 15, 2006
We develop a full theoretical approach to clustering in complex networks. A key concept is introduced, the edge multiplicity, that measures the number of triangles passing through an edge. This quantity extends the clustering coefficient in that it involves the properties of two --and not just one-- vertices. The formalism is completed with the definition of a three-vertex correlation function, which is the fundamental quantity describing the properties of clustered networks....
January 12, 2011
One of the main characteristics of real-world networks is their large clustering. Clustering is one aspect of a more general but much less studied structural organization of networks, i.e. edge multiplicity, defined as the number of triangles in which edges, rather than vertices, participate. Here we show that the multiplicity distribution of real networks is in many cases scale-free, and in general very broad. Thus, besides the fact that in real networks the number of edges ...