The relative importance of structure and dynamics on node influence in reversible spreading processes

Identifying influential spreaders is an important topic in the spreading dynamics on complex networks Koschützki et al. (2005); Lü et al. (2016); Pei et al. (2020). Identifying these nodes can help us to formulate precise marketing strategies Leskovec et al. (2007), control the spread of public opinions Bovet and Makse (2019); Lin et al. (2018), prevent the catastrophic disruptions in power girds Motter and Lai (2002); Albert et al. (2004) and control the outbreak of epidemics Pastor-Satorras and Vespignani (2002); Scarpino and Petri (2019); Zhou and Liu (2008).

In recent years, there have been a lot of researches devoted to identifying the most influential spreaders Morone and Makse (2015); Pei et al. (2018); Hu et al. (2018); Lokhov and Saad (2017); Zheng et al. (2021). As the network structure has a significant impact on the spreading processes, some structural centralities are used to measure the spreading influence of a node or node set, such as degree, closeness centrality, betweenness centrality and $k$-shell index Lü et al. (2016); Pei et al. (2020).

However, the complex interplays between network structure and spreading dynamics sometimes make the structural centralities be unable to effectively identify the influential nodes accurately in complex networks. Poux-Médard et al. (2020); Erkol et al. (2020); Aral and Dhillon (2018). Integrating the dynamical states of nodes in the spreading process can promote the accuracy of measures in identifying the most influential spreaders Klemm et al. (2012). Most of previous researches focus on irreversible spreading dynamics which has a final state. But, some spreading processes are reversible with repeated infections, such as meme spreading on online social networks Gleeson et al. (2014), gonorrhea spreading propagation on sexual intercourse networks Pastor-Satorras and Vespignani (2001a) and the rise and fall of stock prices on financial stock market networks Stavroglou et al. (2019). These reversible processes can be described by the SIS spreading dynamics Barzel and Barabási (2013); Pastor-Satorras and Vespignani (2001b, c), where a node transfers between infection state and recovery state. Qu $et$ $al$. proposed a single-node control model to evaluate the influence of nodes and a structure-dynamics combined centrality to identify influential nodes in the reversible spreading system Qu et al. (2020). They found that taking the neighbors’ centrality and dynamical states into account can identify influential nodes more accurately in real-world networks than the benchmark centralities.

Although the interplay between network structure and dynamics determines the influence of nodes, the relative importance of the two factors in identifying influential nodes is still unknown. By considering the positive effects of the neighbors’ local structures and the negative effects of the neighbors’ dynamical states, a new structure-dynamics combined centrality is proposed to identify influential spreaders and evaluate the relative importance of structure and dynamics on the determining node influence. In this new measure, the number of outgoing edges and the infection risks of neighbors are used to represent the local structures and dynamical states of the neighbors respectively. Simulation results on real-world networks show that considering neighbors’ local structures and dynamical states can help improving the accuracy of the index in identifying influential spreaders. Notably, compared with the number of outgoing edges of neighbors, slightly weakening the impact of neighbors’ infection risks can greatly promote the accuracy of the index to identify influential spreaders. There is an optimal range, within which the local structures and dynamical states of neighbors enhance the accuracy of the influence ranking index the most.

The rest of the paper is organized as follows. Section II introduces a single-node control model to quantify the influence of a node in SIS spreading processes. In Section III, based on the neighbors’ local structures and dynamical states , we propose a node centrality index in the SIS spreading dynamics. Section IV shows the numerical simulation results and analyses on real-world networks. Section V is the conclusion and discussion.

In our previous research, we have proposed a single-node control method to evaluate the influence of nodes in the reversible spreading system Qu et al. (2020). In SIS spreading processes, a node has only two possible states: susceptible (S) state and infected (I) state. An infected node transmits a disease to each of its direct susceptible neighbors with rate $\beta$ and recovers to susceptible state with rate $\mu$. After a long-time transient process, the proportion of infected nodes in the network will be stable, which is recorded as $\varphi_{0}$. Then we artificially set one node to be in the infected state constantly. This will cause a change (improvement) in the proportion of infected nodes in the entire network. After certain time steps, the proportion of the I-state nodes reaches a new steady state and the proportion of infected nodes is recorded as $\varphi$. We define $\Delta\varphi=\varphi-\varphi_{0}$ as the spreading influence, also called the spreading efficiency of the controlled node. The larger the $\Delta\varphi$ is, the higher influence of the controlled node has.

In simulations, we use the synchronous updating method Shu et al. (2016). The recovery rate is $\mu=0.1$ and the effective transmission rate $\lambda=\beta/\mu$ should not be too large because when it is too large, the propagation can easily spread to the entire network regardless of the node under control Liu et al. (2015). In that case the difference between the controlled nodes is diminished, and the influence of each node is indistinguishable. Meanwhile, the effective transmission rate $\lambda$ should not be too small. If it is too small, the propagation will be limited to the local neighbourhood of the controlled node and cannot affect the entire network. We obtain the SIS epidemic threshold $\lambda_{c}$ using the susceptibility Ferreira et al. (2012); Shu et al. (2015); Xu et al. (2019)

