Evidentialmethod to identify in fl uentialnodes in complex networks

,3,4,*

1.Schoolof Computer and Information Science,Southwest University,Chongqing 400715,China; 2.Departmentof the Tibetan Language,Sichuan University of Nationalities,Kangding 626001,China; 3.Schoolof Automation,Northwestern Polytechnical University,Xi’an 710072,China; 4.Schoolof Engineering,Vanderbilt University,TN 37235,USA

Evidentialmethod to identify in fl uentialnodes in complex networks

Hongming Mo1,2,CaiGao1,and Yong Deng1,3,4,*

1.Schoolof Computer and Information Science,Southwest University,Chongqing 400715,China; 2.Departmentof the Tibetan Language,Sichuan University of Nationalities,Kangding 626001,China; 3.Schoolof Automation,Northwestern Polytechnical University,Xi’an 710072,China; 4.Schoolof Engineering,Vanderbilt University,TN 37235,USA

Identifying in fl uentialnodes in complex networks is still an open issue.In this paper,a new comprehensive centrality measure is proposed based on the Dempster-Shafer evidence theory. The existing measures of degree centrality,betweenness centrality and closeness centrality are taken into consideration in the proposed method.Numericalexamples are used to illustrate the effectiveness of the proposed method.

Dempster-Shafer evidence theory(D-S theory);belief function;complex networks;in fl uentialnodes;evidentialcentrality; comprehensive measure.

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 biologicalsciences can be regarded as complex networks.Itis of theoretical signi fi cance and practical value to know how to identify the in fl uentialnodes effectively in complex networks[9-16].Itis essentialto identify the node centrality, for itwillhelp to better know the structure of the complex networks and wellmanage the complex networks[17-25].

The existing commonly used methods to identify the central nodes of binary networks are degree centrality (DC),betweenness centrality(BC)[26]and closeness centrality(CC)[27].DC,BC and CC function well in some special networks.The DC method is straight-forward, simple and ef fi cient,butof little globalstructure relevance. Itjustconsiders the localstructure butnotthe globalstructure of the network.BC and CC metrics can better identify in fl uential nodes,since they take the global structure into consideration.BC is de fi ned as the number of the shortest paths from all vertices to all others that pass through that node.CC is de fi ned as the inverse sum of the shortest distances to all other nodes from a focal node.Some other measures are also available to identify the in fl uential nodes in complex networks,such as semi-local centrality [28],eigenvectorcentrality[29],PageRank[30]and LeaderRank[31].

The Dempster-Shafer evidence theory(D-S theory) [32,33]is a powerfultoolin data fusion,decision making, etc.[34-43].And the combination rule of Dempster,as introduced later,can be used to combine differentproperties of the same objectto yield a new comprehensive characteristic.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 in fl uential nodes in complex networks.Wei et al.[44]proposed a centrality measure based on the D-S theory,trading off between the degree and the strength of every node in a weighted network.Based on[44],Gao etal.[45]proposed an improvementmeasure,which takes the degree and the weight of every node itself and the nearest neighbors into consideration in a weighted network.The two evidential measures of node centrality are applied to weighted networks.When the networks are unweighed,the two existing evidentialmeasuresofnode centrality degenerate to the fundamentalmeasure of DC,ignoring the weightelement. To address the issue,a new evidential method to identifyin fl uential nodes in unweighted networks,combining DC, BC and CC based on the D-S theory,is proposed in this paper.In the proposed evidential method,the in fl uence of nodes are ascertained by unionization of degree,betweenness and closeness.We all know that,the capability of a node depends on many aspects,such as degree,betweenness and closeness.Thus the proposed method is more comprehensive than those existing single methods in unweighted networks.To evaluate the performance of the proposed method,the susceptible and infected(SI)model is adopted to examine the spreading in fl uence of the nodes ranked by differentcentrality measures.

