Advertisement
Research Article

A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks

  • Cai Gao,

    Affiliation: School of Computer and Information Science, Southwest University, Chongqing, China

    X
  • Xin Lan,

    Affiliation: School of Computer and Information Science, Southwest University, Chongqing, China

    X
  • Xiaoge Zhang,

    Affiliation: School of Computer and Information Science, Southwest University, Chongqing, China

    X
  • Yong Deng mail

    ydeng@swu.edu.cn

    Affiliations: School of Computer and Information Science, Southwest University, Chongqing, China, School of Engineering, Vanderbilt University, Nashville, Tennessee, United States of America

    X
  • Published: June 14, 2013
  • DOI: 10.1371/journal.pone.0066732

Abstract

How to identify influential nodes is a key issue in complex networks. The degree centrality is simple, but is incapable to reflect the global characteristics of networks. Betweenness centrality and closeness centrality do not consider the location of nodes in the networks, and semi-local centrality, leaderRank and pageRank approaches can be only applied in unweighted networks. In this paper, a bio-inspired centrality measure model is proposed, which combines the Physarum centrality with the K-shell index obtained by K-shell decomposition analysis, to identify influential nodes in weighted networks. Then, we use the Susceptible-Infected (SI) model to evaluate the performance. Examples and applications are given to demonstrate the adaptivity and efficiency of the proposed method. In addition, the results are compared with existing methods.

Introduction

It is of theoretical significance and practical value to know how to identify influential nodes effectively in complex networks [1][14], such as controlling rumor and disease spreading [15], electric power supply [16], evolution of cooperation [9], [17][19], game theory [20][22], link prediction [23][25] and robust reproduction of organisms [26].Various centrality measures have been proposed over the years to capture network entities meanings influence [27], importance [28][30], popularity [6], [31], controllability [32], [33] and spreading efficiency [34]. Three best known centrality measures were developed to distinguish which nodes are more central than others in binary networks, namely, degree, closeness and betweenness centrality [35]. Degree centrality based on counting the first neighbors of a node has an advantage of simplicity, ignoring the global structure. Closeness centrality was defined as the inverse sum of shortest distances from a focal node to all other nodes, which means high closeness centrality score is, a node more close to the others. However, if a node is at a dead-end, its removal will be without any effect in contrast with the case of a cut-vertex (the analog of a bridge for edges) which leads to disconnected components. Another important centrality is betweenness centrality, It is calculated by assessing the degree to which a node lies on the shortest path over the total number of shortest paths. These three centrality measures have already been extended to be applied in weighted networks. In 2011, a random-walk-based centrality called LeaderRank is proposed in [6], which can identify leaders in social networks better than the well-known PageRank algorithm [36], [37]. After that, Chen et al [27] developed a centrality method called semi-local centrality as a tradeoff between local degree centrality and other global but time-consuming measures with limitation to unweighted networks. Besides, there are also spectral centrality measures such as the eigenvector centrality [38], alpha centrality [38], Katz's centrality [39] and subgraph centrality [40].

However, in many real networks, edges are with with some form of attribute or weight. In addition, network can be changed dynamically. It is necessary to develop a new method to identify influential nodes with a adaptive manner. In 2012, an amoeboid centrality measure called Physarum centrality is proposed in [41], which can be used in weighted dynamic networks. Physarum polycephalum, as an amoeboid organism, can form a dynamic tubular network connecting discovered food sources. Furthermore, it has been applied on many fields, such as transportation [42], optimization [43], [44]. Concretely, Physarum can only control the flux through its body tube dynamically and then adapt itself to find optimal paths connecting two specified nodes conveniently, which means physarum centrality is likely to be applied in dynamically changed large networks suitably.

