Ranking the spreading ability of nodes in complex networks based on local structure

doi:10.1016/j.physa.2014.02.032

Physica A: Statistical Mechanics and its Applications

Volume 403, 1 June 2014, Pages 130-147

https://doi.org/10.1016/j.physa.2014.02.032 Get rights and content

Highlights

•
The structure of the neighbors of a node can affect its spreading ability.
•
A local structural centrality method for ranking node’s spreading ability is proposed.
•
The proposed method considers both the number and structure of node’s neighbors.
•
The proposed method outperforms other measures on both real and artificial networks.
•
The proposed method is robust to different network sizes and community structure.

Abstract

Ranking nodes by their spreading ability in complex networks is a fundamental problem which relates to wide applications. Local metric like degree centrality is simple but less effective. Global metrics such as betweenness and closeness centrality perform well in ranking nodes, but are of high computational complexity. Recently, to rank nodes effectively and efficiently, a semi-local centrality measure has been proposed as a tradeoff between local and global metrics. However, in semi-local centrality, only the number of the nearest and the next nearest neighbors of a node is taken into account, while the topological connections among the neighbors are neglected. In this paper, we propose a local structural centrality measure which considers both the number and the topological connections of the neighbors of a node. To evaluate the performance of our method, we use the Susceptible–Infected–Recovered (SIR) model to simulate the epidemic spreading process on both artificial and real networks. By measuring the rank correlation between the ranked list generated by simulation results and the ones generated by centrality measures, we show that our method can rank the spreading ability of nodes more accurately than centrality measures such as degree, $k$ -shell, betweenness, closeness and local centrality. Further, we show that our method can better distinguish the spreading ability of nodes.

Introduction

The study of the spreading process on complex networks has drawn much attention recently because of its great theoretical significance and remarkable practical value in many areas including epidemic controlling [1], [2], [3], [4], [5], information dissemination [6], [7] and viral marketing [8], [9] etc. One of the fundamental problems in understanding and controlling spreading process is evaluating the spreading ability for each node in the network, i.e. how many nodes will finally be covered when the spreading origins from this single node [10], [11], [12], [13], [14], [15], [16]. The knowledge of node’s spreading ability shows new insights for applications such as finding social leaders [17], ranking reputation of scientists, publications [18] and designing efficient methods to either hinder epidemic spreading or accelerate information dissemination.

Over the recent years, various centrality measures such as degree, betweenness [19], closeness [20] and eigenvector [21] centralities have been proposed to rank nodes in the network. Degree centrality is a simple and efficient local metric, but it is less relevant since it neglects the global structure of the network. Some well-known global metrics such as betweenness centrality and closeness centrality can give better results. However due to their high computational complexity, they are incapable to be applied in large-scale networks. Recently, Kitsak et al. found that the most efficient spreaders are those located within the core of the network as identified by the $k$ -shell decomposition analysis [10]. After this, some modified network decomposition algorithms have been introduced to further improve the ranking performance [16], [22]. In directed networks, several iterative process based ranking methods such as PageRank [23], HITS [24] and LeaderRank [17] have been proposed to rank nodes.

Since the scale of online social systems keep growing, they can have millions or even billions of user, e.g. the total number of monthly active Facebook users is 1.1 billion till June 2013.¹ Thus the ranking algorithms which are based on global information of the network will be very time-consuming and incapable to be applied. Hence, in order to rank nodes effectively and efficiently, it is better to design the ranking algorithms based on the local information of the network. For example, a semi-local centrality measure which considers both the nearest and the next nearest neighbors of a node has been proposed in Ref. [11]. This centrality measure has been shown to well rank the spreading ability of nodes and achieves a good tradeoff between low-relevant degree centrality and other time-consuming measures.

However, when the local centrality is used to rank nodes, only the number of the nearest and the next nearest neighbors of a node is considered, while the topological connections among the neighbors are completely ignored. Actually, the topological connections among the neighbors are also very important. For nodes with the same local centrality, the one with denser connected neighbors is supposed to have stronger spreading ability since denser connected neighbors get more chance to influence each other. Inspired by this idea, we propose a local structural centrality measure which considers both the number and the topological connections of node’s neighbors, where the local clustering coefficient of a node is used to measure the topological connections among its neighbors. We use the susceptible–infected–recovered (SIR) model [25] to simulate the epidemic spreading process on both artificial and real networks. By measuring the rank correlation between the ranked list generated by simulation results and the ones generated by centrality measures, we show that our method can rank the spreading ability of nodes more accurately than centrality measures such as degree, $k$ -shell, betweenness, closeness and local centrality. Through experiments on artificial networks generated by Barabási–Albert (BA) [26], [5] network model and Lancichinetti–Fortunato–Radicchi (LFR) network model [27], we show that our method can outperform other centrality measures in scale-free networks with different sizes and different community structure. Further, we show that our proposed method can better rank the most influential nodes than other measures considered. Moreover, we use the susceptible–infected (SI) model [25] to simulate the epidemic spreading process and show that our proposed method can better rank the spreading ability of nodes under the SI model. Finally, we examine the ability of different methods to distinguish the spreading ability of the nodes and show that our proposed method performs better.

