Clustering in complex networks. I. General formalism

M. Ángeles Serrano and Marián Boguñá

Phys. Rev. E 74, 056114 – Published 28 November 2006

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 different metrics that are able to thoroughly characterize transitive relations. A rigorous analysis of several real networks, which makes use of this formalism and the metrics, is also provided. It is also found that clustered networks can be classified into two main groups: the weak and the 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.

Received 15 August 2006

DOI:https://doi.org/10.1103/PhysRevE.74.056114

Authors & Affiliations

M. Ángeles Serrano¹ and Marián Boguñá²

¹School of Informatics, Indiana University, Eigenmann Hall, 1900 East Tenth Street, Bloomington, Indiana 47406, USA
²Departament de Física Fonamental, Universitat de Barcelona, Martí i Franquès 1, 08028 Barcelona, Spain

Clustering in complex networks. II. Percolation properties

M. Ángeles Serrano and Marián Boguñá

Phys. Rev. E 74, 056115 (2006)

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 74, Iss. 5 — November 2006

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
(Color online) This figure illustrates the different information encoded in the functions $P (k, k^{'})$ and $Q (k, k^{'})$ . In this simple graph, there are two kind of vertices, two of them with degree $k = 2$ and the other two of degree $k = 3$ . Each edge is labeled with its multiplicity. The function $(2 - δ_{k, k^{'}}) P (k, k^{'})$ tells us which is the probability that a randomly chosen edge connects two vertices of degrees $k$ and $k^{'}$ , respectively. Then, the probability that a randomly chosen edge connects two vertices of degrees $k = 2$ and $k = 3$ is $4 ∕ 5$ and the probability of connecting two vertices of degree $k = 3$ is $1 ∕ 5$ . In the case of $Q (k, k^{'})$ , we first have to chose randomly a triangle—either triangle labeled 1 or 2 in this example—and from this triangle one of its edges is randomly chosen. Using this procedure, the probability that an edge connects two vertices of degrees $k = 2$ and $k = 3$ is $2 ∕ 3$ that corresponds to first chose one triangle—with probability $1 ∕ 2$ each in this particular graph—and then one edge—with probability $1 ∕ 3$ . Analogously, the probability of connecting two vertices of degree $k = 3$ is $1 ∕ 3$ . Then we can write that $P (2, 3) = P (3, 2) = 2 ∕ 5$ , $P (3, 3) = 1 ∕ 5$ and $Q (2, 3) = Q (3, 2) = 2 ∕ 6$ , $Q (3, 3) = 2 ∕ 6$ .Reuse & Permissions
Figure 2
(Color online) Empirical measures of the average nearest neighbors multiplicity as a function of $k$ compared with the average nearest neighbors degree.Reuse & Permissions
Figure 3
(Color online) Sketch of the maximum possible value of the edge multiplicity in a case where the two vertices do not have neighbors of degree 1 (top) and where one of them has one of these neighbors (bottom). In the top plot, the blue vertices (large circles) have degrees $k = 3$ and $k = 5$ respectively and no neighbors of degree 1. Then, the maximum value of $m$ for the edge connecting these two vertices is $m_{3, 5}^{c} = \min (3 - 1, 5 - 1) = 2$ . In the bottom plot, the vertex of degree $k = 3$ has a neighbor of degree 1. In this case, the maximum multiplicity for that edge is $m_{3, 5}^{c} = \min (3 - 1 - 1, 5 - 1) = 1$ .Reuse & Permissions
Figure 4
(Color online) Clustering $\bar{c} (k)$ vs the maximum value $λ (k)$ for several real networks. In all cases, empirical measures fall below the diagonal line, validating the inequality Eq. (18).Reuse & Permissions
Figure 5
(Color online) Empirical measures of the ratio between the clustering coefficient $\bar{c} (k)$ and the maximum value $λ (k)$ for different real networks.Reuse & Permissions
Figure 6
Gray-scale contour plots of the edge clustering coefficient $\bar{c} (k, k^{'})$ as a function of $k$ and $k^{'}$ for the different real networks analyzed.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics