Generation of arbitrarily two-point-correlated random networks

Sebastian Weber and Markus Porto

Phys. Rev. E 76, 046111 – Published 18 October 2007

Abstract

Random networks are intensively used as null models to investigate properties of complex networks. We describe an efficient and accurate algorithm to generate arbitrarily two-point degree-degree correlated undirected random networks without self-edges or multiple edges among vertices. With the goal to systematically investigate the influence of two-point correlations, we furthermore develop a formalism to construct a joint degree distribution $P (j, k)$ , which allows one to fix an arbitrary degree distribution $P (k)$ and an arbitrary average nearest neighbor function $k_{nn} (k)$ simultaneously. Using the presented algorithm, this formalism is demonstrated with scale-free networks $[P (k) \propto k^{- γ}]$ and empirical complex networks [ $P (k)$ taken from network] as examples. Finally, we generalize our algorithm to annealed networks which allows networks to be represented in a mean-field-like manner.

Received 14 February 2007

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

Authors & Affiliations

Sebastian Weber and Markus Porto

Institut für Festkörperphysik, Technische Universität Darmstadt, Hochschulstrasse 8, 64289 Darmstadt, Germany

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 76, Iss. 4 — October 2007

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
(Color online) Density plot of the correlation function $f_{ref} (j, k)$ of the empirical network versus the correlation function $f (j, k)$ of the corresponding random network as generated by the algorithm for all indices $j$ and $k$ . Darker red regions contain a higher density of data points, while lighter red indicates a lower density. The reference line $y = x$ is drawn as a guide to the eye.Reuse & Permissions
Figure 2
(Color online) Degree distribution $P (k)$ of empirical networks and their corresponding degree distribution as generated by the algorithm. The red squares denote the reference points as measured from the empirical networks and the black circles mark values measured from the randomized networks.Reuse & Permissions
Figure 3
(Color online) Data collapse for average nearest neighbor function $k_{nn} (k) \propto k^{α}$ with various values of the power parameter $α$ for networks with a scale-free degree distribution with varying values of the scale parameter $γ$ . The symbols used for the different values for the scale parameter $α$ are blue circle, $- 0.2$ ; pink square, $- 0.1$ ; dark green up triangle, 0.0; red diamond, 0.1; yellow down triangle, 0.2; and light green star, 0.3.Reuse & Permissions
Figure 4
(Color online) Newman factor $r$ as a function of the scale parameter $α$ for different values of the scale parameter $γ$ . The straight line denotes the theoretic values of the Newman factor $r$ as of Eq. (16). The symbols denote the value of the scale parameter $γ$ : blue circle, 2.0; pink square, 2.4; dark green triangle, 2.8; and red diamond, 3.2.Reuse & Permissions
Figure 5
(Color online) Network size dependence of the Newman factor $r$ as a function of the exponent $α$ for different values of the scale parameter $γ$ . The network size $N$ is marked by the symbols: blue circle, $10^{4}$ ; pink square, $10^{5}$ ; and dark green triangle, $10^{6}$ .Reuse & Permissions
Figure 6
(Color online) Data collapse for average nearest neighbor function $k_{nn} (k)$ for the three empirical networks actor, WWW, and yeast protein-interaction network. The left column (a), (b), and (c) show the data collapse for networks generated by the algorithm, while the right column (d), (e), and (f) show the same data collapse for networks simulated in an annealed manner. The statistics for each curve is $10^{2}$ , $10^{3}$ , and $10^{4}$ realizations, respectively. The different symbols indicate different values for the exponent $α$ : blue circle, $- 0.2$ ; pink square, $- 0.1$ ; dark green up triangle, 0.0; red diamond, 0.1; and yellow down triangle, 0.2.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics