Identifying influential spreaders in complex networks based on limited spreading domain

Abstract

In recent years, the problem of influential spreader identification in complex networks has attracted extensive attention as its fundamental role in social network analysis, rumor controlling, viral marketing and other related fields. Centrality measures that consider different scales of neighborhood are commonly utilized for ranking node influence. The 2-hop neighborhood of the target node is deemed a suitable evaluation metric. However, as the network scale expands, only considering 2-hop neighborhood is overly restrictive. Furthermore, the interconnections among nodes are often disregarded. In this article, a new method named Limited Spreading Domain (LSD) is proposed to identify influential spreaders. LSD defines the target node’s 2-hop neighborhood as basic domain and takes the neighbors who are 3–6 hops away from target node as extended domain. The influence of target node is modeled as diffusion along the paths with limited length in basic domain and extended domain. A series of experiments are conducted in eight real complex networks and results demonstrate that LSD outperforms common centralities in terms of accuracy, stability,distinguishability and scalability.

Keywords

Complex network influential spreaders SIR model centrality measure

1 Introduction

Spreading phenomena are ubiquitous in complex networks, such as the diffusion of viruses within crowds, the propagation of specific information across social media platforms, the traffic flow in cities, etc. Nodes with great influence often play a key role in expanding dissemination or turning public opinion [1]. Therefore it is essential to identify influential spreaders in order to discover opinion leaders, control rumors or infectious diseases, promote products and more. A series of methods have been proposed in the field of complex networks to discover nodes with strong spreading ability [2].

To discover influential nodes, the first step is to determine an appropriate method for estimating a single node’s spreading potential within the network. Centrality is a widely used metric for evaluation. The difference of various centralities, such as degree, semi-local centrality, closeness, primarily stem from the different scale of neighborhoods they consider. Consequently, their performance varies accordingly [3]. In [4], a centrality considering the number of neighbors within a 2-hop distance from the target node is concluded to be a good metric as it balances the efficiency and effectiveness. Ref. [5] develops a method to discover the optimal evaluation radius of the neighborhood for a given network. The aforementioned studies indicate that the performance of the method in estimating nodes’ influence is influenced by the scale of neighborhood considered. However, the 2-hop neighborhood may not always be the optimal choice. For example, the efficacy of centralities is contingent upon the probability of spreading [6]. Semi-local centrality and closeness centrality, which take into account a larger scale of neighborhood, are more suitable for large spreading probabilities [7]. There are other factors that can impact the performance of centralities, such as taking into account the interconnectivity among neighbors [8].

Inspired by above observations, we propose an effective method for estimating nodes’ influence and identifying influential ones in complex networks. Firstly, we hold the view that, in general, the influence of each node is primarily confined to its 2-hop neighbors, and it is imperative to accurately calculate this aspect of influence. We define the target node’s 2-hop neighborhood as basic domain. At the same time, we also consider the scenario where the influence of the target node spreads further through the propagation of certain neighbors within a 2-hop range. Therefore, we consider the nodes within a 3–6 hop range from the target node as extended domain. The influence of target node is comprised of basic domain influence and extended domain influence, which can be adjusted by a tunable parameter. The Susceptible-Infected-Recovered (SIR) model is employed to obtain the simulation results that serve as the ground truth of spreading. Experimental results in eight real complex networks demonstrate that the proposed method is more accurate and stable in estimating nodes’ influence and identifying influential ones. Our approach enables a more precise differentiation of nodes’ impact compared to common centralities. Our approach enables a more precise differentiation of nodes’ influence.

The main contributions of this article are as follows:

A novel method for identifying influential nodes based on local structure is proposed, which defines the target node’s 2-hop neighborhood as basic domain and takes the neighbors who are 3-6 hops away from the target node as extended domain.

Different evaluation details are adopted for local domain and extended domain to achieve a balance between evaluation accuracy and calculation time.

Experiments in eights real complex networks show that the proposed method has better accuracy, discrimination and scalability with acceptable running time. It performs better under inhomogeneous spreading probabilities.

The rest of this article is outlined as follows: Section 2 presents a review of related research on influence evaluation. Section 3 gives a concise overview of some common centralities for comparison. In Section 4 we explicate the details of our approach. Section 5 focuses on the experimental results. Finally, in Section 6, we summarize the core research contents and draw conclusions.

2 Related work

The research fields of complex networks such as community detection [9–10], information dissemination [1], and identification of influential nodes [2], have been increasingly emphasized in recent years. The spreading ability of a node can be considered as its influence. Centralities, which indicate the topological significance of nodes, are naturally regarded as measures of their spreading ability. Degree is a widely used local centrality measure that quantifies the number of directly connected neighbors to a target node [11]. Although simple to calculate, it may be misleading in some cases due to the limited topology information considered [12]. The research findings suggest that expanding the scale of the target node’s neighborhood can be a feasible approach to improving the accuracy of identifying influential spreaders [13, 14]. Semi-local centrality, which expands the neighborhood scale to 4 hops, is a typical example. Other centralities based on degree consider additional network properties such as clustering coefficient [15], closeness among neighbors [16], structural hole [17], or edge weight [18].