Following parts are organized as follows. We briefly review the definition of centrality measures used for comparison in Section 2 and introduce our local structural centrality measure in Section 3. In Section 4, we present the data, the spreading model and the evaluation measure that are used to evaluate the performance of our method. The experimental results are presented in Section 5. We conclude our paper and give a discussion in Section 6.

Section snippets

Centrality measures

Consider an unweighted and undirected simple network $G = (V, E)$ with $n = | V |$ nodes and $m = | E |$ links. $G$ could be described by an adjacent matrix $A = {a_{u v}} \in R^{n, n}$ , where $a_{u v} = 1$ if node $u$ is connected with node $v$ and $a_{u v} = 0$ otherwise. We use $Γ_{h} (v)$ to denote the set of neighbors within $h$ -hops from node $v$ .

The degree centrality (DC), $C_{D} (v)$ , of node $v$ can be calculated as $C_{D} (v) = \sum_{u = 1}^{n} a_{u v} = | Γ_{1} (v) | .$ The computational complexity for degree centrality is $O (n)$ .

The $k$ -shell centrality (KS) [10], $C_{K S}$ , is obtained by

Our proposed local structural centrality

To begin our analysis, we first discuss the impact of the local structure of a node on its spreading ability. By local structure, we mean the structure of the nearest and next nearest neighbors of a node. As is known to us, the number of neighbors of a node can affect its spreading ability. For example, the degree centrality considers the number of the nearest neighbors and the local centrality considers the number of the nearest and the next nearest neighbors. Both of them are commonly used

Experimental setup

To evaluate the performance of our proposed centrality measure, we apply it on both artificial and real networks. The artificial networks include networks generated by the Barabási–Albert (BA) network model [26], [5] and the Lancichinetti–Fortunato–Radicchi (LFR) network model [27]. All these artificial networks are undirected unweighted and scale-free. The real networks are drawn from disparate fields, including: (i) Email: a network of e-mail interchanges between members of the University

Results

In this paper, we use relatively small values of $β$ in SIR model, namely $β \in (0, 0.1]$ , so that the infected percentage of the nodes remains small. When $β = 0.1$ , the average infected percentage of the nodes is 0.1147 in Email, 0.0008 in Blog, 0.0057 in PGP and 0.0031 in Twitter. In the case of large $β$ values, where spreading can reach a large fraction of the nodes, the role of individual node is no longer important and spreading would cover almost all the network, independently of where it originates

Conclusion and discussions

In this paper, we propose a local structural centrality measure to rank the spreading ability of nodes in the network. The proposed centrality measure considers not only the number of nearest neighbors of a node, but also the topological connections among the neighbors. To evaluate the performance, we apply our method on both artificial and real networks and use the SIR model to simulate the spreading process. By employing the Kendall’ tau ( $τ$ ) coefficient to measure the rank correlation between

Acknowledgments

We greatly appreciate the Editor’s encouragement and the anonymous reviewer’s valuable comments and suggestions to improve this work. This work is supported by the Natural Science Foundation of China (61272240, 61103151, 71301086, 11101243), the Doctoral Fund of Ministry of Education of China (20110131110028), the Natural Science foundation of Shandong province (ZR2012FM037) and the Excellent Middle-Aged and Youth Scientists of Shandong Province (BS2012DX017, BS2012SF016).

References (45)

J. Yang et al.
A study of the spreading scheme for viral marketing based on a complex network model
Physica A
(2010)
D. Chen et al.
Identifying influential nodes in complex networks
Physica A
(2012)
B. Hou et al.
Identifying all-around nodes for spreading dynamics in complex networks
Physica A
(2012)
J.-G. Liu et al.
Ranking the spreading influence in complex networks
Physica A
(2013)
D. Wei et al.
Identifying influential nodes in weighted networks based on evidence theory
Physica A
(2013)
A. Zeng et al.
Ranking spreaders by decomposing complex networks
Phys. Lett. A
(2013)
L.C. Freeman
Centrality in social networks conceptual clarification
Social Networks
(1978–1979)
H.-B. Hu et al.
Unified index to quantifying heterogeneity of complex networks
Physica A
(2008)
S. Zhang et al.
Identification of overlapping community structure in complex networks using fuzzy-means clustering
Physica A
(2007)
R.M. Anderson et al.
Infectious Diseases of Humans: Dynamics and Control
(1991)

