Technical Comments

Comment on “Control profiles of complex networks”

See allHide authors and affiliations

Science  31 Oct 2014:
Vol. 346, Issue 6209, pp. 561
DOI: 10.1126/science.1256492

Abstract

Ruths and Ruths (Reports, 21 March 2014, p. 1373) find that existing synthetic random network models fail to generate control profiles that match those found in real network models. Here, we show that a straightforward extension to the Barabási-Albert model allows the control profile to be “tuned” across the control profile space, permitting more meaningful control profile analyses of real networks.

Ruths and Ruths (1) present a statistic for characterizing the control nodes within a network. The measures Embedded Image, Embedded Image, and Embedded Image are respectively defined as the fraction of a network’s control nodes that arise from source nodes, external dilations, and internal dilations.. The authors show that several existing synthetic networks are dominated by Embedded Image (i.e., Embedded Image).

Here, we show that with the addition of a single parameter, the Barabási-Albert (BA) model (2) may be modified to be dominated by any of the three types of control nodes introduced in (1). We first note that the BA model in its original form generates an undirected network. As such, two considerations are raised when modifying the BA model to generate directed networks. First, the preferential node selection may be based on total node degree, in-degree, or out-degree. Second, new edges may be directed either to or away from new nodes as they are added to the network. We consider here preferential attachment based on total node degree, which reduces to the undirected BA model when disregarding edge directionality; i.e., it generates networks with total node degree distributions that obey power laws.

The second consideration—that is, the choice of edge directionality—may be used to “tune” the control profile of the generated networks to be dominated by any of Embedded Image, Embedded Image, and Embedded Image, as seen in real networks. Consider a time step in the BA model where an existing node x has been preferentially selected based on its total degree and is being connected to a new node y. We introduce the parameter p such that the directed edge x y is assigned with probability p; directed edge yx is thus assigned with probability (1 – p). This modified BA model is therefore defined by three parameters: n, the number of nodes in the network; m, the number of edges to be connected to each new node; and p, the probability of new edges running out from the existing network to new nodes as the network is built.

Because the lowest-degree nodes are the most abundant in BA networks, the extremal values of p = 0 and p = 1 result in networks that are characterized by many source nodes (Embedded Image domination) and many sink nodes (Embedded Image domination), respectively. A moderate value of p reduces the uneven distribution between source nodes and sink nodes and introduces a heterogeneous flow structure to the networks, which results in the emergence of internal dilations (Embedded Image domination).

We show the distribution of Embedded Image, Embedded Image, and Embedded Image as a function of p for n = 1000, m = 3 in Fig. 1, and project the same data to a ternary plot, in the style of figure 3 from (1), in Fig. 2. Notably, the ternary plot of Fig. 2 shows that the control profile “travels,” as a function of p, across the perimeter of the control profile space, suggesting that mixed control profiles constitute a forbidden region (1) of the state space for this model. This matches well with the control profiles of the real networks reported in (1), although the persistence of some number of source and sink control nodes prevents the model from generating networks with Embedded Image. We note, however, that a post hoc mechanism that eliminates all source and sink nodes (e.g., by adding edges x → source and sink x for preferentially selected nodes x) successfully moves the control profile to Embedded Image while maintaining a degree distribution that approximately obeys a power law.

Fig. 1 The abundance of Embedded Image(black squares),Embedded Image (red squares), and Embedded Image(green squares) in the modified Barabási-Albert model.

The figure shows 1000 networks with n = 1000, m = 3, and p randomly sampled from the interval [0,1]. Colorized curves represent fits to the data.

Fig. 2 The data of Fig. 1 projected onto a ternary plot.

Coloring corresponds to the largest value ofEmbedded Image(black, Embedded Image; green, Embedded Image; red, Embedded Image). As p increases from 0 to 1, the networks move clockwise across the control profile space, fromEmbedded ImagetoEmbedded ImagetoEmbedded Image.

Random network models offer insight into the mechanisms by which real networks form. In (1), the authors show that the control profile of real networks differs from existing models of random networks. In this Comment, we have shown that controlling the directionality and heterogeneity of a random network’s edges can substantially affect the network control profile. These findings have implications for the development of new and modified network models that will greatly improve our ability to understand, control, defend, and protect a wide range of real networks.

References and Notes

  1. Acknowledgments: This work was supported by NSF grant DMS-1313115.
View Abstract

Navigate This Article