However, in contrast to common belief, there are plausible circumstances where the best spreaders do not correspond to the most highly connected or the most central nodes [34]. It has been proved that topology of networks plays an important role in spreading process. For example, if a hub (a node with high degree) exists at the end of a branch at the periphery of a network, it will have a minimal impact in the spreading process, whereas a less connected person who is strategically placed in the core of the network will have more influence on other individuals through a large network.

In this paper, a new method is proposed based on combining Physarum centrality and the layer of nodes located in networks. By using the K-shell decomposition analysis [45], [46], the K-shell index of nodes are obtained, which can be used to distinguish the relative location of a node in networks. Then we use the Susceptible-Infected (SI) model [47], [48] to evaluate the performance of the top-L nodes' spreading influence ranked by different centrality measures. Some existing centrality methods, such as semi-local centrality, physarum centrality, LeaderRank and PageRank approach, are used to compared with the proposed method.

The rest of the paper is organized as follows. Section 2 begins with a brief introduction to Physarum centrality. In Section 3 our method is proposed. Then, we use the SI model to evaluate the performance between previous approaches. The proposed method applied on simple numerical example and three real-world networks in Section 4. Finally, in Section 5, we give our conclusions.

Basic Theories

Physarum Model for Path Finding

A mathematical model for cases with two food sources has previously been proposed [49]. In brief, this model represents the shape of physarum cell body by a graph, in which an edge corresponds to a plasmodial tube and a node corresponds to a junction between tubes. At the beginning, there is an undirected weighted network which is strongly connected. Physarum can find the shortest path between starting node s and ending node t (node s and t correspond to food sources). Suppose that the variable means the flux through the edge between nodes i and j, at which pressures are and , respectively. According to Poiseuille flow, the flux is denoted as,(1)
where and are the length and conductivity of the tube corresponding to the edge , respectively. is its conductivity which is assigned with a value that belongs to (0,1] in the initialization.

At each node i (except the nodes s and t which are presented as two food sources), the total flow must be balanced as,(2)
Hence by considering the conservation law of flux we have,(3)
where is the flux flowing into the starting node s and out of the ending node t, which is constant.

Then the network Poisson equation derived from Eqs. 13 is as follows,(4)

In order to show the positive feedback mechanism that a tube thickens depending on increasing flux and thins with decreasing flux, the conductivity is assumed to change over time according to the flux ,(5)
where is a decay rate of the tube. is a increasing function with . More description of can be found in [49], [50]. The process above is just one iteration. The next is to judge whether the termination criterion is met or not. If the specified criterion is fulfilled, tubes without flux are cut off while others complete optimal paths. Meanwhile, update pressure at each node. The iteration will be stopped until the shortest path is found.

Physarum Centrality

In weighted networks, the extension of degree centrality is defined as [51],>(6)

Inspired by it, physarum centrality of a node is defined as the sum of the criticality of each edge linked to it,(7)
where means the criticality of edge linked by node i and j. The value of is calculated by using physarum model for path finding between all pairs of nodes in undirected weighted networks.

In the abovementioned model, physarum model can find optimal paths between any pair of nodes, by adapting the flux through each edge and its conductivity. When the adaptation is finished, optimal paths are reserved while other tubes fade away since no flux is passing though them.

In order to capture this characteristic, the criticality of the edge is defined as the sum of flux through it,(8)
where denotes the final flux through edge by using the physarum mathematical model, while different k implies different path finding between different pairs of food sources nodes s and t.

Proposed Methods

Analyzing the definition of physarum centrality, it seems that physarum centrality is defined as a tradeoff between the extension of degree centrality and betweenness centrality. Physarum finds the shortest path with flux passing through tubes. is the amount of flux on the edges. Then a node's centrality is the sum flux of the edges linked to it. It has been shown that physarum has advantages of flexible self-adaptability and less computational time than Dijkstra's algorithm [52]. Inspired by this, physarum may show a superiority for the adaptive dynamics of networks, in the cases of traffic congestion or following accidents. Therefore, physarum will quickly adapt itself to identify newly influential nodes, when some randomly selected nodes of top-L ones in a network are removed.