J. Heesterbeek

H. Hethcote

The mathematics of infectious diseases

SIAM Rev.

(2000)

R. Pastor-Satorras et al.

Epidemic spreading in scale-free networks

Phys. Rev. Lett.

(2001)

R. Albert et al.

Statistical mechanics of complex networks

Rev. Modern Phys.

(2002)

L. Lü et al.

The small world yields the most effective information spreading

New J. Phys.

(2011)

M. Medo et al.

Adaptive model for recommendation of news

Europhys. Lett.

(2009)

C. Castellano et al.

Statistical physics of social dynamics

Rev. Modern Phys.

(2009)

M. Kitsak et al.

Identification of influential spreaders in complex networks

Nat. Phys.

(2010)

F. Bauer et al.

Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach

Europhys. Lett.

(2012)

L. Lü et al.

Leaders in social networks, the delicious case

PLoS One

(2011)

Y.-B. Zhou et al.

Quantifying the influence of scientists and their publications: distinguishing between prestige and popularity

New J. Phys.

(2012)

G. Sabidussi

The centrality index of a graph

Psychometrika

(1966)

Cited by (176)

An improved gravity centrality for finding important nodes in multi-layer networks based on multi-PageRank
2024, Expert Systems with Applications
How to identify important nodes in multi-layer networks is still an unresolved issue in network science, which has aroused the interest of many researchers. In addition, the relationships between entities in many real-world systems are diverse and can be modeled as multi-layer networks. In the past few decades, scholars have defined various centrality methods from different perspectives to find influential nodes in multi-layer networks, but they only utilize the local or global topology information. Recently, various gravity centralities that utilize both the local and global topological structure information have been defined for identifying key nodes in single-layer networks. In the gravity model, the interaction between two nodes is related to their mass and distance. In consideration of the advantages of gravity model, in this paper, we define an improved gravity centrality for identifying key nodes in multi-layer networks based on multi-PageRank centrality, referred to as the PRGC. Unlike the existing gravity centralities that treat each node degree as its mass, our proposed centrality views the multi-PageRank centrality value of each node as its mass. Furthermore, PRGC weights the shortest path distance between any two nodes across all network layers to define their distance in multi-layer networks. Finally, to illustrate the effectiveness and superiority of the proposed centrality approach, numerical experiments are conducted on six real-world multi-layer networks show that our proposed centrality method outperforms state-of-the-art centralities.
WSLC: Weighted semi-local centrality to identify influential nodes in complex networks
2024, Journal of King Saud University - Computer and Information Sciences
Identifying and ranking influential nodes in complex networks is a critical aspect to study the survival and robustness of networks. Many ongoing researches have proposed centrality metrics to address this problem, so that the performance of each is attributed to specific scenarios. For example, metrics based on local structure have low ranking accuracy due to the use of limited information, and metrics based on global structure suffer from high complexity. Meanwhile, metrics based on semi-local structure are amazingly well, but an efficient centrality for identifying influential nodes is still not available due to differences in the structure and scale of networks. In addition, most semi-local centrality metrics only consider one aspect of each node's information, and their development still faces serious challenges. This paper develops a Weighted Semi-Local Centrality (WSLC) to identify influential nodes in complex networks based on extended neighborhood concept. Here, several different weights are investigated to find the best performance on WSLC. We use the extended neighborhood concept to select the nearest neighbors, which considers the global information of the network in a limited and efficient way to calculate the ranks. Here, a distributed approach is presented that can cut a subgraph of the entire network for each node with low complexity. This subgraph contains neighbors with different hops, which are used to maintain high efficiency when facing large-scale networks. In addition to the importance of the node itself, WSLC also combines the importance of the node's nearest neighbors with different hops for ranking. Therefore, defining semi-local structure with a distributed approach as well as using an efficient edge weighting policy differentiates WSLC from other existing centrality metrics. The evaluation of WSLC has been done through several real-world networks using Kendall's correlation. The effectiveness of WSLC under the SIR infection spreading model has been verified by extensive simulations compared to state-of-the-art centrality metrics.
Identify influential nodes in complex networks: A k-orders entropy-based method
2023, Physica A: Statistical Mechanics and its Applications
Identifying influential nodes is a recognized challenge for the tremendous number of nodes in complex networks. Most of proposed methods detect the influential nodes based on their degree or topological location, which only consider the local or global information of the network causing inaccuracy. In this paper, we propose a k-orders entropy-based method to identify influential nodes. The influence of node is determined by its entropy with local and global information. The entropy reflecting local information is measured by the different order neighbors’ information of nodes while the entropy reflecting global information by the betweenness centrality. The experiments conducted on real-world networks demonstrate the proposed method is more accurate than other methods.
Towards identifying influential nodes in complex networks using semi-local centrality metrics
2023, Journal of King Saud University - Computer and Information Sciences
The influence of the node refers to the ability of the node to disseminate information. The faster and wider the node spreads, the greater its influence. There are many classical topological metrics that can be used to evaluate the influencing ability of nodes. Degree centrality, betweenness centrality, closeness centrality and local centrality are among the most common metrics for identifying influential nodes in complex networks. Degree centrality is very simple but not very effective. Global metrics such as betweenness centrality and closeness centrality can better identify influential nodes, but they are not compatible on large-scale networks due to their high complexity. In order to design a ranking method of influential nodes, in this paper a new semi-local centrality metric is proposed based on the relative change in the average shortest path of the entire network. Meanwhile, our metric provides a quantitative global importance model to measure the overall influence of each node. To evaluate the performance of the proposed centrality metric, we use the Susceptible-Infected-Recovered (SIR) epidemic model. Experimental results on several real-world networks show that the proposed metric has competitive performance in identifying influential nodes with existing equivalent centrality metrics and has high efficiency in dealing with large-scale networks. The effectiveness of the proposed metric has been proven with numerical examples and Kendall's coefficient.
A novel higher-order neural network framework based on motifs attention for identifying critical nodes
2023, Physica A: Statistical Mechanics and its Applications
Quantifying the importance of nodes is a fundamental and significant problem in network science. Potential applications including identifying critical people, epidemic spreading control, rumor control, protecting critical infrastructures that is vulnerable, predicting key proteins, and so on. However, most of the existing methods concentrate on the iterative approaches, only a minority of methods attempt to explore the importance of nodes by adopting machine learning. More importantly, in reality, multiple nodes often work together or generate associations. Although the existing important nodes mining methods based on machine learning consider network structures and node features, all of them ignore the higher-order relationships, i.e., multiple nodes interactions. Inspired by this, to accurately identify critical nodes with higher-order interaction information in networks, we propose a novel higher-order neural network framework based on motif-attention (i.e., HONNMA) from the perspective of higher-order interactions. The proposed framework (i.e., HONNMA) can encode the higher-order interaction relationships by employing weighted motif adjacency matrix, and learn the attention weights by motif-based attention mechanism, then adopt skip connection to obtain the node embeddings, finally use multiple feedforward layers to predict the critical scores of nodes. Extensive experiments conducted on four real-world datasets demonstrate the proposed model significantly outperforms the existing state-of-the-art baseline methods. To emphasize that, the higher-order neural network framework (i.e., HONNMA) can enhance the prediction of important nodes such as critical infrastructures, critical people, critical scientific publications, and critical proteins, and much more.
Ranking nodes in complex networks based on TsRank
2023, Physica A: Statistical Mechanics and its Applications
It is theoretically and practically meaningful to rank and identify nodes in complex networks in various fields, however, many existing methods consider single feature of graph. To utilize multiple attributes of graph, a novel ranking method based on Tsallis entropy is proposed in this paper, which considers information transfer efficiency as global information of nodes and takes extended mixed degree and core neighborhood centrality as local information of nodes. We utilize the monotonicity function index, cumulative distribution (CDF), Kendall’s tau coefficient, Jaccard similarity coefficient, and the total number of infected nodes based on susceptible–infected–recovered (SIR) model as evaluation metrics to measure the performance of the proposed method. The simulation results demonstrate that the proposed method has great superiority in terms of monotonicity, resolution, the accuracy of both the whole ranking results and top-c ranked nodes, and spreading ability of the top-10 nodes.

View all citing articles on Scopus

View full text

Ranking the spreading ability of nodes in complex networks based on local structure

Highlights

Abstract

Introduction

Section snippets

Centrality measures

Our proposed local structural centrality

Experimental setup

Results

Conclusion and discussions

Acknowledgments

Physica A

Physica A

Physica A

Physica A

Physica A

Phys. Lett. A

Social Networks

Physica A

Physica A

Infectious Diseases of Humans: Dynamics and Control

The mathematics of infectious diseases

SIAM Rev.

Epidemic spreading in scale-free networks

Phys. Rev. Lett.

Statistical mechanics of complex networks

Rev. Modern Phys.

The small world yields the most effective information spreading

New J. Phys.

Adaptive model for recommendation of news

Europhys. Lett.

Statistical physics of social dynamics

Rev. Modern Phys.

Identification of influential spreaders in complex networks

Nat. Phys.

Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach

Europhys. Lett.

Leaders in social networks, the delicious case

PLoS One

Quantifying the influence of scientists and their publications: distinguishing between prestige and popularity

New J. Phys.

The centrality index of a graph

Psychometrika