Journal of Systems Engineering and Electronics
Vol. 26, No. 2, Apr il 2015, pp.381–387
Evidential method to identify influential nodes in
complex networks
Hongming Mo
1,2
,CaiGao
1
, and Yong Deng
1,3,4,*
1. School of Computer and Information Science, Southwest Univ ersity, Chongqing 400715, China;
2. Department of the Tibetan Language, Sichuan University of Nationalities, Kangding 626001, China;
3. School of Automation, Northwestern Polytechnical University, Xi’an 710072, China;
4. School of Engineering, Vanderbilt University, TN 37235, USA
Abstract:
Identifying influential nodes in complex networks is still
an open issue. In this paper, a new comprehensive centrality mea-
sure is proposed based on the Dempster-Shafer evidence theory.
The existing measures of degree centrality, betweenness centra-
lity and closeness centrality are taken into consideration in the
proposed method. Numerical examples are used to illustrate the
effectiveness of the proposed method.
Keyw ords: Dempster-Shafer evidence theory (D-S theory); belief
function; complex networks; influential nodes; evidential centrality;
comprehensive measure.
DOI: 10.1109/JSEE.2015.00044
1. Introduction
Complex networks have attracted more and more attention
in recent years [1–8]. Many real-world systems such as
computer sciences, economics, management and biologi-
cal sciences can be regarded as complex n etworks. It is of
theoretical significance and practical value to know how
to identify the influential nodes effectively in complex net-
works [9–16]. It is essential to identify the node centrality,
for it will help to better know the structure of the complex
networks and well manage the complex networks [17–25].
The existing commonly used methods to identify the
central nodes of b inary networks are degree centrality
(DC), betweenness centrality (BC) [26] and closeness cen-
trality (CC) [27]. DC, BC and CC function well in some
special networks. The DC method is straight-forward,
Manuscript received May 9, 2014.
*Corresponding author.
This work was supported by the National Natural Science Foundation
of China (61174022), the National High Technology Research and De-
velopment Program of China (863 Program) (2013AA013801), the Open
Funding Project of State Key Laboratory of Virtual Reality Technology
and Systems, Beihang University (BUAA-VR-14KF-02), the General Re-
search Program of the Science Supported by Sichuan Provincial Depart-
ment of Education (14ZB0322), and the Fundamental Research Funds for
the Central Universities (XDJK2014D008).
simple and efficient, but of little global structure relevance.
It just considers the local structure but not the global struc-
ture of the network . BC and CC metrics can better identify
influential nodes, since they take the global structure into
consideration. BC is defined as the number of the short-
est paths from all vertices to all others that pass through
that node. CC is defined as the inverse sum of the short-
est distances to all other nodes from a focal node. Some
other measures are also available to identify the influential
nodes in complex networks, such as semi-local centrality
[28], eigenvector centrality [29] , PageRank [ 30] and L ead-
erRank [31].
The Dempster-Shafer evidence theory (D-S theory)
[32,33] is a powerful tool in data fusion, decision making,
etc. [34–43]. And the combination rule o f Dempster, as in-
troduced later, can be used to combine different proper ties
of the same object to yield a new comprehensive characte-
ristic. Thus, the Dempster’s combination rule can be used
to combine the DC, BC and CC of a node and generate a
new index, which can be viewed as the capability of the
node. Based on the ability of the Dempster’s combination
rule, the D-S theory has been applied to identify influen-
tial nodes in complex networks. Wei et al. [44] proposed
a centrality measure based on the D-S theory, trading off
between the d egree and the strength of every node in a
weighted network. Based on [44], Gao et al. [45] proposed
an improvement measure, which takes the degree and the
weight of every node itself and the nearest n eighbors into
consideration in a weighted network. The two evidential
measures of node centrality are applied to weighted net-
works. When the n etworks are unweighed, the two exist-
ing evidential measures of node centrality degenerate to the
fundamental measure of DC, ignoring the weight element.
To address the issue, a new evidential method to identify