The paper is organized as follows.In Section 2,a brief overview of centrality measures and a short introduction of the D-S theory are given.In Section 3,the proposed method to identify in fl uential nodes in complex networks is developed and illustrated by detailed steps.Assessment of the proposed method by the SI modelis shown in Section 4.A shortconclusion is drawn in the last Section.

2.Preliminaries

2.1 Centrality measure

A network can generally be represented as a set G= (V,E)[27].Here,V and E are the sets of all nodes and edges,respectively.|V|=n,which is the number of nodes.

The three centrality measures of DC,BC and CC are given as follows:

Definition 1The DC of node i,denoted as d(i),is de fi ned as

where vijis the edge between node i and node j.The value of vijis 1,when there is an edge between node i and node j,otherwise 0.

Definition 2The BC of node i,denoted as b(i),is defi ned as

where gpqis the number of the shortest paths from all nodes to allothers,and gpq(i)denotes the numberofnode i passing through the shortestpaths.

Definition 3The CC of node i,denoted as c(i),is defi ned as

where stijis the shortest distance between node i and node j.

2.2 DS theory

In the D-S theory,a problem domain is denoted by a finite nonempty setΩof mutually exclusive and exhaustive hypotheses,called the frame of discernment.A few basic concepts[32,33]are introduced as follows:

Definition 4LetΩ={θ1,θ2,...,θN}be a fi nite set of N elements.Let 2Ωdenote the power set ofΩ,and 2Ω={?,θ1,...,θN,θ1∪θ2,θ1∪θ3,...,Ω}.

Definition 5For a frame of discernmentΩ,a basic probability assignment(BPA)function is a mapping m:2Ω→[0,1],which is also called mass function,satisfying

where?is an empty set and A is any elementof 2Ω.The mass function m(A)represents how strongly the evidence supports A.Given two BPAs m1and m2,the Dempster’s combination rule can be used to combine them and yield a new BPA.

Definition 6Dempster’s rule of combination,also called orthogonalsum,denoted by m=m1⊕m2,is defi ned as follows:

where A,B and C are the elements of 2Ω,and K is a normalization constant,called the con fl ict coef fi cient of the two BPAs.The Dempster’s rule of combination is the core of the D-S theory,satisfying commutative and associative properties,i.e.(i)m1⊕m2=m2⊕m1;(ii)

(m1⊕m2)⊕m3=m1⊕(m2⊕m3).Thus if there exist multiple BPAs,the combination of them can be carried out in a pairwise way with any order.

3.Evidentialcentrality

In this section,we propose a new method to identify the in

fl uentialnodes in complex networks,called comprehensive evidence centrality(CEC).In CEC,the in fl uence ofa node takes into accountnot only degree,betweenness or closeness,but all of them.The in fl uence of a node is de fi ned by the Dempster’s rule of combination,regarding DC,BC and CC as differentBPAs.The method to generate the new BPA of CEC is developed as follows.

3.1 Construction of BPAs of degree,betweenness and closeness

Step 1Ascertain a frame of discernmentθ,θ= (high,low).Let high and low be the evaluation indicesof in fl uence of degree,betweeness and closeness of each node.Let h represent high,and l represent low,for short. And then,the frame of discernmentθcan be represented asθ=(h,l).

Step 2Ascertain a reference value based on the degree, betweenness and closeness.The maximum and minimum values of the degree,betweenness and closeness,can be obtained respectively as follows:

In general,dM≥dm,bM≥bmand cM≥cmin complex networks,and n is the number of nodes.

Step 3Construct BPAs for the degree,betweenness and closeness of each node.mdi(h)and mdi(l)(i= 1,2,3,...,n)represent the probabilities of“high”and“l(fā)ow”in fl uence of degree of the i th node,respectively. mbi(h),mbi(l),mci(h)and mci(l),likewise.These mass functions of the i th node are generated as follows:

whereαis a user-de fi ned parameter,α∈[0,1],andα is set to be 1,for simplicity.di,biand ciare the degree, betweenness and closeness of the i th node,respectively. Therefore,the BPAs of the i th node according to the degree,betweenness and closeness can be generated respectively as follows:

Step 4Apply the combination rule of Dempster.Using(4),a new BPA ofthe i th node,combining with Md(i), Mb(i)and Mc(i),can be obtained as follows:

3.2 Comprehensive evidence centrality

Step 5In(24),mi(θ)implies that the probabilities of high or low are unknown.For simplicity,assign mi(θ)to mi(h)and mi(l)averagely,therefore the indices of the i th node can be represented as follows:

where Mi(h)and Mi(l)are the in fl uentialprobabilities of high and low of the i th node,respectively.Obviously,the higherthe value of Mi(h),the more importantthe node.In contrast,the lower the value of Mi(l),the more important the node.Therefore,the comprehensive evidence centrality can be presented by a function associated with Mi(h) and Mi(l).

Definition 7Denoting CEC(i)as the CEC value of node i,which satis fi es

where CEC(i)is a real number,CEC(i)∈[-1,1],and the greater the value,the more importantthe node.

Example 1A toy network with 8 nodes and 11 edges is shown in Fig.1.The values of degree,betweenness and closeness of each node are shown in the second,third and fourth columns in Table 1,respectively.

Fig.1 A network with 8 nodes

Table 1 Evidential centrality of a network with 8 nodes

From Table 1,using(6)-(11),the following values ca n be obtained:dM=5,dm=1;bM=17,bm=0;cM= 0.777 8,cm=0.411 8.

Taking node A as an example,the BPA of the degree of node A,with(12),(13)and(18)used,can be obtained as follows:

Thatis,the BPA of the degree of node A can be rewritten as

Similarly,using(14)-(20),the BPAs of betweeness and closeness of node A can be obtained as follows:

By(4),combining the three BPAs,Md(A),Mb(A)and Mc(A),a new BPA M(A)is generated as

From(24),the values of mA(h),mA(l)and mA(θ)are as follows:

Using(25)-(27),the comprehensive evidential centrality of node A can be obtained as follows:

Repeating the above processes,the CEC values of the other nodes can be calculated.The CEC value of each node in this example is shown in the fi fth column in Table 1.

4.Application

The data from Zachary’s Karate Club Network were collected from the members at a USA university karate club by Wayne Zachary in 1977[46].Zachary constructed a network by considering each member in the club as a node. Each edge in the network represents that the connected two members are friends outside the club activities.The network is shown in Fig.2.

Fig.2 Zachary’s Karate Club Network with 34 nodes and 78 edges

To evaluate the performance of the proposed method, we adoptthe SI modelto examine the spreading in fl uence oftop-L nodes ranked by differentmeasures.The SImodel is used to mimic the spreading ability of diseases,rumors and so on[28,47,48].In the SImodel,there are two compartments,namely the susceptible(S)and the infected(I). At each step,each infected node randomly selects one of its neighbors to contact,with probabilityλ.Node i infects node j with probability(?＞0),where djis the degree of node j,and dMis the maximum degree in the network.For simplicity,?is setto be 1.Notice that this model is slightly different from the standard SI model where all the neighbors of an infected node have the chance to be infected.Considering its function,the SI modelis usually used to mimic the limited spreading capability of individuals.