Commonly used global centralities, such as betweenness [15], closeness [19], pagerank [20], and Leaderrank [21], consider the node’s position in the entire network and are effective in many scenarios. However, these measures have high computational complexity and require knowledge of the whole network structure [22]. Kshell centrality is a widely used and simple global centrality measure, but its poor distinguishability due to the limited number of rank values assigned to many nodes has been recognized [8, 23]. To address this issue and enhance its performance, various improvements have been proposed [24 –26]. The concept of gravity formula and information entropy has been used more and more frequently in influence evaluation in recent years. Ref. [27] combines information entropy with kshell, which effectively enhancement the distinguishability ability of kshell. Gravity centrality is a novel centrality measure that integrates both local and global information of a node to accurately capture the interplay among nodes [28].

With the expansion of network scale, obtaining a complete network structure that global centralities need becomes increasingly challenging. In such circumstances, methods based on local structures are proposed as an alternative. Furthermore, certain local centralities, such as semi-local centrality, exhibit comparable or even superior performance to global centralities in complex networks.

Recently, it has been suggested that a neighborhood within 2 hops is an appropriate local topology scale for evaluating node influence. However, this conclusion may not always hold true as the spread of influence depends on various factors. When the spreading probability is large, the influence of the target node will propagate far beyond two hops. What’s more, connections among nodes should be considered. However, expanding the scale or considering more factors inevitably leads to an increase in computational complexity, which is not conducive to large-scale networks. Therefore, this article aims to propose a method that can balance accuracy and efficiency.

3 Preliminaries

In this section, some common centralities are introduced briefly, including degree, semi-local centrality, betweenness, closeness and kshell. As the 2-hop neighborhood of a target node is often crucial in many networks, we also define nearest and next-nearest centralities here. Two novel methods based on gravity and entropy are also introduced here. The complexity of all these methods is listed in Table 1.

Table 1
The computational complexity of nine commonly used methods

Types Method Full Name Complexity

Local Centrality DC Degree Centrality O (n) n is the number of nodes

NC Nearest and next nearest neighbor Centrality is the average degree of the network

SLC Semi-local Centrality

Global Centrality BC Betweenness Centrality O (n³)

CC Closeness Centrality O (n³)

PR PageRank O (tn²) t represents the number of iterations

GC Gravity Centrality is the average shortest distance of the network

KS Kshell Decomposition O (n)

IKS Improved Kshell Decomposition m is the number of edges

Types	Method	Full Name	Complexity
Local Centrality	DC	Degree Centrality	O (n)	n is the number of nodes
	NC	Nearest and next nearest neighbor Centrality		is the average degree of the network
	SLC	Semi-local Centrality
Global Centrality	BC	Betweenness Centrality	O (n³)
	CC	Closeness Centrality	O (n³)
	PR	PageRank	O (tn²)	t represents the number of iterations
	GC	Gravity Centrality		is the average shortest distance of the network
	KS	Kshell Decomposition	O (n)
	IKS	Improved Kshell Decomposition		m is the number of edges

Consider a complex network G = (V, E) that is undirected and unweighted, consisting of n nodes in V and m edges in E.

(1) Degree centrality (DC) captures the 1-hop neighborhood by quantifying the number of nodes directly connected to the target node [3].

(2) Nearest and next nearest neighbor centrality (NC) includes the 2-hop neighborhood of the target node. The definition is as follows:

$NC (u) = | N (u) | + \sum_{v \in N (u) ∖ u} | N (v) |$ (1) where N (u) contains node u’s 1-hop neighbors.

(3) Semi-local centrality (SLC) incorporates a 4-hop neighborhood and is proposed as a trade-off between degree and global centralities [13].

$SLC (u) = \sum_{v \in N (u)} \sum_{w \in N (v)} | NN (w) |$ (2) where N (u) includes u’s all 1-hop neighbors, NN (w) is w’s neighbors within 2 hops.

(4) Betweenness centrality (BC) is a global metric that measures the importance of a node based on its ability to connect other nodes through the shortest paths. s_st represents the shortest paths’ number between any two nodes except the target node. s_st (u) means the nunber of shortest paths between all other nodes that node u is included [16].

$BC (u) = \sum_{s \neq u \neq t \in V} s_{st} (u) / s_{st}$ (3)

(5) Closeness centrality (CC) quantifies the distance from the target node to other nodes [16]. It defines as follows:

$CC (u) = \sum_{v \in V ∖ u} 2^{- d_{uv}}$ (4) where d_uv donates the length of shortest path from target node u to any other node v.

(6) Kshell centrality (KS) is obtained by kshell decompositon [8]. Initially kshell decomposition method removes all the nodes with degree DC = 1. When the degree of nodes remained is all larger than 1, this step stops and all the removed nodes are assigned with kshell value KS = 1. Then kshell decomposition iteratively removes nodes with DC = 2 and assigns them with KS = 2 in a similar way. Repeately perform this procedure until all the nodes in G are assigned to one of the KS values.

