Identification of influential spreaders in complex networks

Identification of influential spreaders in complex networksSummaryIntroductionArgumentGeneral ApproachWhen hubs may not be good spreadersk-shell predicts spreadingk-shell structureSIS Spreading





"Here we argue that the topology of the network organization plays an important role such that there are plausible circumstances under which the highly connected nodes or the highest-betweenness nodes have little effect on the range of a given spreading process. For example, if a hub exists at the end of a branch at the periphery of a network, it will have a minimal impact in the spreading process through the core of the network, whereas a less connected person who is strategically placed in the core of the network will have a significant effect that leads to dissemination through a large fraction of the population."


General Approach


When hubs may not be good spreaders


k-shell predicts spreading

"To quantify the influence of a given node in an SIR spreading process we study the average size of the population Mi infected in an epidemic originating at node with a given (,). The infected population is averaged over all the origins with the same (,) values:

where , is the union of all nodes with values."

Studying lead to three general results (illustrated in Fig. 2 (a,c,e,g))

  1. For a fixed degree, there is a wide spread of values.

    1. Importantly, there are many hubs located at the periphery of the network (large , low ) that are poor spreaders.
  2. For a fixed k—shell, is approximately independent of the degree of the nodes.

    1. We see this in the vertically layered structure of , which suggests that infected nodes located in the same k—shell produce similar epidemic outbreaks, independent of the value of at the infection origin.
  3. The most efficient spreaders are located in the inner core of the network (large region), fairly independently of their degree

"These results indicate that the k—shell index of a node is a better predictor [than degree ()] of spreading influence. When an outbreak starts in the core of the network (large ) there exist many pathways through which a virus can infect the rest of the network; this result is valid regardless of the node degree."

"Similar results on the efficiency of high— nodes are obtained from the analysis of in Fig. 2 (b,d,f,h), where is the betweenness centrality of a node in the network: the value of is not a good predictor for spreading efficiency."


k-shell structure


SIS Spreading

The spreading efficiency of a given node in SIS spreading is the persistence, , defined as the probability that node is infected at time .

Previous studies have shown that the largest persistence is found in the network hubs.

"However, we find that this result holds only in randomized network structures. In the real network topologies studied here, we find that viruses persist mainly in high- layers instead, almost irrespectively of the degree of the nodes in the core." Fig. 4 a, b

"Note that a virus cannot survive in the degree-preserving randomized version of the CNI network, owing to the absence of high-k shells. The importance of the inner-core nodes in spreading is not influenced by the infection probability values, . In both models, SIS and SIR, we find that the persistence or the average infected fraction , respectively, is systematically larger for nodes in inner shells compared with nodes in outer shells, over the entire range that we studied (Fig. 4c,d). Thus, the k-shell measure is a robust indicator for the spreading efficiency of a node."


Notes by Matthew R. DeVerna