Ranking spreaders by decomposing complex networks

Abstract

Ranking the nodes' ability for spreading in networks is a fundamental problem which relates to many real applications such as information and disease control. In the previous literatures, a network decomposition procedure called k-shell method has been shown to effectively identify the most influential spreaders. In this paper, we find that the k-shell method have some limitations when it is used to rank all the nodes in the network. We also find that these limitations are due to considering only the links between the remaining nodes (residual degree) while entirely ignoring all the links connecting to the removed nodes (exhausted degree) when decomposing the networks. Accordingly, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic process on the real networks, we show that the MDD method can outperform the k-shell and the degree methods in ranking spreaders. Finally, the influence of the network structure on the performance of the MDD method is discussed.

6 pages, 5 figures

References in corpus (30)

• Emergence of scaling in random networks
• Epidemic spreading in scale-free networks
• Lethality and centrality in protein networks
• Finding community structure in networks using the eigenvectors of matrices
• The structure of scientific collaboration networks
• Catastrophic cascade of failures in interdependent networks
• The large-scale organization of metabolic networks
• Identification of influential spreaders in complex networks
• Critical phenomena in complex networks
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Efficient Immunization Strategies for Computer Networks and Populations
• Community Structure in Jazz
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Cascade control and defense in complex networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• Thresholds for epidemic spreading in networks
• k-core organization of complex networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Epidemic threshold in structured scale-free networks
• A k-shell decomposition method for weighted networks
• Absence of influential spreaders in rumor dynamics
• Identifying the starting point of a spreading process in complex networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Worldwide spreading of economic crisis
• Adaptive model for recommendation of news
• Enhancing synchronization by directionality in complex networks
• Optimal Tree for Both Synchronizability and Converging Time
• Decelerated spreading in degree-correlated networks

Cited by in corpus (27)

• Epidemic processes in complex networks
• Vital nodes identification in complex networks
• Identifying influential spreaders in complex networks based on gravity formula
• Ranking the spreading influence in complex networks
• Spreading dynamics in complex networks
• Identifying Influential Spreaders by Weighted LeaderRank
• A Survey on Centrality Metrics and Their Implications in Network Resilience
• Path diversity improves the identification of influential spreaders
• M-Centrality: identifying key nodes based on global position and local degree variation
• Identifying effective multiple spreaders by coloring complex networks
• Spatial super-spreaders and super-susceptibles in human movement networks
• Influence Maximization in Social Networks: A Survey of Behaviour-Aware Methods
• Top influencers can be identified universally by combining classical centralities
• Influencers identification in complex networks through reaction-diffusion dynamics
• Centrality Measures in Complex Networks: A Survey
• Identification of highly susceptible individuals in complex networks
• Weighted H-index for identifying influential spreaders
• Predicting Item Popularity: Analysing Local Clustering Behaviour of Users
• Inferring network topology via the propagation process
• EMH: Extended Mixing H-index centrality for identification important users in social networks based on neighborhood diversity
• Finding the proper node ranking method for complex networks
• Locating influential nodes via dynamics-sensitive centrality
• Maximizing spreading in complex networks with risk in node activation
• Lowest Degree Decomposition of Complex Networks
• The spreading ability of nodes towards localized targets in complex networks
• Promotion and resignation in employee networks
• A novel method based on node correlation to evaluate the important nodes in complex networks