Just like degree centrality and betweenness centrality, physarum centrality only captures the characteristics in the aspects of degree, shortest path, rather than location of the network. In contrast to common belief, it seems to be more possible that the most efficient spreaders are those located within the core of a network, rather than highly connected or the most central ones on the edge location [34]. Here we use the k-shell decomposition analysis to identify the location of a node in the network. By using this well-established tool, each node will be assigned with k-shell index value, , to each node, representing its location in the network. If the value of a node equals to 1, it means that the node is located on the periphery of the network.

In our approach, two factors of a node physarum centrality and k-shell index in the network, are both taken into consideration. The flow chart of the proposed method is shown in Figure 1.

thumbnail

Figure 1. The flow chart of the proposed method.

doi:10.1371/journal.pone.0066732.g001

Step 1. Construct a undirected weighted network. Since weights in most weighted networks stands for tie strength, rather than the length between two individuals. the edge weights need to be reversed, in order to correspond to the tube length in physarum model.

Step 2. Apply physarum model to find optimal paths between all pairs of nodes.

  1. The conductivity of each tube is assigned with 0.5.
  2. in Eq. 5 adopts with parameters set a = 2, = 27.
  3. Termination criterion is is determined by maximum iterations, which is 4logn.

Step 3. Calculate the criticality of each edge by Eq. 8 with recorded values .

Step 4. Calculate physarum centrality of nodes with Eq. 7.

Step 5. By using the tool of k-shell decomposition analysis, each node will be assigned with value. According to its decomposition process, first of all, nodes of degree one have index equal to one. Then prune all these nodes and the links incident on nodes with one connection from the network. Nodes that have degree one on the reduced graph are assigned index of one and recursively pruned. Secondly, the same is done for nodes with two connections and so on, until all nodes are pruned from the network. Lastly, normalization is necessary.

Then, the final influence value of nodes ranked by the proposed method, (short for K-shell Physarum Centrality) is expressed as follows,

Hence, nodes located in the core of networks have larger value than ones in the periphery of a network.

Illustrative Examples

In this section, two simple examples and two applications in real networks are used to evaluate the performance of centrality measures. Here, a comparison with another several centrality measures (degree, closeness, betweenness and physarum in weighted networks and semi-local centrality, LeaderRank and PageRank in unweighted networks) is also provided to shown the differences among them.

Two numerical Examples

The first simple example is a weighted network with 5 nodes and 6 weighted edges, which is adopted from [53], as illustrated in Figure 2.

thumbnail

Figure 2. A weighted example network.

doi:10.1371/journal.pone.0066732.g002

Due to symmetry of the network, the influence scores of node 1 and 2, or node 4 and 5 should be the same, regardless of which centrality measure is taken. However, the results listed in Table 1 show that degree centrality ranks the node 1, 2, 4 and 5 as the same ranking score, while betweenness centrality, closeness centrality and our method have consistent results as node 4 and 5 have greater centrality value than node 1 and 2.

thumbnail

Table 1. Influence scores based on different centrality methods for network in Figure 2.

doi:10.1371/journal.pone.0066732.t001

To further illustrate the difference between our method and other centrality measures in weighted and unweighted networks, respectively, we develop another example from [54]. As illustrated in Figure 3, node 1, 2, 3, 4, 5 and 15 colored in yellow are located at the periphery of the network and assigned with value 1. Node 7, 10, 11 and 14 with value 2 are on the second layer. Node 6, 8, 9, 12 and 13 are at the core of the network.

thumbnail

Figure 3. A weighted example network with 15 nodes and 21 weighted edges.

K-shell decomposition analysis is applied to this network. Different value paint in different colors. Nodes 1, 2, 3, 4, 5 and 15 colored in yellow are at the periphery of the network. Nodes 7, 10, 11 and 14 colored in blue are located at the second layer. Nodes 6, 8, 9, 12 and 13 are apparently on the core of the network.

