Clustering in complex networks. I. General formalism

Abstract

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. The formalism suggests new metrics that are able to thoroughly characterize transitive relations. A rigorous analysis of several real networks, which makes use of the new formalism and the new metrics, is also provided. It is also found that clustered networks can be classified into two main groups: the {\it weak} and the {\it strong transitivity} classes. In the first class, edge multiplicity is small, with triangles being disjoint. In the second class, edge multiplicity is high and so triangles share many edges. As we shall see in the following paper, the class a network belongs to has strong implications in its percolation properties.

References in corpus (25)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Lethality and centrality in protein networks
• Random graphs with arbitrary degree distributions and their applications
• Who is the best connected scientist? A study of scientific coauthorship networks
• Defining and identifying communities in networks
• Hierarchical Organization in Complex Networks
• Self-similar community structure in organisations
• Dynamical and correlation properties of the Internet
• Generation of uncorrelated random scale-free networks
• k-core organization of complex networks
• Large-scale topological and dynamical properties of Internet
• Topology of the World Trade Web
• Epidemic spreading in correlated complex networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Class of correlated random networks with hidden variables
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Cut-offs and finite size effects in scale-free networks
• The origin of degree correlations in the Internet and other networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Tuning clustering in random networks with arbitrary degree distributions
• Clustering in complex networks. II. Percolation properties
• Uncorrelated Random Networks
• Perturbing General Uncorrelated Networks

Cited by in corpus (54)

• Critical phenomena in complex networks
• The Kuramoto model in complex networks
• Random graphs with clustering
• Structure and dynamics of core-periphery networks
• Random graphs containing arbitrary distributions of subgraphs
• The unreasonable effectiveness of tree-based theory for networks with clustering
• The robustness of interdependent clustered networks
• Clustering in complex networks. II. Percolation properties
• How clustering affects the bond percolation threshold in complex networks
• Bond percolation on a class of clustered random networks
• Evolving Clustered Random Networks
• Robustness of partially interdependent network formed of clustered networks
• The Organization of Strong Links in Complex Networks
• Deciphering the global organization of clustering in real complex networks
• Persistence in Complex Systems
• Clustering Drives Assortativity and Community Structure in Ensembles of Networks
• Time Evolution of Disease Spread on Networks with Degree Heterogeneity
• Time evolution of epidemic disease on finite and infinite networks
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Trust transitivity in social networks
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Percolation in self-similar networks
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Transport on weighted Networks: when correlations are independent of degree
• Clustering determines the dynamics of complex contagions in multiplex networks
• Detecting the ultra low dimensionality of real networks
• Clustering of random scale-free networks
• Social Bootstrapping: How Pinterest and Last.fm Social Communities Benefit by Borrowing Links from Facebook
• Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
• Evolution of the Internet k-dense structure
• Triangular clustering in document networks
• Bond percolation on a class of correlated and clustered random graphs
• Analytical results for bond percolation and k-core sizes on clustered networks
• Cascades on clique-based graphs
• Generating random networks with given degree-degree correlations and degree-dependent clustering
• Clustering Spectrum of scale-free networks
• Networks with arbitrary edge multiplicities
• Triadic closure in configuration models with unbounded degree fluctuations
• Two-pathogen model with competition on clustered networks
• Cooperative coinfection dynamics on clustered networks
• Exponential rate of epidemic spreading on complex networks
• Protein residue networks from a local search perspective
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Higher-order distributions and nongrowing complex networks without multiple connections
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• Low Cost Carriers induce specific and identifiable delay propagation patterns: an analysis of the EU and US systems
• Random degree-degree correlated networks
• Localized attack on clustering networks
• Structural Properties of Networks Grown via an Achlioptas Process
• Nonrandom behavior in the Projection of Random bipartite networks
• Relaxation dynamics of maximally clustered networks
• A Survey on Role-Oriented Network Embedding
• Transfer and routing of Gaussian states through quantum complex networks with and without community structure
• The short-cut network within protein residue networks