and choose an appropriate transmission rate $\lambda>\lambda_{c}$. Under this effective transmission rate, the influence of nodes can be distinguished.

It has been pointed out that compared with degree and $k$-shell index, considering the contribution of neighbors to the initial spreader can significantly improve the accuracy of ranking measures in the SIR-like spreading processes Liu et al. (2016). If a neighbor $j$ of node $i$ only has neighbors that are also the direct neighbor of node $i$, when we control node $i$, the contribution of neighbor $j$ is less because it cannot assist node $i$ to spread the message to the entire network.

Assume that the network $G=(V,E)$ is unweighted and undirected composed of $|V|=N$ nodes and $|E|=M$ edges. The adjacency matrix of the network is denoted as $\textbf{A}=(a_{ij})$, where $a_{ij}=1$ means there is a direct connection between node $i$ and node $j$, otherwise $a_{ij}=0$. We further consider the two-step neighbor $l$ of node $i$ connected to the node $i$ through the nearest neighbour node $j$. If $a_{ij}=1$, $a_{jl}=1$ and $a_{il}\neq 1$, then we define $b_{jl}=1$ to represent an outgoing edge of node $j$. The edge between the nearest neighbour node $j$ and node $l$ is the outgoing edge of node $j$ relevant to node $i$. For each of the neighbor node $j$, there is $k_{j}^{out}=\sum_{l\in\Gamma_{j}}{b_{jl}}$. Take the network in Fig. 1 for example. Node 1 has four neighbors $\{2,3,4,5\}$ and the outgoing edges of its nearest neighbour node 2 are the edges that connect node 2 and the node set $\{6,7,8,9\}$. The outgoing edges of nodes 3, 4, 5 connect to the node sets $\{10,11\}$, $\{12,13,14\}$ and $\{15,16\}$ respectively. Considering the characteristics of SIS spreading processes, we introduce the number of outgoing edges of neighbors into the node influential index with a weighting parameter $a$. The idea is the more outgoing edges the neighbor nodes have, the more they help the considered node to spread information or message to the entire network Liu et al. (2016).

In the SIS spreading dynamics, when the system reaches a steady state, a node can still be infected repeatedly. In order to maximize the spreading to the entire network, we consider the risk that a node is infected. In Fig. 1, the infection risk of node 3 is 0.5. When node 1 is controlled and spreads out through node 3, because node 3 has a risk of infection, the influence of node 1 will be reduced. As the infection risk has a negative impact on the influence of origin node, the term with $\rho$ has a minus sign. Parameter $b$ is an adjustable weight indicating the relative importance of local dynamical states (i.e., infection risks).

As considering neighbors’ local structures and dynamical states can effectively improve the accuracy of ranking measure for node influence on them Qu et al. (2020), we here investigate how to quantitatively evaluate the importance of these two factors. We propose an index to rank node influence in SIS reversible spreading processes called neighboring local structures and infection risks coupled centrality (NSRC), which is defined as

where $k_{i}$ is the benchmark centrality (i. e., degree), $j\in\Gamma_{i}$ is the direct neighbor of node $i$. The second item on the right side of Eq. (6) represents the local structures of the neighbor node $j$, which is the number of outgoing edges through all neighbors of node $i$. The third item represents the contribution of dynamical state of neighbor node $j$, which is the infection risk of node $j$. In the spreading process, when the system reaches its steady state, a node can still be infected repeatedly. In order to maximize the spread of infection to the entire network, we consider controlling a node $i$ in I state. Suppose the neighboring node $j$ is in the I state with infection probability $\rho_{j}$ in steady state. In simulations, if the neighboring node $j$ is in I state at this time step, node $i$ will have no effect on node $j$ and the influence of node $i$ will be reduced. As the $\rho_{j}$ has a negative impact on the influence of node $i$, the term with $\rho_{j}$ has a minus sign. For simplicity, only the one-step neighbors of node $i$ and their outgoing edges are considered. $a$ and $b$ are two weight parameters, which represent contribution of the the local structures and the dynamical states of the neighbors respectively. The larger $a$ indicates the higher importance of the local structures and the larger $b$ indicates that the neighbors’ infections are more important. The combination of $a$ and $b$ can be coordinated by their weights which will be discussed in detail later.

In order to measure the accuracy of NSRC in identifying influential spreaders, the following two evaluation methods are used. The imprecision function is defined as

where $p$ is the fraction of network size $N$. $\phi(p)$ is the average spreading efficiency of $pN$ nodes with the highest NSRC, and $\phi_{eff}(p)$ is the average spreading efficiency of the $pN$ nodes with the highest spreading efficiency. When $p$ is fixed, a smaller $\varepsilon(p)$ value indicates a more accurate centrality in identifying influential spreaders.