In order to identify the in fl uence between nodes 1,33 and 34,the three nodes are set as infected nodes in the SI model,respectively.Then,the trial proceeds until all the nodes are infected.Niis the number of infected nodes at the i th step,and〈Ni〉denotes the average value of Niin 100 traces.The in fl uence of nodes 1,33 and 34 are shown in Fig.3.It indicates that the spreading speed of node 1 is the fastest,thus node 1 is the most in fl uential node in the network,which has the largestCEC value.The evaluation indices and orders of Zachary’s Karate Club Network, processed by DC,BC,CC and CEC methods are shown in Table 2,respectively.From Table 2,it is clearly seen that the orders,as shown in the 3rd,5th,7th and 9th columns, are different by the DC,BC,CC and CEC methods,respectively.In otherwords,differentmethods take different indices into consideration.The DC,BC and CC methods are single index,and the CEC method is multi-indices.For example,DC just takes the degree of the node into consideration,discarding other indices of the node.However, the CEC method takes these indices of DC,BC and CC into consideration.Itis obvious that,the method of multiindices refers to more factors of the node than the singleindex method.Thatis,the results generated by CECshould be more objective and reasonable than those by the DC,BCor CC method.In order to examine the ability of identi fication,the SImodelis used to compare the proposed CEC method with DC,BC and CC,respectively.The different spreading abilities and stabilities are shown in Figs.4-6, which indicates thatthe proposed method CEC is slightly better than DC,BC and CC.

Table 2 Order ofinfluential nodes of Zachary’s Karate Club Network by different measures

Fig.3 Spreading capabilities of nodes 1,33 and 34 in Zachary’s Karate Club Network

Fig.4 Influence of evidential centrality and degree centrality in Zachary’s Karate Club Network

Fig.5 Influence of evidential centrality and betweenness centrality in Zachary’s Karate Club Network

Fig.6 Influence of evidential centrality and closeness centrality in Zachary’s Karate Club Network

5.Conclusions

In this paper,a comprehensive evidential method is proposed to identify in fl uential nodes in complex networks. The proposed method integrates degree,betweenness and closeness of each node based on the D-S theory.Numericalexamples illustrate thatthe proposed measure can well identify in fl uentialnodes.Itshould be pointed outthatthe proposed method only focuses on unweighted networks. Our ongoing work is to improve this proposed method to address the identi fi cation of in fl uential nodes in weighted networks.

[1]S.H.Strogatz.Exploring complex networks.Nature,2001, 410(6825):268-276

[2]A.L.Barab′asi,R.Albert.Emergence of scaling in random networks.Science,1999,286(5439):509-512.

[3]D.J.Watts,S.H.Strogatz.Collective dynamics ofsmall-world networks.Nature,1998,393(6684):440-442.

[4]H.J.Kim.Analysis ofa complex network ofphysics concepts. Modern Physics Letters B,2012,26(28):125-186.

[5]O.Shanker,T.Hogg.Epidemiology model on shortcut and small world networks.Modern Physics Letters B,2009, 23(10):1249-1262.

[6]J.Wang,L.L.Rong.Similarity index based on the information ofneighbornodes forlink prediction ofcomplex network. Modern Physics Letters B,2013,27(6):1350039.

[7]H.X.Zhang,X.Lan,D.J.Wei,etal.Self-similarity in complex networks:from the view of the hub repulsion.Modern Physics Letters B,2013,27(28):1350201.

[8]C.Shi,Z.Y.Yan,Y.N.Cai,etal.Multi-objective community detection in complex networks.Applied SoftComputing,2012, 12(2):850-859.

[9]M.Kitsak,L.K.Gallos,S.Havlin,et al.Identi fi cation of infl uentialspreaders in complex networks.Nature Physics,2010, 6(11):888-893.

[10]T.Zhou,G.Yan,B.H.Wang.Maximalplanar networks with large clustering coef fi cient and power-law degree distribution. PhysicalReview E,2005,71(4):046141.

[11]D.B.Chen,H.Gao,L.Y.L¨u,et al.Identifying in fl uential nodes in large-scale directed networks:the role of clustering. PloS One,2013,8(10):e77455.

[12]J.G.Liu,Z.M.Ren,Q.Guo.Ranking the spreading in fl uence in complex networks.Physica A:StatisticalMechanics and its Applications,2013,392(18):4154-4159.

[13]L.Y.L¨u,D.B.Chen,T,Zhou.The small world yields the mosteffective information spreading.New JournalofPhysics, 2011,13(12):123005.