doi:10.1371/journal.pone.0066732.g003

To evaluate the performance, we use a variant of the SI model adopted from [55] to study the dynamical evolution of epidemic spreading process in weighted networks. In this model, individuals can be in two discrete states: (i) Susceptible S(t) represents the number of individuals susceptible to the disease, not yet infected; (ii) Infected I(t) denotes the number of individuals that have been infected and are able to spread the disease to susceptible neighbors. At each step, one node is set to be infected initially and Then each infected node spreads disease or information to randomly one of its susceptible neighbors with probability in weighted networks (such a model is usually to mimic the limited spreading capability of individuals),(9)

where is a positive constant and is the largest value of in the network. For weighted networks, we assume that weight denote connection strength through link . For example, more familiar two individuals (with larger weight) may infect each with greater probability. Since , the smaller is, more quickly the disease or information spreads. Here we use the total number of infected nodes at time t, denoted by F(t) as an indicator of influence evaluation. Larger F(t) value of a node is, larger spreading ability the node has. The process stops when there is no susceptible node to be infected, namely, at a stable state, denoted by F().

According to the results in Table 2, regardless of unweighted network or weighted network, node 6 have a larger F() value than node 5 due to its core position in the network, but physarum centrality () ranks node 5 higher than node 6. After taking the k-shell index into consideration, node 6 ranked by the proposed method is more central than node 5, which is consistent with ranking order by the SI spreading model. In the weighted network, the top-1 ranked by the proposed method is node 12 which has the largest F() (larger than node 6 ranked by closeness centrality and betweenness centrality as the top-1 node, node 13 by degree centrality). In addition, all the nodes with value 3 have larger spreading ability than others. This demonstrates the k-shell index of nodes plays an important role of ranking influential nodes in networks.

thumbnail

Table 2. Simulations of effectiveness on the network illustrated in Figure 3.

doi:10.1371/journal.pone.0066732.t002

Applications in Real-world Networks

In this section, applications to three real networks are given to demonstrate our the flexible adaptability and efficiency of the proposed method. (i) The US Air line network it has 322 air ports and the air line between two air port can be denoted as a connection between two nodes in the network. The data can be downloaded from . (ii) Club network [56] the undirected Zachary's “karate club ” networks of 1977. The data are collected from the members of a university karate club by Wayne Zachary over two years. Zachary constructed a weighted network by denoting each member in the club as a node. Each edge in the network represents the connected two members are friends outside the club activities and its weight indicates the relative strength of the associations (number of situations in and outside the club in which interactions occurred). (iii) Citation network [57] this data set consists of paper and citation relationship chosen from Arnetminer. There are 235 nodes and 411 edges in this unweighted network. The basic topological properties of these three networks are shown in Table 3.

thumbnail

Table 3. The basic topological features of the two real networks.

doi:10.1371/journal.pone.0066732.t003

In the US Air lines network, the initial ranking of top-20 air ports by the proposed method are listed on the 2nd column in Table 4. Then, three air ports of the top-10 are randomly selected to be removed node 118, 261 and 313. In our common belief, after topology is changed, the ranking orders will not change at all. Actually, node 8 is ranked as second order at the initial state. After randomly removing three nodes, node 8 drops to the 10th place, rather than top 1. In this case, Dijkstra's algorithm needs to traverse the whole nodes network again, which leads to high computational complexity, while physarum can just adapt the flux though tubes dynamically and finally new influence score of each node will be obtained. The adaptivity of the proposed method is very useful to identify the influential node when the topology of networks is changed dynamically.

thumbnail

Table 4. The different order of top-20 nodes at the initial status and final status.

doi:10.1371/journal.pone.0066732.t004

