Physica A: Statistical Mechanics and its Applications
A modified evidential methodology of identifying influential nodes in weighted networks
Introduction
It is of theoretical significance and practical value to know how to identify influential nodes effectively in complex networks, such as controlling rumor and disease spreading [1], [2], [3], [4], [5] and creating new marketing tools [6], [7], [8], [9], [10], [11], [12], [13], [14], [15]. Various centrality measures have been proposed over the years to capture network individuals meanings — influence [16], importance [17], [18], [19], popularity [20], [21], recommendation [22], [23], controllability [24] and spreading efficiency [25], according to their degree and weight strength of each node and topological importance in the network structure [26].
The methods commonly used in binary networks are Degree centrality (DC), Betweenness centrality (BC) [27] and Closeness centrality (CC) [28]. The DC method is very simple but of little relevance, since it does not take into account the global structure of a complex network. BC and CC are well-known metrics which can better capture the global structure of a network, but are difficult to be applied in large-scale networks due to the computational complexity. Meanwhile, another limitation of CC is the lack of adjustability to networks with disconnected components: two nodes that belong to different components but do not have a finite distance between them. These three centrality measures have already been extended to be applied in weighted networks [27]. In 2011, Chen et al. [16] proposed an effective Semi-local Centrality which can give a better result in low computational complexity than other methods, such as BC and CC, but is incapable of being applied in weighted networks. Several spectral centrality measures are also available, such as eigenvector centrality (EC) [29], Katz’s centrality [30], subgraph centrality [31], PageRank [32] and LeaderRank [33]. Some centrality measures have been extended to weighted networks [27], [34], [35], [36]. In a word, the design of an effective ranking method to identify influential nodes is still an open issue.
The Dempster–Shafer evidence theory was first proposed by Dempster [37] and then developed by Shafer [38]. This theory needs weaker conditions than the Bayesian theory of probability, so it is often regarded as an extension of the Bayesian theory. The probability assigned to each subset is limited by a lower bound and an upper bound, which respectively measure the total belief and the total plausibility for the objects in the subset. Furthermore, the Dempster–Shafer evidence theory has the ability to combine pairs of evidence or belief functions to derive a new evidence or belief function. Due to its ability to handle the uncertainty or imprecision in the evidence, the Dempster–Shafer theory has been widely applied in recent years [39], [40], [41], [42], [43], [44], [45], [46]. The existing EVC [47] based on the Dempster–Shafer theory of evidence is obtained by the combination of degree and weight strength of each node. However, there is an assumption that EVC obviously follows uniform distribution, which does not accord with degree distribution of real complex networks. In addition, the EVC centrality measure has ignored the global structure information of the network, which is analogous with the extension of DC — simple but of little relevance. Moreover, the application of semi-local centrality [16] in weighted networks has not been addressed. In this paper, modified evidential centrality is obtained by taking into account the degree distribution. Then a new Evidential Semi-local centrality (ESC) measure is proposed by a combination of modified evidential centrality and the extension of semi-local centrality in weighted networks. To evaluate the performance of the proposed method, we adopt the Susceptible and Infected (SI) model to examine the spreading influence of the nodes ranked by different centrality measures. The simulations on real networks are used to show the efficiency of the proposed method.
The remaining parts are organized as follows. Section 2 begins with a brief overview of existing centrality measures and an introduction to the evidence theory. Then, the proposed method for identifying the influential nodes is developed and illustrated by an example network in Section 3. In Section 4, the SI model is adopted to evaluate the performance in two example networks and real complex networks. Some conclusions are presented in Section 5.
Section snippets
Centrality measures
A weighted network can generally be represented as a set [28]. Here, and are the sets of all nodes and edges, respectively. Let and be the corresponding degree and weight of node with its neighbors. is the weight set of , i.e., the link from nodes to has a weight .
DC, BC and CC applied in unweighted networks are well defined in Ref. [28]. In a weighted network, these three measures have been extended [27] as follows.
Definition 2.1 DC in a Weighted Network The DC of node , denoted as ,
Evidential semi-local centrality
In complex networks, the degree distribution of a network denoted by is defined to be the fraction of nodes in the network with degree . There are several different degree distributions, such as the Poisson distribution in random graphs and a power law in scale-free networks [48]. In Ref. [47], the BPA obtained from the degree of a node is based on the assumption that the network follows a uniform distribution. In this paper, such a deficiency will be overcome. In addition, the
Examples and applications
In this section, we will adopt two simple networks and applications in different networks of the proposed evidential semi-local centrality method. Meanwhile, comparisons with another three know centrality measures (DC, CC and BC) are also given to shown the difference between them.
Conclusion
In this paper, an Evidential Semi-local Centrality measure is proposed based on the Dempster–Shafer theory of evidence to identify influential nodes in weighted networks. The modified method is more reasonable than the existing evidential centrality due to the fact that the degree distribution of a complex network is taken into consideration. In addition, semi-local centrality has been extended to be applied on a weighted network. The numerical examples show that the proposed approach can
Acknowledgments
We greatly appreciate the Editor’s encouragement and the anonymous reviewer’s valuable comments and suggestions to improve this work. The Ph.D. candidates of the corresponding author at Shanghai Jiao Tong University, Xiaoyan Su and Peida Xu, gave some discussions on the algorithm. The work described in this paper is partially supported by Chongqing Natural Science Foundation, Grant No. CSCT, 2010BA2003, National Natural Science Foundation of China, Grant Nos. 61174022 and 71271061, National
References (57)
- et al.
Methods to find community based on edge centrality
Physica A: Statistical Mechanics and its Applications
(2013) - et al.
Link prediction in complex networks: a survey
Physica A: Statistical Mechanics and its Applications
(2011) - et al.
Using metrics from complex networks to evaluate machine translation
Physica A: Statistical Mechanics and its Applications
(2011) - et al.
A modified sis model with an infective medium on complex networks and its global stability
Physica A: Statistical Mechanics and its Applications
(2011) - et al.
Identifying all-around nodes for spreading dynamics in complex networks
Physica A: Statistical Mechanics and its Applications
(2012) - et al.
Identifying influential nodes in complex networks
Physica A: Statistical Mechanics and its Applications
(2012) - et al.
Quantifying positional importance in food webs: a comparison of centrality indices
Ecological Modelling
(2007) - et al.
Group betweenness and co-betweenness: inter-related notions of coalition centrality
Social Networks
(2009) - et al.
Street centrality and land use intensity in baton rouge, louisiana
Journal of Transport Geograph
(2011) - et al.
Degree centrality for semantic abstraction summarization of therapeutic studies
Journal of Biomedical Informatics
(2011)