A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques. (15th December 2020)

• Record Type: Journal Article
• Authors: Maji, Giridhar; Mandal, Sharmistha; Sen, Soumya
• Is Part Of: Expert systems with applications. Volume 161(2020)
• Publication Date: 2020-12-15
• Subjects: K-shell decomposition -- Systematic review -- Node centrality -- Influential spreader identification -- Node ranking heuristics -- Kendall's rank correlation -- Influence maximization; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.113681
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Identification of important nodes in complex networks have real world applications. Basic centrality measures along with K-shell decomposition yield impressive results. Many topology based heuristics rank nodes with lower time complexities. Systematically compared representative state-of-the-art heuristics with example. SIR epidemic model and performance evaluation metrics are thoroughly investigated. Abstract: Almost all the complex interactions between humans, animals, biological cells, neurons, or any other objects are now modeled as a graph with the nodes as the objects of interest and interactions as the edges. The identification of the most central or influential node in such a complex network has many practical applications in diverse domains such as viral marketing, infectious disease spreading, rumor spreading in a social network, virus/worm spreading in computer networks, etc. Many centrality measures using the position/location of a node and network structure have been proposed in the literature. The node degree, shortest paths (closeness), and betweenness are used since long with degree capturing local effect and others global effect. The k-shell considers the coreness of the nodes by dividing the network into layers or shells. Many variations of k-shell proposed in recent years, as well as many researchers, use k-shell as a building block in their heuristic technique to alleviate the problems of classical k-shell and to identify influential spreaders more elegantly. The main objective of this paper is to analyze and compare the major variations of the k-shell based methods along with representative network topology based hybrid techniques by considering a toy network with detailed computations. A discussion on different performance evaluation metrics and, simulation models such as the SIR epidemic model, has been undertaken with a comparative analysis between different state-of-the-art on a few standard real networks.