In the Club network, the top-5 nodes ranked by the proposed method, degree centrality, closeness centrality and betweenness centrality are listed Table 5. Obviously, we need to distinguish the spreading ability among node 1, 3, 20 and 34 in order to efficiency of the proposed method. Here, we let infecting probability be 1.2 or 1.8 in order to slow down the spreading process. In Figures 4, 5, 6, 7, node 1 has greater F(t) value than node 3 regardless of 's value. There is subtle difference between node 1 and 34 in the aspects of spreading speed and stability. Besides, it is obvious that node 3 have much greater F(t) value than node 33 and 20 which is ranked by closeness and betweenness centrality as the third best influential node. Hence, the proposed method correctly identifies the most influential nodes in the Club network.

thumbnail

Figure 4. Comparison of spreading ability among node 1, 3 and 34.

For each node, F(t) is obtained by averaging over 100 implementations ( = 1.2).

doi:10.1371/journal.pone.0066732.g004
thumbnail

Figure 5. Comparison of spreading ability among node 1, 3 and 34.

For each node, F(t) is obtained by averaging over 100 implementations ( = 1.8).

doi:10.1371/journal.pone.0066732.g005
thumbnail

Figure 6. Comparison of spreading ability among node 3, 33 and 20.

For each node, F(t) is obtained by averaging over 100 implementations ( = 1.2).

doi:10.1371/journal.pone.0066732.g006
thumbnail

Figure 7. Comparison of spreading ability among node 3, 33 and 20.

For each node, F(t) is obtained by averaging over 100 implementations ( = 1.8).

doi:10.1371/journal.pone.0066732.g007
thumbnail

Table 5. The top-5 nodes ranked by the proposed method, degree, closeness and betweenness centrality.

doi:10.1371/journal.pone.0066732.t005

Furthermore, when considering the Citation network, we set the initial infected to be the nodes either appear as the top-L (top 5 and top 20) by the proposed method or each of the four measures (such as physarum centrality, but not appear in both), as shown in Table 6. In Figure 8 and 9, no matter what the top-L nodes are, both show that the proposed method performs a quicker and wider spreading than purely physarum centrality. The top-5 ranked by semi-local centrality is little faster than the proposed method, but in turn, the top-20 nodes ranked by our method perform much better than semi-local centrality. Besides, LeaderRank can perform better than the proposed method when comparing top-20 nodes. However, it is notable that there is little difference between the proposed method, PageRank and LeaderRank in Figure 8. Furthermore, in Figure 10, due to the same of the top-19 nodes ranked by purely K-shell index, there is no strictly top-5 in the condition. Therefore, we only compare the proposed method with purely K-shell index in the case of top-20. Obviously, top-20 nodes ranked by the proposed method have much more spreading ability than purely K-shell index.

thumbnail

Figure 8. Simulation of top-5 nodes with initial infected to appear by our method with other four methods respectively (but not both).

For each node, F(t) is obtained by averaging over 100 implementations ().

doi:10.1371/journal.pone.0066732.g008
thumbnail

Figure 9. Simulation of top-20 nodes with initial infected to appear by our method with other four methods respectively (but not both).

For each node, F(t) is obtained by averaging over 100 implementations ().

doi:10.1371/journal.pone.0066732.g009
thumbnail

Figure 10. Simulation of top-20 with initial infected to appear by our method with k-shell index (but not both).

For each node, F(t) is obtained by averaging over 100 implementations ().

doi:10.1371/journal.pone.0066732.g010
thumbnail

Table 6. The top-20 nodes ranked by different methods.

doi:10.1371/journal.pone.0066732.t006

Conclusions

Identifying the most influential nodes in a weighted network has great physical and theoretical meanings. In this paper, a bio-inspired measure is proposed for identifying influential nodes in weighted networks. We have made a tradeoff between the physarum centrality and the k-shell index obtained by the k-shell decomposition analysis. To evaluate the performance, the SI model is used to distinguish the difference of top-L nodes ranked by different centrality measures. Compared with existing methods, experiment results show that the proposed method can well identify influential nodes, even in dynamic complex networks.