(7) PageRank (PR) is a well-established algorithm for sorting web pages [20], which can be used to solve the node importance sorting problem in complex networks.

${PR}_{v}^{t} = \frac{1 - α}{n} + α \sum_{u \in N_{v}} \frac{{PR}_{u}^{t - 1}}{k_{u}}$ (5)

Where n is the number of nodes, N_v is the number of v’s neighbors, k_u is the number of nodes pointed by u.

(8) Gravity Centrality (GC) is proposed based on gravity formula: the gravitational force between objects is related to mass and distance [28]. In complex networks, the mass of node u can be represented as |N (u) |, which means the degree of u. The distance between node u and v can be expressed as d_uv, which is the length of the shortest path connecting these nodes. is the average shortest distance of the network.

$G C (u) = \sum_{v \neq u, d_{u v} \leq 〈 d 〉 / 2} \frac{| N (u) | | N (v) |}{d_{u v}^{2}}$ (6)

(9) Improved k-shell (IKS) divides the nodes into different shells according to the node information entropy [29]. The node entropy is defined as:

$e (u) = - \sum_{v \in N (u)} I_{v} \cdot ln I_{v}$ (7)

$I_{v} = \frac{| N (v) |}{\sum_{w \in V} N (w)}$ (8)

Where N (v) denotes the 1-hop neighbors of node v.

4 Our method

We already know that 2-hop neighborhood of target node is regarded as a good choice for measureing nodes’ influence in most networks [4], which implies that nodes with a higher number of neighbors within 2 hops exhibit greater potential for information dissemination. However, relying solely on the number of neighbors within 2 hops to measure nodes’ influence is too restrictive in rapidly expanding networks. The target node’s influence will spread far beyond 2 hops with the increase of spreading probability. Expanding the scope of evaluation can enhance ranking accuracy, it may also lead to an increase in computational complexity. Closeness Centrality, which assumes that a node’s influence spreads along the shortest paths to all the nodes it can reach, performs well at large spreading probabilities. However, its computational complexity is unacceptable for large-scale networks. In addition, the connectivity of neighbors within a certain scale should also be taken into consideration, as it directly affects their probability of being activated by the target node. In short, our aim is to propose a method that can effectively expand the scope of evaluation, take into account the interconnections among nodes within this scope, while minimizing computational complexity.

Taking inspiration from the aforementioned opinions, we raise a method named Limited Spreading Domain (LSD for short). As illustrated in Fig. 1, this method defines the neighborhood within 2 hops of the target node as Basic Domain (BD for short). The influence of a target node u ∈ V within basic domain Inf_BD (u) is estimated by summing up its activation probabilities to all u’s 1-hop and 2-hop neighbors as follows:

Fig. 1

The influence evaluation scope of target node u. The area within the solid circle represents the basic domain, and the area within the dotted circle represents the extended domain.

$\begin{matrix} {Inf}_{BD} (u) \\ = 1 - \prod_{{path}_{u \to w} \in {PATH}_{u \to T (u)}} (1 - Inf ({path}_{u \to w})) \end{matrix}$ (9) where T (u) is the neighbors of u within 2 hops, path_u→w donates a path from u to w with 1 hop or 2 hop. ${PATH}_{u \to T (u)}$ represents a collection of all paths from node u to node set T (u). Inf (path_u→w) means the probability that u activates w through this path. Inf (path_u→w) is calculated as follows:

