Influence and Influenceability Global Directionality in Directed Complex Networks Niall Rodgers Peter Tiˇ no and Samuel Johnson

2025-05-05 0 0 1.86MB 31 页 10玖币

侵权投诉

Inﬂuence and Inﬂuenceability: Global Directionality in

Directed Complex Networks

Niall Rodgers, Peter Tiˇno and Samuel Johnson

June 27, 2023

Abstract

Knowing which nodes are inﬂuential in a complex network and whether the network can be

inﬂuenced by a small subset of nodes is a key part of network analysis. However, many tradi-

tional measures of importance focus on node level information without considering the global

network architecture. We use the method of Trophic Analysis to study directed networks and

show that both ‘inﬂuence’ and ‘inﬂuenceability’ in directed networks depend on the hierarchical

structure and the global directionality, as measured by the trophic levels and trophic coherence,

respectively. We show that in directed networks trophic hierarchy can explain: the nodes that

can reach the most others; where the eigenvector centrality localises; which nodes shape the be-

haviour in opinion or oscillator dynamics; and which strategies will be successful in generalised

rock-paper-scissors games. We show, moreover, that these phenomena are mediated by the

global directionality. We also highlight other structural properties of real networks related to

inﬂuenceability, such as the pseudospectra, which depend on trophic coherence. These results

apply to any directed network and the principles highlighted – that node hierarchy is essential

for understanding network inﬂuence, mediated by global directionality – are applicable to many

real-world dynamics.

1 Introduction

Inﬂuence in directed complex networks and the ability of the networks to be inﬂuenced is vitally

important in many real-world systems, for example the spreading of opinions and epidemics or

the synchronisation of the brain in a seizure [1]. However, when we think of what makes nodes

inﬂuential, the answer is very disparate and depends on many factors. This question has been

of great interest to the network science community and well studied in the case of undirected

networks [2, 3]. However, in the directed case insight can be gained by considering properties

unique to directed networks. This is necessary as many real-world systems are intrinsically directed

and the inﬂuence of nodes is strongly tied to the directionality of the edges [4]. Inﬂuence can

be thought of as how well nodes control the dynamics of a network, how measures of centrality

are distributed across the network, how many nodes can be reached from a set of nodes and how

sensitive the network is to perturbations. We show that all of these properties can be understood

and made intuitive by considering the hierarchical ordering and global directionality of the network

as measured through the technique of Trophic Analysis [5, 6, 7].

When the nodes are easily ordered in a hierarchical fashion, as in a food-web, it is clear that the

network can be inﬂuenced by the nodes at the bottom of this hierarchy and conversely it is very

arXiv:2210.12081v2 [physics.soc-ph] 26 Jun 2023

diﬃcult to inﬂuence the network from the top of the hierarchy. When there is little hierarchical

