A modified evidential methodology of identifying influential nodes in weighted networks

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

Highlights

  • Evidential Centrality could represent the local information of each node.

  • The degree distribution is taken into consideration to built the BPA of each node.

  • Semi-local Centrality is extended to be applied in weighted complex networks.

  • The proposed method can rank identify influential nodes accurately.

Abstract

How to identify influential nodes in complex networks is still an open hot issue. In the existing evidential centrality (EVC), node degree distribution in complex networks is not taken into consideration. In addition, the global structure information has also been neglected. In this paper, a new Evidential Semi-local Centrality (ESC) is proposed by modifying EVC in two aspects. Firstly, the Basic Probability Assignment (BPA) of degree generated by EVC is modified according to the actual degree distribution, rather than just following uniform distribution. BPA is the generation of probability in order to model uncertainty. Secondly, semi-local centrality combined with modified EVC is extended to be applied in weighted networks. Numerical examples are used to illustrate the efficiency of the proposed method.

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 G=(V,E,W)   [28]. Here, V and E are the sets of all nodes and edges, respectively. Let ki and ωi be the corresponding degree and weight of node i with its neighbors. W is the weight set of E, i.e., the link Eij from nodes i to j has a weight ωijW.

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 i, denoted as Cdω(i),

Evidential semi-local centrality

In complex networks, the degree distribution of a network denoted by P(k) is defined to be the fraction of nodes in the network with degree k. 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)

  • P.H. Pathak et al.

    Centrality-based power control for hot-spot mitigation in multi-hop wireless networks

    Computer Communications

    (2012)
  • T. Opsahl et al.

    Node centrality in weighted networks: generalizing degree and shortest paths

    Social Networks

    (2010)
  • L. Freeman

    Centrality in social networks conceptual clarification

    Social Networks

    (1979)
  • P. Bonacich et al.

    Eigenvector-like measures of centrality for asymmetric relations

    Social Networks

    (2001)
  • S. Brin et al.

    The anatomy of a large-scale hypertextual web search engine

    Computer Networks and ISDN Systems

    (1998)
  • X. Chu et al.

    Epidemic spreading with nonlinear infectivity in weighted scale-free networks

    Physica A: Statistical Mechanics and its Applications

    (2011)
  • J.B. Yang et al.

    The evidential reasoning approach for MADA under both probabilistic and fuzzy uncertainties

    European Journal of Operational Research

    (2006)
  • B. Kang et al.

    Evidential cognitive maps

    Knowledge-Based Systems

    (2012)
  • Y. Deng et al.

    Modeling contaminant intrusion in water distribution networks: a new similarity-based DST method

    Expert Systems with Applications

    (2011)
  • P. Bonissone et al.

    Fast meta-models for local fusion of multiple predictive models

    Applied Soft Computing

    (2011)
  • Y. Deng et al.

    A new linguistic mcdm method based on multiple-criterion data fusion

    Expert Systems With Applications

    (2011)
  • X.Y. Su et al.

    An improved method for risk evaluation in failure modes and effects analysis of aircraft engine rotor blades

    Engineering Failure Analysis

    (2012)
  • D. Wei et al.

    Identifying influential nodes in weighted networks based on evidence theory

    Physica A: Statistical Mechanics and its Applications

    (2013)
  • L. Allen

    Some discrete-time si, sir, and sis epidemic models

    Mathematical Biosciences

    (1994)
  • F. Rakowski et al.

    Influenza epidemic spread simulation for polanda large scale, individual based model study

    Physica A: Statistical Mechanics and its Applications

    (2010)
  • S. Ni et al.

    Modeling the effects of social impact on epidemic spreading in complex networks

    Physica A: Statistical Mechanics and its Applications

    (2011)
  • H. Bernard et al.

    Informant accuracy in social-network data v. an experimental attempt to predict actual communication from recall data

    Social Science Research

    (1982)
  • H. Zhang et al.

    A stochastic sir epidemic on scale-free network with community structure

    Physica A: Statistical Mechanics and its Applications

    (2012)
  • Cited by (0)

    View full text