$Inf ({path}_{u \to w}) = {\begin{matrix} p_{uw}, w \in N (u) \\ p_{uv} p_{vw}, v \in N (u), w \in N (v) ∖ u \end{matrix}$ (10)

If w is conncted to u directly, then Inf (path_u→w) = p_uw. If w is connected to u by an intermediate node v, then Inf (path_u→w) = p_uvp_vw. The set of nodes directly connected to u is denoted as N (u), while the set of neighbors of node v excluding u is represented by N (v) ∖ u. p_uv is the spreading probability from node u to node v.

In addition to basic domain, we also consider the neighbors of target node in a wider scope, which is referred to as Extended Domain (ED for short). Firstly we consider the scope that the neighbors can be reached in 3 or 4 hops from the target node u. The number of nodes located at a distance of 3 or 4 hops away from the target node is typically large, and accurately calculating their influence on other nodes when activated by the target node requires significant time investment. For the sake of simplicity, we regard their influence in the basic domain as their approximate influence. As a result, the extended domain encompasses the neighborhood within 3–6 hops from the target node. These remote nodes are typically influenced by the secondary spread caused by neighboring nodes of u. The nodes can be reached in 3 or 4 hops (the gray nodes in Fig. 1) are the neighbors or neighbors’ neighbors of node w, w is the 2-hop neighbor of target node u. Therefore node u’s extended domain influence ${Inf}_{ED} (u)$ can be calculated as:

$\begin{matrix} {Inf}_{ED} (u) \\ = p_{uv} p_{vw} \sum_{v \in N (u)} \sum_{w \in N (v)} \sum_{q \in NN (w), q \notin N (u)} {Inf}_{BD} (q) \end{matrix}$ (11) where p_uv is the spreading probability from node u to node v, p_vw is the spreading probability from node v to node w. N (u) denotes the set of all 1-hop neighbors of node u. NN (w) is defined as the set of all neighbors that are either 1 hop or 2 hops away from node w.

In summary, the calculation formula for target node u’s influence is:

$Inf (u) = λ \cdot {Inf}_{BD} (u) + {Inf}_{ED} (u)$ (12)

λ is a tunable parameter. The influence ratio between BD and ED can be adjusted by λ, thereby impacting the evaluation results.

There are specific regulations that can be followed when making a selection for λ. Given the known spreading probability, we derive the baseline parameter $\tilde{λ}$ using the following formula:

$\tilde{λ} = 10^{Round (\log_{10} ({\bar{Inf}}_{ED} / {\bar{Inf}}_{BD}))}$ (13) where the term ${\bar{Inf}}_{BD}$ and ${\bar{Inf}}_{ED}$ denote the average influence of all nodes in BD and ED respectively in the network. $\tilde{λ}$ indicates the difference in order of magnitude between average influence in BD and ED.

The selection of λ should be explored by varying the order of magnitude based on $\tilde{λ}$ .

Algorithm 1 presents the pseudocode for LSD method, where N (u) refers to all the 1-hop neighbors of node u and NN (w) refers to the set of w’s neighbors within 2 hops. Inf (u) represents node u’s total influence. Finally according to Inf (u), we get the ranking list.

According to Algorithm 1, LSD needs to traverse the neighbors within a radius of two hops for each node to compute its Inf_BD (u), and this procedure costs (lines 1–4). is the averge degree of the network. The next step involves traversing nodes within a 2-hop range to identify the neighbors’ neighbors of node u, and the complexity of this part is still . For each node w ∈ N (v) (line 11), the complexity of line 12 and line 13 is O (1) owe to the pre-stored value of NN (w) and Inf_BD. Hence the complexity of lines 5–17 is , and the total complexity of LSD amounts to . The complexity of LSD is the same as SLC, but less than BC and CC which is O (n³).

Algorithm 1: LSD method
Input: The network G, the spreading probability p
of SIR model, λ
Output: the ranking result
1. For each node u in G do
2. Find u’s neighbors within 2 hops and put them in NN (u)
3. Calculate Inf_BD (u)
4. end for
5. For each node u in G do
6. Initialize Inf_ED (u) =0, Inf_tmp (u) =0,
Inf (u) =0, has_visited =∅.
7. Put u to has_visited
8. Find u’s neighbors with 1 hop and put them to
N (u) and has_visited
9. For each node v ∈ N (u)
10. Find all 1-hop neighbors for v and put them to N (v)
11. For each node w ∈ N (v)
12. NN (w) = NN (w) - has_visited
13. Inf_tmp (u) = Inf_tmp (u) + ∑_q∈NN(w)Inf_BD (q)
14. End for
15. End for
16. Inf_ED (u) = p_uv * p_vw * Inf_tmp (u)
17. Inf (u) = λ * Inf_BD (u) + Inf_ED (u)
17. End for
18. Sort all nodes in G in descending order according to
the value of Inf (u)
19. Output the ranking result

Table 2

The network characteristics of eight real networks

Network	n	m		H		C	r	$\hat{p}$
Netscience [30]	379	914	4.82	1.66	4.71	0.74	–0.08	0.125
Email [31]	1133	5451	9.62	1.94	3.6	0.22	0.078	0.054
Blog [32]	3982	6803	3.42	4.04	6.25	0.28	–0.13	0.073
Router [33]	5022	6258	2.59	5.5	6.45	0.01	–0.14	0.073
Lastfm [30]	7532	26749	7.1	3.47	5.67	0.21	0.02	0.041
Amazon [34]	8733	15329	3.51	3.74	7.32	0.15	–0.18	0.076
PGP [35]	10680	24340	4.56	4.15	7.49	0.27	0.24	0.053
Delicious [30]	13844	25751	3.72	14.33	4.44	0.09	–0.16	0.018

5 Experimental results

5.1 Experimental environment and datasets

The experimental hardware environment consists of an Intel(R) Core(TM) i7-6567U CPU with 7.58 GB of memory, while the software environment is Matlab R2013a.

In this article, LSD is compared to the centralities introduced in Section 3 in eight real complex networks. The detailed topological characteristics of these networks are summarized in Table 1. The characteristics include node number n, edge number m, average degree , clustering coefficient C, average shortest distance , assortative coefficient r, degree heterogeneity H (defined as) and epidemic threshold $\hat{p}$ (defined as).

5.2 SIR model

Due to the difficulty in tracking the actual process of influence spreading, simulations based on spreading models are generally used to determine the influence of a specific node or set of nodes. The SIR (Susceptible-Infected-Recovered) model is a well-known epidemic model that has also been widely applied to simulate the diffusion of information or influence, particularly in the realm of node influence evaluation. Therefore, the SIR model is utilized in this article, and the outcomes produced by numerous simulations based on SIR typically serve as the benchmark for evaluating different methods.

In the initial stage, most nodes are in Susceptible (S) state except for the target node, which is in Infected (I) state. When the spreading starts, at each timestamp, each node in state I will visit its 1-hop neighbors one by one and identify the status of these neighbors. Upon encountering a neighbor in status S, it will attempt to infect this neighbor with probability p. p represents the probability of successful infection, which is also called spreading probability. The infected nodes then enter Recovered (R) state with a probability μ. The value of μ is explicitly assigned as 1 for the sake of simplicity. The recovered nodes are immune to both infection and transmission. This setting of μ is also more consistent with the characteristics of information or influence dissemination, as this process typically does not recur after message reception or influence exertion. Recovered nodes will neither be infected by other nodes nor infect others. The process terminates when no new infections occur in the network.

In order to reduce uncertainty, the entire process needs to be simulated for many times. In our experiments, we conduct 5000 simulations for each node in the network, and the influence of each node is determined by the average number of nodes in the final state R for all the simulations.

The spreading probability p in SIR model exerts a profound impact on both the spreading speed and scope. It is necessary to pre-assign a p value to each edge within the network. A typical approach is to assign a uniform value manually to all edges. Small values are typically utilized to avoid wide spreading caused by a high probability of diffusion, which renders the origin irrelevant [8]. Refer to general practices we set p ∈ (0, 0.1] in our work. It cannot be overlooked that each network has a specific value, known as the epidemic threshold $\hat{p}$ , which holds significant importance. The value of $\hat{p}$ is considered to be related with the scale and the structure of the network [36]. When $p > \hat{p}$ , mass propagation will occur in the network.

5.3 Evaluation metric

(1) Kendall coefficient τ

Kendall coefficient τ is usually used to evaluate the similarity of two sorted lists with the same length. It is widely adopted to measure the accuracy of various influence evaluation methods. Consider two lists X and Y, which denote node lists ranked by a specific centrality and SIR simulations respectively. The rank vlues of node i and j in X are x_i and x_j, and in Y are y_i and y_j respectively. For pairs (x_i, y_i) and (x_j, y_j), if (x_i - x_j) (y_i - y_j) > 0, then they are considered as concordant. if (x_i - x_j) (y_i - y_j) < 0, they are considered as discordant. The number of concordant and discordant pairs are represented with n_c and n_d respectively. Then τ is calculated as:

$τ = \frac{2 (n_{c} - n_{d})}{n (n - 1)}$ (14) where n denotes the nodes’ number of the network. The value range of τ is between+1 and –1. The centrality measure with a τ closer to 1 is considered more accurate.

(2) M monotone function

M monotone function [37] is often used to reflect the measure’s distinguishability. The calculation method is as follows:

$M (R) = {[1 - \frac{\sum_{r \in R} n_{r} (n_{r} - 1)}{n (n - 1)}]}^{2}$ (15)

where R represents the ranking list obtained by a certain measure, r represents a centrality value in the ranking list, n is still the nodes’s number of the network, n_r is the occurrence number of element r in the ranking list. The value range of M is between 0 and 1, where M = 1 implies that the network’s nodes can be distinguished totally, and M = 0 implies that the centrality value of each node is the same, and cannot be distinguished in any manner.

5.4 Experimental results

(1) Parameter λ

According to the value of $\tilde{λ}$ under different spreading probabilities, we explore the optimal value of λ for each network by adjusting it from 10^–1 to 10³ and observe its impact on LSD’s performance. The Kendall coefficient τ values between ranking results produced by LSD with different λ and the ranking result produced by SIR model in eight real networks at different spreading probabilities p are presented in Fig. 2. In each of the figures, the epidemic threshold $\hat{p}$ of this network is represented by the dotted line, while the dashed line corresponds to the value of $\tilde{λ}$ . We can see that for all the networks, when $p < \hat{p}$ , the optimal value of λ is typically equivalent to or an order of magnitude greater than $\tilde{λ}$ . LSD can achieve the best effect with $λ = \tilde{λ}$ at $p = \hat{p}$ . While when $p > \hat{p}$ , λ should be an order of magnitude smaller than $\tilde{λ}$ . λ = 100 is almost the best choice for all the networks at $p = \hat{p}$ . In Netscience, Email, Blog and Amazon, the optimal τ values of LSD can be achieved for almost all spreading probabilities with λ = 100.

Fig. 2

The Kendall coefficient τ values between ranking results produced by LSD with different λ and the ranking results produced by SIR model in eight real networks at various spreading probabilities p. In each of the figures, the epidemic threshold $\hat{p}$ of this network is represented by the dotted line and the dashed line corresponds to the value of $\tilde{λ}$ .

(2) Effectiveness in ranking the nodes

The effectiveness of LSD is evaluated by comparing its τ values with those of DC, NC, SLC, BC, CC, KS, GC and IKS under various p. The parameter λ in LSD is set to be 100 in all the networks as we have found that λ = 100 provides the optimal result on most spreading probabilites.

Based on the results shown in Fig. 3, it can be concluded that LSD outperforms other centrality measures under all spreading probabilities in Netscience, Blog, Router and Amazon. In Email, Lastfm, PGP, the situation is slightly complicated. When p is small ( $p < \hat{p}$ ), LSD performs better than other centralitlites. As p continues to increase, the performance of LSD is similar to SLC or GC. In Delicious, the performance of LSD is similar to CC or GC. On the whole, LSD has advantages under most spreading probabilities in ranking the influence of nodes. It exhibits greater resilience under varying spreading probabilities.

Fig. 3

The Kendall coefficient τ values between ranking results produced by DC, NC, SLC, BC, CC, KS, GC, PR, IKS, LSD with λ = 100 and the ranking results produced by SIR model in eight real networks at various spreading probabilities p. The epidemic threshold $\hat{p}$ of this network is represented by the dotted line in each of the figures.

(3) Identifying influential nodes

In many cases, nodes with great influence have more important values. Therefore, we assess the efficacy of LSD to identify top-L (L varing from 1 to 100) influential nodes. The average number of nodes infected by top-L influential nodes which are measured by DC, NC, SLC, BC, CC, KS, PR, GC, IKS LSD (λ = 100) in eight real networks when $p = \hat{p}$ are shown in Fig. 4. We can see that the infected nodes’ number of top-L influential nodes selected by LSD are largest on most L in Netscience, Email, Blog, Lastfm, PGP. NC and SLC are the comparable centralities while they are not as stable as LSD. KS varies significantly in different networks, which implies it’s more sensitive to network structure. In Netscience, Blog and PGP, the divergence of different methods about the most influential nodes is relatively small. While in Lastfm and Amazon, the divergence is large.

Fig. 4

The average number of nodes infected by top-L influential nodes which are measured by DC, NC, SLC, BC, CC, KS, GC, PR, IKS and our method LSD ( $λ = 100$ ) in real networks when $p = \hat{p}$ .

(4) Distinguishability

In this part, we aim to compare the distinguishability of various methods. Distinguish-ability of a method mainly depends on whether this method can distinguish the influence of different nodes. If multiple nodes are assigned the same rank value, they will be deemed to have same influence.

Table 3 presents the M values of lists ranked by DC, NC, SLC, BC, CC, KS, PR, GC, IKS, LSD (λ = 100) when $p = \hat{p}$ in eight networks. The IKS algorithm itself posesses the capability to circumvent identical rank values, resulting in an IKS value of 1. We can observe that all the M values of LSD are larger than 0.99. It certifies that LSD has superior distinguishability. KS performs worst in all networks as it assigns too many nodes the same value.

Table 3

The M values of lists ranked by DC, NC, SLC, BC, CC, KS, GC, PR, IKS and LSD (λ = 100) when $p = \hat{p}$ in eight networks

Network	DC	NC	SLC	BC	CC	KS	GC	PR	IKS	LSD
Netscience	0.764	0.970	0.994	0.339	0.994	0.642	0.993	0.994	1	0.995
Email	0.887	0.999	0.999	0.940	0.983	0.809	0.998	0.998	1	0.999
Blog	0.565	0.974	0.997	0.400	0.855	0.467	0.997	0.987	1	0.998
Router	0.289	0.921	0.995	0.298	0.996	0.069	0.927	0.972	1	0.996
Lastfm	0.792	0.989	0.999	0.832	0.999	0.728	0.999	0.988	1	0.999
Amazon	0.534	0.974	0.997	0.485	0.998	0.453	0.982	0.974	1	0.998
PGP	0.619	0.959	0.999	0.510	0.999	0.481	0.999	0.983	1	0.999
Delicious	0.212	0.993	0.993	0.154	0.993	0.200	0.986	0.915	1	0.993

In order to further examine the distinguishability of each measure in more detail, we show the frequency distribution of ranks generated by DC, NC, SLC, BC, CC, KS, PR, GC, IKS and LSD in Fig. 5. Frequency of a rank refers to the number of nodes that are assigned this rank by the centrality measure. The poor performance of KS in each network is not unexpected due to its limited range of rank values. Many nodes are assigned identical KS values, rendering their influence indistinguishable. DC also suffers from this issue, which results in the influence measured by DC is not well distinguished. SLC and LSD have more rank values which implies that they can distinguish nodes’ influence better. Especially in SLC and LSD, the frequency of top-ranked nodes is 1, which indicates these nodes are seperated completely. It should be noted that LSD outperforms SLC in distinguishing nodes at larger rank values, indicating its superior performance under such conditions.

Fig. 5

The frequency distribution of ranks generated by DC, NC, SLC, BC, CC, KS, GC, PR, IKS and LSD (λ = 100) when $p = \hat{p}$ in eight networks.

(5) Effectiveness under inhomogeneous spreading probabilities

In practice, the strength of relationships between nodes varies according to their level of intimacy, thus affecting the spreading probability between them. LSD takes into account the different probabilities when calculating the spreading paths. To verify the performance of LSD under inhomogeneous p, we compared the τ values of LSD with other methods in Table 4. The specific approach involves assigning a randomly generated value ranging from 0 to 0.1 to each edge within the network, which represents the spreading probability between these two nodes in SIR model. Table 4 reveals that LSD exhibits the much larger τ value than all the other methods in all datasets except Delicious. In Delicious, LSD performs slightly worse than SLC. This experiment demonstrates that the LSD method has significant advantage in networks with inhomogeneous spreading probabilities.

Table 4

The τ values of all the methods in networks with inhomogeneous spreading probabilities

Network	DC	NC	SLC	BC	CC	KS	GC	PR	IKS	LSD
Netscience	0.636	0.667	0.542	0.304	0.363	0.572	0.681	0.546	0.311	0.923
Email	0.764	0.836	0.837	0.625	0.761	0.774	0.813	0.683	0.242	0.939
Blog	0.504	0.553	0.485	0.389	0.423	0.467	0.613	0.414	0.549	0.899
Router	0.364	0.515	0.479	0.354	0.424	0.235	0.543	0.251	0.517	0.864
Lastfm	0.535	0.706	0.768	0.371	0.669	0.566	0.724	0.390	0.645	0.885
Amazon	0.528	0.580	0.519	0.439	0.462	0.480	0.665	0.507	0.563	0.889
PGP	0.485	0.632	0.643	0.332	0.556	0.454	0.680	0.320	0.618	0.733
Delicious	0.350	0.804	0.806	0.290	0.774	0.340	0.813	0.297	0.785	0.793

(6) Running Time

In small-scale datasets, there is no significant difference in the running time for each method. Moreover, low complexity algorithms such as DC, KS, GC and IKS exhibit relatively shorter running times across different datasets. Therefore we only compare the running time of SLC, BC, CC, LSD in four larger datasets. Fig. 6 shows the running time of these methods. The computational time of LSD is demonstrated to be comparable to that of SLC in Fig. 6, as they share the same level of time complexity. However, LSD runs slightly longer than SLC. In contrast, BC and CC have higher time complexity than SLC and LSD, resulting in much longer computational time.

Fig. 6

The running times of SLC, BC, CC, LSD in Lastfm, Amazon, PGP and Delicious.

6 Conclusion and future work

Identifying influential spreaders is a fundamental task in the field of complex networks. Centralities with different scale of neighborhood are proposed successively to evaluate the nodes’ capacity of spreading. Among them centrality that considers the number of 2-hop neighborhood is considered to be a good metric as its good measurement effect and moderate complexity. When evaluating influence, it is important to consider not only the number of neighbors but also their connectivity. In many cases, accuracy can be improved by taking a broader scope of neighbors into account. We propose the LSD method to identify influential spreaders by considering the 2-hop neighborhood as the basic domain and selecting neighbors within a 3–6 hop range from the target node as an extended domain. By adjusting λ, the ratio of basic domain influence and extened domain influence could be adjusted to to suit different spreading characteristics at varying probabilities. We conduct experiments on eight real networks and demonstrate the rules of discovering the optimal λ. Our results show that, compared to DC, NC, SLC, CC, BC, KS, PR, GC and IKS, LSD can more accurately rank node influence under most spreading probabilities and identify top influential nodes in these networks. We evaluate the distinguishability of various centralities using both M function and rank frequency distribution, and our findings demonstrate that LSD exhibits significant advantages. In addition, we also demonstrate that LSD has significant advantages under the inhomogeneous spreading probabilities, and the running time is acceptable.

In the future, we will conduct experiments on more networks and explore the effect of different characteristics of network, such as degree distribution, clustering coefficient or community structure, on the centralities with different scale of neighborhood. What’s more, the performance of different centralities under different spreading models will be further discussed.

Footnotes

Acknowledgments

This work was funded by Scientific Research Program of Tianjin Education Commission (2021SK141).

References

Shang

, Zhang

, Li

, et al., Identifying influential nodes: A new method based on network efficiency of edge weight updating, Chaos 31(3) (2021), 033120.

Zhang

, Fu

, Cheng

, et al., Identifying multiple influential spreaders based on maximum connected component decomposition method, Physica A 571 (2021), 125791.

and Ma

, A robust method to discover influential users in social networks, Soft Comput 23 (2019), 1283–1295.

Liu

, Tang

, Zhou

, et al., Identify influential spreaders in complex networks, the role of neighborhood, Physica A 452 (2016), 289–298.

, Gao

and Wang

Y.F.

, Finding the proper node ranking method for complex networks, 2018.

Lou

and Tang

, Mining structural hole spanners through information diffusion in social networks, In Proceedings of the 22nd International Conference on World Wide Web (WWW 2013), ACM Press, New York, 2013, 825–836.

and Ma

, Identifying and ranking influential spreaders in complex networks with consideration of spreading probability, Physica A (564) (2017), 312–330.

Kitsak

, Gallos

L.K.

, Havlin

, et al., Identification of influential spreaders in complex networks, Nature Physics 6(11) (2011), 888–893.

Al-Andoli

, Deep autoencoder-based community detection in complex networks with particle swarm optimization and continuation algorithms, &– & fuzzy systems: Applications in Engineering and Technology 40(3) (2021), 4517–4533.

10.

Mohammed Nasser Al-Andoli , Shing Chiang Tan and Wooi Ping Cheah , Distributed parallel deep learning with a hybrid backpropagation-particle swarm optimization for community detection in large complex networks, Information Sciences 600 (2021), 94–117.

11.

Kumar

and Panda

B.S.

, Identifying influential nodes in Social Networks: Neighborhood Coreness based voting approach, Physica A 553 (2020), 124215.

12.

Wen

and Jiang

, Identifying influential nodes based on fuzzy local dimension in complex networks, Chaos Solitons & Fractals 119 (2019), 332–342.

13.

Chen

, Lü

, Shang

, et al., Identifying influential nodes in complex networks, Physica A 391(4) (2012), 1777–1787.

14.

, Zhang

, Guo

, et al., A novel centrality measure for identifying influential nodes based on minimum weighted degree decomposition, International Journal of Modern Physics B 24 (2021), 1–19.

15.

Kamal , Berahmand , Asgarali , et al., A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks, Chaos, Solitons & Fractals 110 (2018), 41–54.

16.

Gao

, Ma

, Chen

, et al., Ranking the spreading ability of nodes in complex networks based on local structure, Physica A 403 (2014), 130–147.

17.

, Cao

, Liu

, et al., Identifying key nodes based on improved structural holes in complex networks, Physica A 486 (2017), 318–327.

18.

Shang

, Zhang

, Li

, et al., Identifying influential nodes: A new method based on network efficiency of edge weight updating, Chaos 31(3) (2021), 033120.

19.

, Zhao

, Xiong

, et al., A novel measure of identifying influential nodes in complex networks, Physica A 523 (2019), 488–497.

20.

Page , Lawrence , Brin , et al., Page, L. et al.: The PageRank citation ranking: Bringing order to the web, stanford digital libraries working paper, 1998.

21.

Lü

, Zhang

Y.C.

, Yeung

C.H.

, et al., Leaders in social networks, the Delicious case, Plos One 6(6) (2011), e21202.

22.

Zhang

, Fu

, Cheng

, et al., Identifying multiple influential spreaders based on maximum connected component decomposition method, Physica A 571 (2021), 125791.

23.

Jiang

, Zhao

, Ge

, et al., An efficient algorithm for mining a set of influential spreaders in complex networks, Physica A 516 (2019), 58–65.

24.

Cai

and Zhou

, K-layer for influencer identification in complex networks, Journal of Physics Conference Series 1453 (2020), 012020.

25.

Qiu

, Zhang

and Tian

, Ranking influential nodes in complex networks based on local and global structures, Applied Intelligence 51(7) (2021), 4394–4407.

26.

Yang

and Xiao

, , An improved gravity model to identify influential nodes in complex networks based on k-shell method, Knowledge-Based Systems 227 (2021), 107198.1–107198.11.

27.

Wang

, Li

, Guo

, et al., Identifying influential spreaders in complex networks based on improved k-shell method, Physica A 554 (2020), 124229.

28.

Qzab

, Bin Shuai a b c d Person Envelope and Min

, A novel method to identify influential nodes in complex networks based on gravity centrality, Information Sciences (2022), 98–117

29.

Wang

, Li

, Guo

, et al., Identifying influential spreaders in complex networks based on improved k-shell method, Physica A (2020), 124229.

30.

Rossi

R.A.

and Ahmed

N.K.

, The Network Data Repository with Interactive Graph Analytics and Visualization, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, Palo Alto, 2015, 1–2.

31.

Liu

J.G.

, Ren

Z.M.

and Guo

, Ranking the spreading influence in complex networks, & & Its Applications 392(18) (2014), 4154–4159.

32.

Bae Kim

, et al., Identifying and ranking influential spreaders in complex networks by neighborhood coreness, Physica A 395 (2014), 549–559.

33.

CAIDA. Skitter Router Adjacencies, 2003. https://catalog.caida.org/dataset/skitter_router_adjacencies

34.

Rozemberczki

, Allen

and Sarkar

, Multi-scale attributed node embedding, Journal of Complex Networks 9(1) (2021), 1–22. [34] J. Yang and J. Leskovec, Defining and Evaluating Network Communities Based on Ground-Truth, IEEE International Conference on Data Mining, IEEE Computer Society (2012), 1–8.

35.

Boguñá

, Pastorsatorras

, Díazguilera

, et al., Models of social networks based on social distance attachment.[J], Physical Review E Statistical Nonlinear & Soft Matter Physics 70(2) (2004), 056122.

36.

Zhang

, Hu

and Tang

, Finite Size Effect of Epidemic Transmission Threshold on Complex Networks, Journal of Natural Science of Xiangtan University 33(4) (2011), 5.

37.

Dong

and Zhou

, Improved influential nodes identification in complex networks[J], Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology 6 (2021), 41.