[14]Q.Li,T.Zhou,L.Y.L¨u,etal.Identifying in fl uentialspreaders by weighted leaderrank.Physica A:StatisticalMechanics and its Applications,2014,404:47-55.

[15]B.N.Hou,Y.P.Yao,D.S.Liao.Identifying all-around nodes for spreading dynamics in complex networks.Physica A:StatisticalMechanics and its Applications,2012,391(15):4012-4017.

[16]Q.C.Hu,Y.Gao,P.F.Ma,et al.A new approach to identify in fl uential spreaders in complex networks.Proc.of the 14th InternationalConference on Web-Age Information Management.2013:99-104.

[17]X.H.Zhang,J.Zhu,Q.Wang,et al.Identifying in fl uential nodes in complex networks with community structure. Knowledge-Based Systems,2013,42(18):74-84.

[18]F.Bauer,J.T.Lizier.Identifying in fl uentialspreaders and ef ficiently estimating infection numbers in epidemic models:A walk counting approach.Europhysics Letters,2012,99(6): 68007.

[19]T.Zhou,Z.Q.Fu,B.H.Wang.Epidemic dynamics on complex networks.Progress in Natural Science,2006,16(5):452-457.

[20]A.Zeng,C.J.Zhang.Ranking spreaders by decomposing complex networks.Physics Letters A,2013,377(14):1031-1035.

[21]D.B.Chen,R.Xiao,A.Zeng,et al.Path diversity improves the identi fi cation of in fl uentialspreaders.Europhysics Letters, 2013,104(6):68006.

[22]J.Borge-Holthoefer,Y.Moreno.Absence ofin fl uentialspreaders in rumor dynamics.Physical Review E,2012,85(2): 026116.

[23]J.Borge-Holthoefer,A.Rivero,Y.Moreno.Locating privileged spreaders on an online socialnetwork.Physical Review E,2012,85(6):066123.

[24]C.Gao,X.Lan,X.G.Zhang,etal.A bio-inspired methodology of identifying in fl uential nodes in complex networks. PloS One,2013,8(6):e66732.

[25]M.G.Gong,X.W.Chen,L.J.Ma,et al.Identi fi cation of multi-resolution network structures with multi-objective immune algorithm.Applied SoftComputing,2013,13(4):1705-1717.

[26]T.Opsahl,F.Agneessens,J.Skvoretz.Node centrality in weighted networks:Generalizing degree and shortest paths. Social Networks,2010,32(3):245-251.

[27]L.C.Freeman.Centrality in socialnetworks conceptualclarifi cation.Social Networks,1979,1(3):215-239.

[28]D.B.Chen,L.Y.L¨u,M.S.Shang,etal.Identifying in fl uential nodes in complex networks.Physica A:Statistical Mechanics and its Applications,2012,391(4):1777-1787.

[29]B.Hou,Y.Yao,D.Liao.Identifying all-around nodes for spreading dynamics in complex networks.Physica A:Statistical Mechanics and its Applications,2012,391(15):4012-4017.

[30]S.Brin,L.Page.The anatomy of a large-scale hypertextual Web search engine.Computer Networks and ISDN systems, 1998,30(1):107-117.

[31]L.Y.L¨u,Y.C.Zhang,C.H.Yeung,et al.Leaders in social networks,the delicious case.PloS One,2011,6(6):e21202.

[32]A.P.Dempster.Upper and lower probabilities induced by a multivalued mapping.The Annals of Mathematical Statistics, 1967,38(2):325-339.

[33]G.Shafer.A mathematical theory of evidence.Princeton: Princeton University Press,1976.

[34]X.Y.Deng,Y.Hu,Y.Deng,et al.Supplier selection using AHP methodology extended by D numbers.Expert Systems with Applications,2014,41(1):156-167.