The imprecision function reflects the accuracy of the NSRC in identifying the most influential nodes. In order to measure the ability of NSRC in ranking all nodes in the network, the Kendall’s $\tau$ correlation coefficient is used, which is given by Kendall (1938)

where $\operatorname{sgn}(x)$ is a sign function. $\operatorname{sgn}(x)$ returns 1 if $x>0$, -1 if $x<0$, and 0 if $x=0$, respectively. $N$ is the number of nodes in the list. $x_{i}$ and $x_{j}$ are the ranking orders of node $i$ and node $j$ in sorting sequence 1. $y_{i}$ and $y_{j}$ are the ranking orders of node $i$ and node $j$ in sorting sequence 2. If node $i$ and node $j$ have a concordant order in sorting sequence 1 and 2, $(x_{i}-x_{j})(y_{i}-y_{j})>0$. If node $i$ and node $j$ have a discordant order in sorting sequence 1 and 2, $(x_{i}-x_{j})(y_{i}-y_{j})<0$. If node $i$ and node $j$ have a same order in sorting sequence 1 or 2, $(x_{i}-x_{j})(y_{i}-y_{j})=0$. We rank the nodes by the proposed NSRC as the sorting sequence 1 and rank the nodes by the simulated spreading efficiency as sorting sequence 2. We compute the correlation coefficient of sorting sequence 1 and 2. The larger correlation coefficient is, the more concordant the centrality and the spreading efficiency are. For an explicit comparison, we calculate the improved $\tau$ ratio of the NSRC over the reference centrality, which is

where $\tau_{c}$ is the correlation coefficient between the NSRC and spreading efficiency, $\tau_{0}$ is the correlation coefficient between the neighboring dynamical information centrality (NDIC) and spreading efficiency.

We apply the NSRC to eight real-world networks as listed in Table 1. The real-world networks are: Netsci (collaboration network of network scientists), Hamster (friendships and family network of a website), Router (the router network collected by the Rocketfuel Project), Blog (communication network between users on the MSN website), PGP (an encrypted communication network), CA_hep (collaboration network of arxiv in high-energy physics theory), Astro (collaboration network of astrophysics scientists) and Email (email communication network of University College London) Newman (2006); Spring et al. (2002); Boguna et al. (2004); Newman (2001); Kitsak et al. (2010).

In this paper, we quantitatively analyzed the relative importance of the neighbors’ local structures and dynamical states in ranking node influence in the SIS-like spreading processes. We proposed a centrality index NSRC that combines the positive effect of the neighbors’ outgoing edges and the negative effect of the neighbors’ infection risks with two weighting factors $a$ and $b$. A large number of neighbors’ outgoing edges have a positive effect on the spreading influence of a node, while the high infection risks of the neighbor nodes reduce the influence of the considered node. A larger value of $a$ or $b$ means a stronger positive local structure effect or negative local dynamical effect. Through a large number of simulations on eight real-world networks, we found that when the positive and negative effects are taken appropriately, under appropriate values of $a/b$, the proposed centrality index NSRC can improve the ranking accuracy significantly.

Specifically, to identify the most influential nodes accurately, the weight of the neighbors’ dynamical states $b$ should not be greater than the weight of the neighbors’ local structures $a$. Although the high infection risk of a neighbor node can inhibit the spreading capacity of the controlled node, the close local structure with more common neighbors between the considered node and its neighbor node can induce the echo chamber effect, and thus slightly promote the spreading processes. Therefore, an optimal combination of parameters with $b<a$ can make the NSRC evaluate the spreading influence of a node more accurately. This is helpful to distinguish the impact of the neighboring nodes having the same local structures but different infection probabilities. By analyzing the simulation results of real-world networks, it is found that when the outgoing edges of neighbor nodes are taken into account, the accuracy of NSRC is greatly improved over the centrality measure NDIC. After further optimizing the parameters, the improved ranking correlation of NSRC over NDIC can be as high as 10% to 100%. Compared with the degree centrality of the neighbors’, the neighbors’ outgoing edges can be more accurate in reflecting the importance of neighbors’ local structures in the spreading processes. Further more, when we change the transmission rate $\lambda$, the NSRC has a higher accuracy than the existing index in ranking influential spreaders in the SIS-like spreading processes.

In the reversible processes, we found that considering the positive effects of neighbors’ outgoing edges and the negative effects of neighbors’ infection risks can effectively improve the accuracy of indexes in identifying influential spreaders. This deepens our understanding of identifying influential spreaders in the reversible processes. The benchmark centrality used in NSRC in our paper is degree, which can be substituted by any other benchmark centralities, such as $k$-shell index centrality Kitsak et al. (2010) and the collective influence index Morone and Makse (2015). The proposed ranking index NSRC can be applied in other reversible dynamics and dynamical systems with steady state such as synchronization processes Barzel and Barabási (2013) and cascading failures Lin et al. (2020).