Abstract
Influential spreaders are used to maximize or control the spreading dynamics in a network. It acts as a maximizer in the case of information dissemination and a controller to control the epidemic spreading. In the literature, researchers are mostly focused on finding the best spreader from an undirected network. Indeed, the edge’s direction of a spreading process in the network has immense significance while estimating the influential spreaders. This paper presents a novel method, i.e., the “crossbred method” to identify the best spreaders for a directed network. The proposed method considers the spreading properties of the directed network. It takes account of two popular parameters of a spreading process, i.e., node’s out-degree and spreading’s reachability of an originator node. We have verified the spreading performance of the proposed method with the Directed Susceptible-Infected-Recovered (SIR) spreading epidemic model on six real networks. The outcome of the investigation demonstrates that the proposed method achieved significant improvement in terms of spreading dynamics over the existing methods of directed networks such as out-degree centrality, betweenness centrality, pagerank centrality, eigenvector centrality, cluster-rank centrality, outgoing closeness centrality, hybrid centrality.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Directed network. http://konect.cc/networks/
Ahajjam, S., Badir, H.: Identification of influential spreaders in complex networks using hybridrank algorithm. Sci. Rep. 8(1), 1–10 (2018)
Alemany, J., Del Val, E., Alberola, J.M., Garćia-Fornes, A.: Metrics for privacy assessment when sharing information in online social networks. IEEE Access 7, 143631–143645 (2019)
Bhat, N., Aggarwal, N., Kumar, S.: Identification of influential spreaders in social networks using improved hybrid rank method. Procedia Comput. Sci. 171, 662–671 (2020)
Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92(5), 1170–1182 (1987)
Brodka, P., Musial, K., Kazienko, P.: A performance of centrality calculation in social networks. In: 2009 International Conference on Computational Aspects of Social Networks, pp. 24–31. IEEE (2009)
Chen, D.B., Gao, H., Lü, L., Zhou, T.: Identifying influential nodes in large-scale directed networks: the role of clustering. PLoS ONE 8(10), e77455 (2013)
Chen, G., Xu, C., Wang, J., Feng, J., Feng, J.: Nonnegative matrix factorization for link prediction in directed complex networks using pagerank and asymmetric link clustering information. Expert Syst. Appl. 113290 (2020)
Dorogovtsev, S.N., Goltsev, A.V., Mendes, J.F.: Critical phenomena in complex networks. Rev. Mod. Phys. 80(4), 1275 (2008)
Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 35–41 (1977)
Freeman, L.C., et al.: Centrality in social networks: conceptual clarification. In: Social Network: Critical Concepts in Sociology, pp. 238–263. Routledge, London (2002)
Kendall, M.G.: The treatment of ties in ranking problems (1945)
Knight, W.R.: A computer method for calculating Kendall’s tau with ungrouped data. J. Am. Stat. Assoc. 61(314), 436–439 (1966)
Kumar, R., Manuel, S.: A centrality measure for directed networks: m-ranking method. In: Social Networks and Surveillance for Society, pp. 115–128 (2019)
Li, C., Wang, H., Van Mieghem, P.: Epidemic threshold in directed networks. Phys. Rev. E 88(6), 062802 (2013)
Lü, L., Zhang, Y.C., Yeung, C.H., Zhou, T.: Leaders in social networks, the delicious case. PLoS ONE 6(6), e21202 (2011)
Maurya, S.K., Liu, X., Murata, T.: Fast approximations of betweenness centrality with graph neural networks. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 2149–2152 (2019)
Maurya, S.K., Liu, X., Murata, T.: Graph neural networks for fast node ranking approximation. ACM Trans. Knowl. Disc. Data 15, 1–32 (2021)
Namtirtha, A., Dutta, A., Dutta, B.: Identifying influential spreaders in complex networks based on kshell hybrid method. Phys. A 499, 310–324 (2018)
Namtirtha, A., Dutta, A., Dutta, B.: Weighted kshell degree neighborhood method: an approach independent of completeness of global network structure for identifying the influential spreaders. In: 2018 10th International Conference on Communication Systems & Networks (COMSNETS), pp. 81–88. IEEE (2018)
Namtirtha, A., Dutta, A., Dutta, B., Sundararajan, A., Simmhan, Y.: Best influential spreaders identification using network global structural properties. Sci. Rep. 11(1), 1–15 (2021)
Newman, M.: Networks: An Introduction. Oxford University Press, New York (2010)
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Technical report, Stanford infolab (1999)
Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86(14), 3200 (2001)
Pei, S., Morone, F., Makse, H.A.: Theories for influencer identification in complex networks. In: Complex Spreading Phenomena in Social Systems: Influence and Contagion in Real-World Social Networks, pp. 125–148 (2018)
Putman, K., Boekhout, H.D., Takes, F.W.: Fast incremental computation of harmonic closeness centrality in directed weighted networks. In: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 1018–1025 (2019)
Wang, J., Hou, X., Li, K., Ding, Y.: A novel weight neighborhood centrality algorithm for identifying influential spreaders in complex networks. Phys. A 475, 88–105 (2017)
Wang, J., Mo, H., Wang, F., Jin, F.: Exploring the network structure and nodal centrality of china’s air transport network: a complex network approach. J. Transp. Geogr. 19(4), 712–721 (2011)
White, D.R., Borgatti, S.P.: Betweenness centrality measures for directed graphs. Soc. Netw. 16(4), 335–346 (1994)
Yeruva, S., Devi, T., Reddy, Y.S.: Selection of influential spreaders in complex networks using pareto shell decomposition. Phys. A 452, 133–144 (2016)
Zhang, P., Wang, T., Yan, J.: Pagerank centrality and algorithms for weighted, directed networks. Physica A Stat. Mech. Appl. 586, 126438 (2022)
Acknowledgment
The Visvesvaraya Ph.D. scheme, MeitY, Govt. of India, provided funding for this research project.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Saha, N., Namtirtha, A., Dutta, A. (2024). Crossbred Method: A New Method for Identifying Influential Spreaders from Directed Networks. In: Cherifi, H., Rocha, L.M., Cherifi, C., Donduran, M. (eds) Complex Networks & Their Applications XII. COMPLEX NETWORKS 2023. Studies in Computational Intelligence, vol 1144. Springer, Cham. https://doi.org/10.1007/978-3-031-53503-1_32
Download citation
DOI: https://doi.org/10.1007/978-3-031-53503-1_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-53502-4
Online ISBN: 978-3-031-53503-1
eBook Packages: EngineeringEngineering (R0)