[35]B.Y.Kang,Y.Deng,R.Sadiq,et al.Evidential cognitive maps.Knowledge-Based Systems,2012,35:77-86.

[36]C.W.Zhang,Y.Hu,F.T.Chan,et al.A new method to determine basic probability assignment using core samples. Knowledge-Based Systems,2014,69:140-149.

[37]S.Y.Huang,X.Y Su,Y.Hu,et al.A new decision making method by incomplete preferences based on evidence distance. Knowledge-Based Systems,2014,56:264-272.

[38]X.Y.Deng,Y.Hu,Y.Deng,et al.Environmental impactassessment based on D numbers.Expert Systems with Applications,2014,41(2):635-643.

[39]Z.G.Liu,Q.Pan,J.Dezert.A belief classi fi cation rule for imprecise data.Applied Intelligence,2014,40(2):214-228.

[40]Z.G.Liu,G.Mercier,J.Dezert,et al.Change detection in heterogeneous remote sensing images based on multidimensional evidential reasoning.IEEE Trans.on Geoscience and Remote Sensing Letters,2014,11(1):168-172.

[41]B.Suo,Y.S.Cheng,C.Zeng,etal.Computationalintelligence approach for uncertainty quanti fi cation using evidence theory. Journal of Systems Engineering and Electronics,2013,24(2): 250-260.

[42]Y.Q.Tan,J.Y.Yang,L.C.Li,etal.Data fusion of radar and IFF for aircraftidenti fi cation.Journal of Systems Engineering and Electronics,2012,23(5):715-722.

[43]Y.He,L.F.Hu,X.Guan,et al.New con fl ict representation model in generalized power space.Journal of Systems Engineering and Electronics,2012,23(1):1-9.

[44]D.J.Wei,X.Y.Deng,X.G.Zhang,et al.Identifying in fl uential nodes in weighted networks based on evidence theory. Physica A:Statistical Mechanics and its Applications,2013, 392(10):2564-2575.

[45]C.Gao,D.J.Wei,Y.Hu,etal.A modi fi ed evidential methodology of identifying in fl uentialnodes in weighted networks. Physica A:Statistical Mechanics and its Applications,2013, 392(21):5490-5500.

[46]W.W.Zachary.An information fl ow model for con fl ict and fi ssion in small groups.Journal of Anthropological Research, 1977:452-473.

[47]L.J.Allen.Some discrete-time SI,SIR and SIS epidemic models.Mathematical Biosciences,1994,124(1):83-105.

[48]G.Yan,T.Zhou,J.Wang,et al.Epidemic spread in weighted scale-free networks.Chinese Physics Letters,2005,22(2): 510.

Biographies

Hongming Mo was born in 1983.He received his B.S.degree from Chongqing NormalUniversity in 2006.He is now an assistantresearcher in Sichuan University of Nationalities.His research interests include uncertain information modeling and processing.

E-mail:mohongmingswu@163.com

Cai Gao was born in 1989.He received his B.S.degree in textile engineering from Southwest Univerity,Chongqing,China,in 2012.He is now a second year graduate student in Southwest University.His research interest is uncertain information modeling and processing.

E-mail:gaocaiswu@163.com

Yong Deng was born in 1975.He received his B.S. degree in physics education from Shaanxi Normal University in 1997.He then received his M.S.degree in measurement technology and instrument from Hunan University in 2000 and Ph.D.degree from Shanghai Jiaotong University in 2003.He is now a professor in Southwest University.His research interests include uncertain information modeling and processing.

E-mail:ydeng@swu.edu.cn;prof.deng@hotmail. com

10.1109/JSEE.2015.00044

Manuscriptreceived May 9,2014.

*Corresponding author.

This work was supported by the National Natural Science Foundation of China(61174022),the National High Technology Research and Development 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 Research Program of the Science Supported by Sichuan Provincial Departmentof Education(14ZB0322),and the Fundamental Research Funds for the Central Universities(XDJK2014D008).