Networks portray a multitude of interactions through which people meet, ideas are spread, and infectious diseases propagate within a society [1] [2] [3] [4] [5] . Identifying the most efficient "spreaders" in a network is an important step to optimize the use of available resources and ensure the more efficient spread of information. Here we show that, in contrast to common belief, there are plausible circumstances where the best spreaders do not correspond to the best connected people or to the most central people (high betweenness centrality) [6] [7] [8] [9] [10] . Instead, we find: (i) The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis [11] [12] [13] . (ii) When multiple spreaders are considered simultaneously, the distance between them becomes the crucial parameter that determines the extent of the spreading. Furthermore, we find that infections persist in the high k-shells of the network, even in the case where recovered individuals do not develop immunity. Our analysis provides a plausible route for an optimal design of efficient dissemination strategies. Spreading is a ubiquitous process which describes many important activities in society [2] [3] [4] [5] . The knowledge of the spreading pathways through the network of social interactions is crucial for developing efficient methods to either hinder spreading in the case of diseases, or accelerate spreading in the case of information dissemination. Indeed, people are connected according to the way they interact with each other in society and the large heterogeneity of the resulting network greatly determines the efficiency and speed of spreading. In the case of networks with a broad degree distribution (number of links per node) [6] , it is believed that the most connected people (hubs) are the key players being responsible for the largest scale of the spreading process [6] [7] [8] . Furthermore, in the context of social network theory, the importance of a node for spreading is often associated with the betweenness centrality, a measure of how many shortest paths cross through this node, which is believed to determine who has more 'interpersonal influence' on others [9, 10]. 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 in 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, while a less connected 2 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. In order to identify the core and the periphery of the network we use the k-shell (also called k-core) decomposition of the network [11] [12] [13] [14] . Examining this quantity in a number of real networks allows us to identify the best individual spreaders in the network when the spreading originates in a single node. For the case of a spreading process originating in many nodes simultaneously we show that we can further improve the efficiency by considering spreading origins located at a determined distance from each other. We study real-world complex networks that represent archetypical examples of social structures. We investigate (i) the friendship network between 3.4 million members of the To study the spreading process we apply the Susceptible-Infectious-Recovered (SIR) and Susceptible-Infectious-Susceptible (SIS) models [2, 3, 18] on the above networks (see Methods section). These models have been used to describe disease spreading as well as information and rumor spreading in social processes where an actor constantly needs to be reminded [19] . We denote the probability that an infectious node will infect a susceptible neighbor as β. In our study we use relatively small values for β, so that the infected percentage of the population remains small. In the case of large β values, where spreading can reach a large fraction of the population, the role of individual nodes is no longer important and spreading would cover almost all the network, independently of where it originated from. The location of a node in the network is obtained using the k-shell decomposition analysis [11] [12] [13] . This process assigns an integer index or coreness, k S , to each node representing its location according to successive layers (k-shells) in the network. The k S index is a quite robust measure and the nodes ranking is not influenced significantly in the case of incomplete information (for details see in SI-Section II). Small values of k S define the periphery of the network and the innermost network core corresponds to large k S (see The above example suggests that the position of the node relative to the organization of the network determines its spreading influence more than a local property of a node, like the degree k. To quantify the influence of a given node i in an SIR spreading process we study the average size of the population M i infected in an epidemic originating at node i with a given (k S , k). The infected population is averaged over all the origins with the same where The analysis of M(k S , k) in the studied social networks reveals three general results (see These results indicate that the k-shell index of a node is a better predictor of spreading influence. When an outbreak starts in the core of the network (large k S ) there exist many pathways through which a virus can infect the rest of the network; this result is valid regardless of the node degree. The existence of these pathways implies that during a typical epidemic outbreak from a random origin, nodes located in high k S layers are more likely to be infected and they will be infected earlier than other nodes (see SI-Section III). The neighborhood of these nodes makes them more efficient in sustaining an infection at the early stages, allowing thus the epidemics to reach a critical mass that will allow it to fully develop. Similar results on the efficiency of high-k S nodes are obtained from the analysis Fig. 2 , where C B is the betweenness centrality of a node in the network [9, 10] : the value of C B is not a good predictor for spreading efficiency. To quantify the importance of k S in spreading we calculate the "imprecision functions" , and ǫ C B (p). These functions estimate for each of the three indicators k S , k, and C B how close to the optimal spreading is the average spreading of the pN (0 < p < 1) chosen origins in each case, (see Methods and SI-Section IV). The strategy to predict the spreading efficiency of a node based on k S is consistently more accurate than a method based on k in the studied p-range (Fig. 3a) . The C B -based strategy gives poor results compared to the other two strategies. Our finding is not specific to the social networks shown in Fig. 2 . In SI-Section V we analyze the spreading efficiency in other networks not social in origin, like the Internet at the router level [20] , with similar conclusions. The key insight of our finding is that in the studied networks a large number of hubs are located in the peripheral low k S layers (Fig. 3b shows the location of the 25 largest hubs in the CNI, see also SI-Section V) and therefore contribute poorly to spreading. The existence of hubs in the periphery is a consequence of the rich topological structure of real networks. In contrast, in a fully random network obtained by randomly rewiring a real network preserving the degree of each node (such a random network corresponds to the configuration model [21] , see SI-Section VI) all the hubs are placed in the core of the network (see the red scatter plot in Fig. 3c ) and they contribute equally largely to spreading. In such a randomized structure the same information is contained in the k-shell as in the degree classification since there is a one to one relation between both quantities which is approximately linear, k S ∝ k (Fig. 3c and SI-Fig. 13 ). Examples of real networks that are similar to a random structure are the network of product space of economic goods [22] and the Internet at the AS level (analyzed in the SI-Section V). Our study highlights the importance of the relative location of a single spreading origin. Next, we address the question of the extent of an epidemic that starts in multiple origins simultaneously. Figure 3d shows the extent of SIR spreading in the CNI network when the outbreak simultaneously starts from the n nodes with the highest degree k or the highest k S index. Even though the high k S nodes are the best single spreaders, in the case of multiple spreading the nodes with highest degree are more efficient than those with highest k S . This result is attributed to the overlap of the infected areas of the different spreaders: large k S nodes tend to be clustered close to each other, while hubs can be more spread in 5 the network and, in particular, they need not be connected with each other. Clearly, the step-like features in the plot of highest k S nodes (red solid curve in Fig. 3d ) suggest that the infected percentage remains constant as long as the infected nodes belong in the same shell. Including just one node from a different shell results in a significantly increased spreading. This result suggests that a better spreading strategy using multiple n spreaders is to choose either the highest k or k S nodes with the requirement that no two of the n spreaders are directly linked to each other. This scheme then provides the largest infected area of the network as shown in Fig. 3d . confer full immunity after infection as assumed in the SIR model, and therefore are suitably described by the SIS epidemic model, where an infectious node returns to the susceptible state with probability λ. In an SIS epidemic the number of infectious nodes eventually reaches a dynamic equilibrium "endemic" state where as many infectious individuals become susceptible as susceptible nodes become infectious [18] . In contrast to SIR, in the initial state of our SIS simulations 20% of the network nodes are already infected. The spreading efficiency of a given node i in SIS spreading is the persistence, ρ i (t), defined as the probability that node i is infected at time t [7] . In an endemic SIS state, ρ i (t → ∞) becomes independent of t (see SI-Section VII). Previous studies have shown that the largest persistence ρ i (t → ∞) is found in the network hubs which are re-infected frequently due to the large number of neighbors [7, 24, 25] . 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 k S layers instead, irrespectively of the degree of the nodes in the core. In the case of random networks, it is found that viruses propagate to the entire network above an epidemic threshold given by β > β 24, 26] . In real networks, such as the CNI network, the threshold β c is different from β rand c . Furthermore, in real networks, we find that viruses can survive locally even when β < β c , but only within the high k S layers of the network, while virus persistence in peripheral k S layers is negligible (Fig. 4a-c ). Since the k-shell structure depends on the network assortativity the lower threshold is in agreement with the observation that high positive assortativity [27] may decrease the epidemic threshold. The importance of high k S nodes in SIS spreading is confirmed when we analyze the asymptotic probability that nodes of given (k S , k) values will be infected. This probability 6 is quantified by the persistence function as a function of (k S , k) at different β values (Fig. 4a and b) . High k S layers in networks might be closely related to the concept of a core group in Sexually Transmitted Infections research [23] . The core groups are defined as subgroups in the general population characterized by high partner turnover rate and extensive intergroup interaction [23] . Similar to the core group, the dense sub-network formed by nodes in the innermost kshells helps the virus to consistently survive locally in the inner-core area and infect other nodes adjacent to the area. These k-shells preserve the existence of a virus, in contrast to e.g. isolated hubs in the periphery. Note that a virus cannot survive in the degree-preserving randomized version of the CNI network, due 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 M, respectively, is systematically larger for nodes in inner k-shells compared to 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. Finding the most accurate ranking of individual nodes for spreading in a population can influence the success of dissemination strategies. When spreading starts from a single node, the k S value is enough for this ranking, while in the case of many simultaneous origins, spreading is greatly enhanced when we additionally repel the spreaders with large degree or k S . In the case of infections that do not confer immunity on recovered individuals, the core of the network in the large k S layers forms a reservoir where infection can survive locally. A. The k-shell decomposition Nodes are assigned to k-shells according to their remaining degree, which is obtained by successive pruning of nodes with degree smaller than the k S value of the current layer. We start by removing all nodes with degree k = 1. After removing all the nodes with k = 1, some nodes may be left with one link, so we continue pruning the system iteratively 7 until there is no node left with k = 1 in the network. The removed nodes, along with the corresponding links, form a k-shell with index k S = 1. In a similar fashion, we iteratively remove the next k-shell, k S = 2, and continue removing higher k-shells until all nodes are removed. As a result, each node is associated with a unique k S index, and the network can be viewed as the union of all k-shells. The resulting classification of a node can be very different than when the degree k is used. To study the spreading process we apply the Susceptible-Infectious-Recovered (SIR) and Susceptible-Infectious-Susceptible (SIS) models. In the SIR model, all nodes are initially in susceptible state (S) except for one node in the infectious state (I). At each time step, the I nodes attempt to infect their susceptible neighbors with probability β and then enter the recovered state (R) where they become immunized and cannot be infected again. The SIS model aims to describe spreading processes that do not confer immunity on recovered individuals: infected individuals still try to infect their neighbors with probability β but they return to the susceptible state with probability λ (here we use λ = 0.8) and can be reinfected at subsequent time steps, while they remain infectious with probability 1 − λ. The betweenness centrality, C B (i), of a node i is defined as follows: Consider two nodes s and t and the set σ st of all possible shortest paths between these two nodes. If the subset of this set that contains the paths that pass through the node i is denoted by σ st (i), then the betweenness centrality of this node is given by: where the sum runs over all nodes s and t in the network. The imprecision function ǫ(p) quantifies the difference in the average spreading between the pN nodes (0 < p < 1) with highest k S , k, or C B from the average spreading of the pN most efficient spreaders (N is the number of nodes in the network). Thus, it tests the merit of using k-shell, k and C B to identify the most efficient spreaders. For a given β value and 8 a given fraction of the system p we first identify the set of the Np most efficient spreaders as measured by M i (we designate this set by Υ eff ). Similarly, we identify the Np individuals with the highest k-shell index (Υ k S ). We define the imprecision of k-shell identification as ǫ k S (p) ≡ 1 − M k S /M eff , where M k S and M eff are the average infected percentages averaged over the Υ k S and Υ eff groups of nodes respectively. ǫ k and ǫ C B are defined similar to ǫ k S . [1] Caldarelli G., Vespignani A. (eds) Large scale structure and dynamics of complex networks.
Kitsak et al. REF propose Kl-shell in 2010, which is a method to determine the core of the network.
Identification of influential spreaders in complex networks
Nature Physics, 6, 888 (2010)
Physics