Analysis of relative influence of nodes in directed networks

Many complex networks are described by directed links; in such networks, a link represents, for example, the control of one node over the other node or unidirectional information flows. Some centrality measures are used to determine the relative importance of nodes specifically in directed networks. We analyze such a centrality measure called the influence. The influence represents the importance of nodes in various dynamics such as synchronization, evolutionary dynamics, random walk, and social dynamics. We analytically calculate the influence in various networks, including directed multipartite networks and a directed version of the Watts-Strogatz small-world network. The global properties of networks such as hierarchy and position of shortcuts rather than local properties of the nodes, such as the degree, are shown to be the chief determinants of the influence of nodes in many cases. The developed method is also applicable to the calculation of the PAGERANK. We also numerically show that in a coupled oscillator system, the threshold for entrainment by a pacemaker is low when the pacemaker is placed on influential nodes. For a type of random network, the analytically derived threshold is approximately equal to the inverse of the influence. We numerically show that this relationship also holds true in a random scale-free network and a neural network.

Figure 1

Influence of nodes in networks having $N=20$. A dark node has a large value of $v_i$. (a) Directed network generated by the configuration model. The indegree and outdegree follow independent power-law distributions with the scaling exponent 2.5 and the minimum degree 2. (b) Directed Watts-Strogatz network with three shortcuts. See Secs. 3E, 4 for details of the network models. The networks are visualized by Pajek [12].

Figure 2

Schematic of (a) weighted chain, (b) special case of weighted chain, (c) weighted cycle, and (d) special case of weighted cycle.

Figure 3

Schematic of (a) multipartite network, (b) superstar, and (c) funnel.

Figure 4

Schematic of directionally biased random network under tree approximation.

Figure 5

$v_i$ for a directionally biased random network with $N=5000$. We set [(a) and (b)] $ϵ=0.5$ and [(c) and (d)] $ϵ=0.1$. In (a) and (c), $v_i$ is plotted against the MA results. The lines represent the MA: $v_i=\left(k_i^{\text{out}}/k_i^{\text{in}}\right)/{\sum }_{j=1}^N\left(k_j^{\text{out}}/k_j^{\text{in}}\right)$. In (b) and (d), $v_i$ (circles) and rescaled $k_i^{\text{out}}/k_i^{\text{in}}$ (squares) averaged over all the nodes in each layer are plotted against layer number. The error bars indicate the standard deviation obtained from $v_i$ of all the nodes in the same layer.

Figure 6

Schematics of directed small-world network having (a) one shortcut, [(b)–(d)] two shortcuts, and (e) general number of shortcuts.

Figure 7

$v_i$ in directed small-world networks with $N=5000$. (a) Results for small-world network with three added shortcuts. The thick, medium, and thin lines correspond to the networks in which the mean degree of the underlying cycle is equal to 2, 4, and 6, respectively. [(b)–(d)] Results for directed small-world network with $⟨k⟩=10$ and 500 rewired shortcuts. In (a) and (c), $v_i$ is plotted against the position of the node in the underlying cycle. In (b), $v_i$ is plotted against $\left(k_i^{\text{out}}/k_i^{\text{in}}\right)/{\sum }_{j=1}^N\left(k_j^{\text{out}}/k_j^{\text{in}}\right)$; the line represents the MA result. In (d), the relationship between $v_i/\left(k_i^{\text{out}}/k_i^{\text{in}}\right)$ and $v_i$ is shown.

Figure 8

Schematic of redrawn directionally biased random network when the pacemaker is located in layer $L-M+1$ in the original directionally biased random network.

Figure 9

Relationships between ${\kappa }_{\text{cr}}$ and $v_i$. [(a) and (b)] Directionally biased random network with $N=200$ and weight of parallel links equal to $ϵ$. [(c) and (d)] Directionally biased random network with $N=200$ and weight of parallel links equal to unity. [(e) and (f)] Directed scale-free network with $N=200$. [(g) and (h)] C. elegans neural network with $N=237$. The data are plotted against $v_i$ in (a), (c), (e), and (g) and against $\left(k_i^{\text{out}}/k_i^{\text{in}}\right)/{\sum }_{j=1}^N\left(k_j^{\text{out}}/k_j^{\text{in}}\right)$ in (b), (d), (f), and (h). The lines in (a), (c), (e), and (g) represent ${\kappa }_{\text{cr}}\approx v_i^{-1}$.