Acknowledgments

We greatly appreciate the editor's encouragement and the anonymous reviewer's valuable comments and suggestions to improve this work. We are also grateful to Haixin Zhang, Yuxian Du and Daijun Wei for their comments on an earlier version of the paper and Yajuan Zhang for discussions and comparison of Physarum centrality in the revised paper.

Author Contributions

Conceived and designed the experiments: YD CG XL XZ. Analyzed the data: CG. Wrote the paper: YD. Analytical and numerical calculations: CG.

References

  1. 1. Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45: 167–256. doi: 10.1137/s003614450342480
  2. 2. Szolnoki A, Xie NG, Ye Y, Perc M (2013) Evolution of emotions on networks leads to the evolution of cooperation in social dilemmas. Phys Rev E 87: 042805. doi: 10.1103/physreve.87.042805
  3. 3. Albert R, Barabási AL (2002) Statistical mechanics of complex networks. Rev Mod Phys 74: 47–97. doi: 10.1103/revmodphys.74.47
  4. 4. Masuda N, Kurahashi I, Onari H (2013) Suicide ideation of individuals in online social networks. PLoS ONE 8: 0062262. doi: 10.1371/journal.pone.0062262
  5. 5. Perc M (2006) Coherence resonance in a spatial prisoner’s dilemma game. New J Phys 8: 22. doi: 10.1088/1367-2630/8/2/022
  6. 6. Lü L, Zhang YC, Yeung CH, Zhou T (2011) Leaders in social networks, the delicious case. PLoS ONE 6: e21202. doi: 10.1371/journal.pone.0021202
  7. 7. Zhou T, Medo M, Cimini G, Zhang ZK, Zhang YC (2011) Emergence of scale-free leadership structure in social recommender systems. PLoS ONE 6: e20648. doi: 10.1371/journal.pone.0020648
  8. 8. Zhang J, Jin Z, Sun GQ, Zhou T, Ruan S (2011) Analysis of rabies in china: transmission dynamics and control. PLoS ONE 6: e20891. doi: 10.1371/journal.pone.0020891
  9. 9. Perc M, Szolnoki A (2008) Social diversity and promotion of cooperation in the spatial prisoner’s dilemma game. Phys Rev E 77: 011904. doi: 10.1103/physreve.77.011904
  10. 10. Cheng Z, Zhang HT, Chen MZ, Zhou T, Valeyev NV (2011) Aggregation pattern transitions by slightly varying the attractive/repulsive function. PLoS ONE 6: e22123. doi: 10.1371/journal.pone.0022123
  11. 11. Wei D, Deng X, Zhang X, Deng Y, Mahadevan S (2013) Identifying influential nodes in weighted networks based on evidence theory. Physica A 392: 2564–2575. doi: 10.1016/j.physa.2013.01.054
  12. 12. Perc M (2007) Stochastic resonance on excitable small-world networks via a pacemaker. Phys Rev E 76: 066203. doi: 10.1103/physreve.76.066203
  13. 13. Jiang LL, Perc M, Wang WX, Lai YC, Wang BH (2011) Impact of link deletions on public cooperation in scale-free networks. EPL 93: 40001. doi: 10.1209/0295-5075/93/40001
  14. 14. Lü L, Zhang Z, Zhou T (2013) Deviation of zipf’s and heaps’ laws in human languages with limited dictionary sizes. Scientific Reports 3..
  15. 15. Yan G, Zhou T, Wang J, Fu ZQ, Wang BH (2005) Epidemic spread in weighted scale-free networks. Chin Phys Lett 22: 510–513. doi: 10.1088/0256-307x/22/2/068
  16. 16. Albert R, Albert I, Nakarado GL (2004) Structural vulnerability of the north american power grid. Phys Rev E 69: 025103 (R).. doi: 10.1103/physreve.69.025103
  17. 17. Perc M (2009) Evolution of cooperation on scale-free networks subject to error and attack. New J Phys 11: 033027. doi: 10.1088/1367-2630/11/3/033027
  18. 18. Perc M, Gómez-Gardeñes J, Szolnoki A, Floría LM, Moreno Y (2013) Evolutionary dynamics of group interactions on structured populations: a review. Journal of The Royal Society Interface 10..
  19. 19. Perc M, Szolnoki A, Szabó G (2008) Restricted connections among distinguished players support cooperation. Phys Rev E 78: 066101. doi: 10.1103/physreve.78.066101
  20. 20. Szolnoki A, Perc M (2013) Effectiveness of conditional punishment for the evolution of public cooperation. Journal of Theoretical Biology.
  21. 21. Perc M (2005) Spatial coherence resonance in excitable media. Phys Rev E 72: 016207. doi: 10.1103/physreve.72.016207
  22. 22. Chen X, Szolnoki A, Perc M (2012) Risk-driven migration and the collective-risk social dilemma. Phys Rev E 86: 036101. doi: 10.1103/physreve.86.036101
  23. 23. Gao Y, Cai S, Lü L, Wang B (2013) Evolutionary model on market ecology of investors and investments. Physica A : doi:10.1016/j.bbr.2011.03.031.
  24. 24. Liu W, Lü L (2010) Link prediction based on local random walk. EPL 89: 58007. doi: 10.1209/0295-5075/89/58007
  25. 25. Lü L, Liu W (2011) Information filtering via preferential diffusion. Phys Rev E 83: 066119. doi: 10.1103/physreve.83.066119
  26. 26. Hartwell LH, Hopfield JJ, Leibler S, Murray AW (1999) From molecular to modular cell biology. Nature 402: C47–C52. doi: 10.1038/35011540
  27. 27. Chen D, Lü L, Shang MS, Zhou T (2012) Identifying influential nodes in complex networks. Physica A 391: 1777–1787. doi: 10.1016/j.physa.2011.09.017
  28. 28. Jordán F, Benedek Z, Podani J (2007) Quantifying positional importance in food webs: A comparison of centrality indices. Ecological Modelling 205: 270–275. doi: 10.1016/j.ecolmodel.2007.02.032
  29. 29. Kolaczyk ED, Chua DB, Barthélemy M (2009) Group betweenness and co-betweenness: Interrelated notions of coalition centrality. Social Networks 31: 190–203. doi: 10.1016/j.socnet.2009.02.003
  30. 30. Wang F, Antipova A, Porta S (2011) Street centrality and land use intensity in baton rouge, louisiana. Journal of Transport Geography 19: 285–293. doi: 10.1016/j.jtrangeo.2010.01.004
  31. 31. Zhang H, Fiszman M, Shin D, Miller CM, Rosemblat G, et al. (2011) Degree centrality for semantic abstraction summarization of therapeutic studies. Journal of Biomedical Informatics 44: 830–838. doi: 10.1016/j.jbi.2011.05.001
  32. 32. Zio E, Sansavini G (2011) Component criticality in failure cascade processes of network systems. Risk Analysis 31: 1196–1210. doi: 10.1111/j.1539-6924.2011.01584.x
  33. 33. Pathak PH, Dutta R (2012) Centrality-based power control for hot-spot mitigation in multi-hop wireless networks. Computer Communications 35: 1074–1085. doi: 10.1016/j.comcom.2012.01.023
  34. 34. Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, et al. (2010) Identification of influential spreaders in complex networks. Nature Phys 6: 888–893. doi: 10.1038/nphys1746
  35. 35. Barthelemy M (2004) Betweenness centrality in large complex networks. The European Physical Journal B-Condensed Matter and Complex Systems 38: 163–168. doi: 10.1140/epjb/e2004-00111-4
  36. 36. Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: bringing order to the web. Technical Report Stanford InfoLab : 1999–66.
  37. 37. Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems 30: 107–117. doi: 10.1016/s0169-7552(98)00110-x
  38. 38. Bonacich P, Lloyd P (2001) Eigenvector-like measures of centrality for asymmetric relations. Social Networks 23: 191–201. doi: 10.1016/s0378-8733(01)00038-7
  39. 39. Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18: 39–43. doi: 10.1007/bf02289026
  40. 40. Estrada E, Rodriguez-Velazquez JA (2005) A subgraph centrality in complex networks. Phys Rev E 71: 056103. doi: 10.1103/physreve.71.056103
  41. 41. Zhang Y, Zhang Z, Wei D, Deng Y (2012) Centrality measure in weighted networks based on an amoeboid algorithm. Journal of Information and Computationnal Science 9: 369–376.
  42. 42. Zhang Y, Zhang Z, Deng Y, Mahadevan S (2013) A biologically inspired solution for fuzzy shortest path problems. Applied Soft Computing 13: 2356–2363. doi: 10.1016/j.asoc.2012.12.035
  43. 43. Zhang X, Deng Y, Chan FTS, Xu P, Mahadevan S, et al.. (2013) Solving 0-1 knapsack problems based on amoeboid organism algorithm. International Journal of Production Research : doi:10.1016/j.amc.2013.04.023.
  44. 44. Zhang X, Hu Y, Zhang Y, Deng Y, Mahadevan S (2013) Ifsjsp: A novel methodology for the jobshop scheduling problem based on intuitionistic fuzzy sets. Applied Mathematics and Computation: doi:10.1080/00207543.2013.793425.
  45. 45. Seidman SB (1983) Network structure and minimun degree. Social Networks 5: 269–287. doi: 10.1016/0378-8733(83)90028-x
  46. 46. Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E (2007) A model of internet topology using k-shell decomposition. Proceedings of the National Academy of Sciences 104: 11150–11154. doi: 10.1073/pnas.0701175104
  47. 47. Yang R, Wang B, Ren J, BaiW, Shi Z, et al. (2007) Epidemic spreading on heterogeneous networks with identical infectivity. Phys Lett A 364: 189–193. doi: 10.1016/j.physleta.2006.12.021
  48. 48. Zhou T, Liu JG, Bai WJ, Chen G, Wang BH (2006) Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity. Phys Rev E 74: 056109. doi: 10.1103/physreve.74.056109
  49. 49. Tero A, Kobayashi R, Nakagaki T (2007) A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology 244: 553–564. doi: 10.1016/j.jtbi.2006.07.015
  50. 50. Tero A, Yumiki K, Kobayashi R, Saigusa T, Nakagaki T (2008) Flow-network adaptation in physarum amoebae. Theory in Biosciences 127: 89–94. doi: 10.1007/s12064-008-0037-9
  51. 51. Barrat A, Barthélémy M, Pastor-Satorras R, Vespignani A (2004) The architecture of complex weighted networks. Proceedings of the National Academy of Sciences 101: 3747–3752. doi: 10.1073/pnas.0400087101
  52. 52. Tero A, Kobayashi R, Nakagaki T (2006) Physarum solver: A biologically inspired method of road-network navigation. Physica A 363: 115–119. doi: 10.1016/j.physa.2006.01.053
  53. 53. Opsahl T, Agneessens F, Skvoretz J (2010) Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32: 245–251. doi: 10.1016/j.socnet.2010.03.006
  54. 54. Miorandi D, De Pellegrini F (2010) K-shell decomposition for dynamic complex networks. In: WiOpt’10: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks. IEEE, pp.488–496.
  55. 55. Yan G, Zhou T, Wang J, Fu Z, Wang B (2005) Epidemic spread in weighted scale-free networks. Chin Phys Lett 22: 510. doi: 10.1088/0256-307x/22/2/068
  56. 56. Zachary WW (1977) An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33: 452–473.
  57. 57. Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 807–816.