structure, like in an Erd˝os-R`enyi random graph, this eﬀect is damped and inﬂuence over the net-

work is more evenly distributed. This simple construction, detailed in the background, aides in the

interpretation of control over network dynamics, spreading processes, localisation of centrality mea-

sures and sensitivity to perturbations. Hierarchical ordering can explain why nodes which locally

look unimportant may be able to inﬂuence the entire network. This framework may provide an

interpretation to observations made about inﬂuence in directed networks in a variety of literature

settings such as the eﬀect of heterogeneous centrality and directionality in opinion formation in

real networks [8], the inﬂuence of peripheral nodes on dynamics of directed networks [9] or the

asymmetry between paths up and down the network hierarchy [10]. Trophic Analysis pairs a global

measure of directionality with a local measure of hierarchy, making it diﬀerent from a single cen-

trality measure. This allows an intuition surrounding the variability in the importance of a node’s

position in the hierarchy and how this aﬀects its role in the network. This diﬀers from previous

results on the relationship between hierarchy and inﬂuence which do not feature this pairing of

local and global measures [11, 12]. The fact that centrality measures play diﬀerent roles dependent

on the mesoscale structure of the network has been noted previously in the case of PageRank and

clustering [13].

This paper is organised as follows. We ﬁrst introduce the background and explain the principles

underlying Trophic Analysis. We then introduce some dynamics and highlight how global direc-

tionality can aﬀect the inﬂuence and inﬂuenceability of these processes. These are Majority Vote,

Kuramoto oscillators, the Voter Model and the frequency of strategies in Generalised Rock-Paper-

Scissors games. We then include some results on the relationship between structure and inﬂuence

in real-world networks and how this can be shaped by hierarchy. We demonstrate the relationship

between hierarchy and eigenvector localisation, left and right eigenvector correlation (with speciﬁc

real-world examples), sensitivity to structural perturbation through the pseudospectra and the size

of the out-component of a node. The real network data used in this paper, also used in [14, 7], is

available at [15] and contains food-webs, neural networks, social networks and more as well as the

original sources of the network data used. This shows how many diverse notions of inﬂuence can be

investigated in directed networks using Trophic Analysis and how in a wide range of systems the

ability to exploit hierarchy to inﬂuence a system depends on the global directional organisation.

2 Background

Real-world systems formed by many interacting elements can be represented using graphs. These

complex networks are sets of nodes or vertices representing the elements of the system while the

edges or links represent the interactions or connections between elements. Many real-world systems

such as social networks, food-webs, the internet and more have interactions which are intrinsically

directional and may represent the inﬂuence a node has over another [16]. This structure can be

represented through a matrix, A, known as an adjacency matrix where the edges are represented

by the non-zero entries of the matrix. For an unweighted directed network of Nnodes this N×N

matrix is deﬁned as

Aij =(1 if there exists an edge i→j

0 otherwise .(1)

In the case of directed networks this matrix is not symmetric, unlike the undirected case where

edges go in both directions and the matrix is symmetric. Each node ithen has an in-degree,

kin

i=PjAji, and an out-degree, kout

i=PjAij . The matrix Acan also be weighted to show the

strength of interactions but here we focus on the simple unweighted case although it is possible to

use Trophic Analysis in the weighted regime [5].

2.1 Trophic Analysis

Trophic Analysis is a technique to quantify the global directionality inherent in real directed net-

works [5], and is applicable to any directed network. Trophic Analysis was originally derived from

ecology [17] where the original deﬁnition linked hierarchy to weighted steps from the basal nodes

(vertices of in-degree zero), which is an intuitive way to view hierarchy but cannot be generalised

to any directed network without basal nodes like the deﬁnition used here and in [5, 6, 18, 7].

Much of the previous work which applied trophic level and incoherence used the previous deﬁnition

[14, 17, 19, 20, 21]. This was successfully applied in a wide variety of settings including infras-

tructure [22, 23], the structure of food webs [20], spreading processes such as epidemics or neurons

ﬁring [21], and organisational structuring [19].

Trophic Analysis combines two parts: the node level local information, Trophic Level, and a

measure of the global network directionality, Trophic Incoherence. Trophic level is a node level

quantity which measures where a speciﬁc node sits in the network hierarchy. Trophic level is

calculated by solving the N×Nmatrix equation, ﬁrst proposed in [5], given by

Λh=v, (2)

where his the vector of trophic levels for each node and vis the vector imbalance of the in and out

degree of each node, where each element is deﬁned as vi=kin

i−kout

i. Λ is the Laplacian matrix:

Λ = diag(u)−A−AT,(3)

where uis the sum of the in and out degrees of each node, ui=kin

i+kout

i, and ATis the transpose

of the adjacency matrix, A. The solution of equation 2, which provides the trophic levels of the

nodes, is only deﬁned up to a constant vector so we take the convention that the lowest level node

is set to trophic level zero. The Laplacian matrix is singular by deﬁnition, yet a solution can be

found either by choosing a node (say i= 1) and setting its value (e.g. h1= 0); or iteratively, which

is convenient for very large networks [5].

In a balanced network, for instance a directed cycle, there is no hierarchical structure so every

node has the same level. This is due to the dependence of equation 2 on the imbalance vector,

vi=kin

i−kout

i, which means that when the in and out-degrees of all nodes are equal the right side

of the equation goes to zero. In a network with a perfect hierarchy like a directed line, the nodes

are assigned integer levels with steps of one between connected nodes. The level distributions of

real networks are more complex and lie somewhere between these extreme cases.

Trophic Incoherence is a global parameter which measures how well hierarchically ordered the

network is. It is related to the amount of feedback in the system, and thus to network properties

such as the spectral radius, non-normality and strong connectivity [5, 7]. It is quantiﬁed via the

trophic incoherence parameter F, which is deﬁned as

F=Pij Aij (hj−hi−1)2

Pij Aij

.(4)

In [5], the authors begin with equation (4) (which is the original deﬁnition of trophic incoherence

[17]) and deﬁne the trophic levels, h, as those which minimise F. Hence, the linear form of equation

(3) and dependence on the imbalance vector comes from the minimisation of the quadratic function

in equation 4.

Trophic Incoherence measures how far the mean square of the diﬀerence in trophic level, h

calculated via equation 2, between start and end vertices of all the edges diﬀers from one. The

equation for Trophic Level, equation 2, can be derived by minimising equation 4 with respect to

h. The Trophic Incoherence takes values between 0 and 1 with real networks found on a spectrum

between these extreme values. Networks with a perfect hierarchy are coherent and have F= 0.

When the network is balanced like a directed cycle then F= 1. It is also possible to speak in terms

of coherence instead of incoherence by using the quantity 1 −F. When we talk about hierarchy we

refer to the bottom of the hierarchy as nodes of low trophic level and the top of the hierarchy as

the nodes of high trophic level. In a directed path the low trophic level nodes would be the start

of the path and the high level nodes would be near the end of the path. In a food-web the bottom

nodes are plants and the top nodes are apex predators. This, however, is just a convention and

the notion of top and bottom can be ﬂipped by taking the transpose of the adjacency matrix (for

example, when describing hierarchies of information ﬂow from nodes to nodes).

Using directionality and hierarchy to analyse the structure of directed networks in this way is

quite natural and as such alternative similar formulations exists which rank nodes and measure

the global directionality. SpingRank [24] views the ranking problem as minimising the energy of a

network of directed springs, leading to a similar minimisation problem as the one used in Trophic

Incoherence. However, these authors focus on the node level ranks rather than the global direc-

tionality and add a regularisation term to remove the invariance of their rank equation to addition

of a constant vector. There is also a methodology based on Helmholtz–Hodge decomposition for

measuring “circularity” in directed networks [25, 26] which has been shown to be equivalent to

Trophic Analysis [5].

2.2 Network Generation

In order to study how the properties of networks depend on their trophic structure it is necessary

to be able to numerically generate networks which span the full range of trophic incoherence, while

keeping the number of nodes and edges ﬁxed. We adapt the Generalised Preferential Preying Model

(GPPM) [21] in an identical way to [6] to the deﬁnition of trophic level which does not require basal

nodes (vertices of zero in-degree) and use that to generate the networks we require. This works by

generating an initial conﬁguration of Nnodes and a small number of random edges, calculating

the initial trophic levels of this setup, adding edges up to the required amount using a probability

determined by the trophic level and a temperature-like control parameter which can aﬀect the spread

of level diﬀerences. In order to generate a network with no basal nodes the initial conﬁguration is

that each node has in-degree one with the source vertex for that edge chosen uniformly at random

from the other nodes in the network. Once the initial trophic levels ˜

hare calculated via equation

2 then new edges, up to the required amount, can be added with probability deﬁned as

Pij = exp "−(˜

hj−˜

hi−1)2

2TGen #,(5)

where Pij is the probability of connecting nodes i to j. The parameter TGen controls this process.

When this parameter is small it is likely that edges connect only between nodes where the level

diﬀerence is 1 or near to it. When TGen is very large then the edge-addition probability goes towards

1 irrespective of the trophic level diﬀerence between the end and start nodes.

Figure 1: Relationship between Trophic Incoherence and generation temperature in the model

used in this work, where each of the 1000 points per network size represents a distinct network

generated by the model, with N= 100, N= 200 and N= 500, ⟨k⟩= 20 and no basal nodes.

The generation temperature is logarithmically spaced between 10−2and 102. We also plot with a

dashed line an analytical approximation, given by equation (7), for the relationship between the

Trophic Incoherence and Temperature.

The relationship between the generation temperature and the trophic incoherence is displayed

in ﬁgure 1, which shows how the model can be used to create a sample of networks of varying

incoherence. In order to eﬃciently sample the whole spectrum of the trophic incoherence we use

logarithmic spacing of TGen throughout the paper, except for in the sections on the generalised rock-

paper-scissors games and the out-component analysis. In these two sections we compare networks of

low, intermediate and high trophic incoherence, for which we selected the generation temperatures

to be 0.02,1 and 100, respectively. As shown in ﬁgure 1 this picks out each of the broad regimes

of the generative model; the low temperature regime of very coherent networks, the intermediate

regime where we see more variability with the temperature, and the high temperature regime of

incoherent networks.

We also show in ﬁgure 1 how the behaviour of this model can be analytically approximated.

In previous work on trophic analysis, where the ecological deﬁnition of trophic levels was used,

the trophic incoherence, q, was deﬁned as the standard deviation of the trophic level diﬀerences

spanned by edges [17]. Under this deﬁnition the mean trophic level is always one, and a network

is more incoherent the more heterogeneously trophic diﬀerences are distributed around this value.

Given a set of trophic levels (by whichever deﬁnition), it is possible to convert between the two

measures of incoherence via the formula deﬁned in [5],

F=η2

1 + η2,(6)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

InfluenceandInfluenceability:GlobalDirectionalityinDirectedComplexNetworksNiallRodgers,PeterTiˇnoandSamuelJohnsonJune27,2023AbstractKnowingwhichnodesareinfluentialinacomplexnetworkandwhetherthenetworkcanbeinfluencedbyasmallsubsetofnodesisakeypartofnetworkanalysis.However,manytradi-tionalmeasuresofim...

展开>> 收起<<

Influence and Influenceability Global Directionality in Directed Complex Networks Niall Rodgers Peter Tiˇ no and Samuel Johnson.pdf

共31页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Influence and Influenceability Global Directionality in Directed Complex Networks Niall Rodgers Peter Tiˇ no and Samuel Johnson

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: