Abstract
Epidemics start within a network because of the existence of epidemic sources that spread information over time to other nodes. Data about the exact contagion pattern among nodes is often not available, besides a simple snapshot characterizing nodes as infected, or not. Thus, a fundamental problem in network epidemic is identifying the set of source nodes after the epidemic has reached a significant fraction of the network. This work tackles the multiple source detection problem by using graph neural network model to classify nodes as being the source of the epidemic. The input to the model (node attributes) are novel epidemic information in the k-hop neighborhoods of the nodes. The proposed framework is trained and evaluated under different network models and real networks and different scenarios, and results indicate different trade-offs. In a direct comparison with prior works, the proposed framework outperformed them in all scenarios available for comparison.
This work has received financial support through research grants from CNPq and FAPERJ (Brazil).
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
Notes
- 1.
Accessible on: https://github.com/rodrigohaddad/multiple-source-detector-gnn.
References
Barabási, A.L., Pósfai, M.: Network Science. Cambridge University Press, Cambridge (2016)
David, E., Jon, K.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York (2010)
Dong, M., Zheng, B., Quoc Viet Hung, N., Su, H., Li, G.: Multiple rumor source detection with graph convolutional networks. In: ACM International Conference on Information and Knowledge Management (CIKM), pp. 569–578 (2019)
Draief, M., Massouli, L.: Epidemics and Rumours in Complex Networks. Cambridge University Press, Cambridge (2010)
Feizi, S., Médard, M., Quon, G., Kellis, M., Duffy, K.: Network infusion to infer information sources in networks. IEEE Trans. Netw. Sci. Eng. 6(3), 402–417 (2019)
Fey, M., Lenssen, J.E.: Fast graph representation learning with PyTorch geometric. In: ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)
Firth, J., Hellewell, J., Klepac, P., Kissler, S., Kucharski, A., Spurgin, L.: Using a real-world network to model localized covid-19 control strategies. Nat. Med. 26, 1616–1622 (2020)
Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30(4), 1141–1144 (1959)
Hamilton, W.L., Ying, R., Leskovec, J.: Inductive representation learning on large graphs. In: NeurIPS, p. 1025–1035 (2017)
Jiang, J., Wen, S., Yu, S., Xiang, Y., Zhou, W.: K-center: an approach on the multi-source identification of information diffusion. IEEE Trans. Inf. Forensics Secur. 10(12), 2616–2626 (2015)
Jiang, J., Wen, S., Yu, S., Xiang, Y., Zhou, W.: Identifying propagation sources in networks: state-of-the-art and comparative studies. IEEE Commun. Surv. Tutor. 19(1), 465–481 (2017)
Kermack, W.O., McKendrick, A.G., Walker, G.T.: A contribution to the mathematical theory of epidemics. Roy. Soc. Lond. 115(772), 700–721 (1927)
Leskovec, J., Mcauley, J.: Learning to discover social circles in ego networks. In: NIPS (2012)
Newman, M.E.: Spread of epidemic disease on networks. Phys. Rev. E 66(1), 016128 (2002)
Pastor-Satorras, R., Castellano, C., Van Mieghem, P., Vespignani, A.: Epidemic processes in complex networks. Rev. Mod. Phys. 87(3), 925 (2015)
Paszke, A., Gross, S., Chintala, S.: PyTorch: an imperative style, high-performance deep learning library. In: NeurIPS, pp. 8024–8035 (2019)
Prakash, B.A., Vreeken, J., Faloutsos, C.: Spotting culprits in epidemics: how many and which ones? In: IEEE International Conference on Data Mining (2012)
Shah, D., Zaman, T.: Rumors in a network: who’s the culprit? IEEE Trans. Inf. Theory 57(8), 5163–5181 (2011)
Shah, D., Zaman, T.: Rumor centrality: a universal source detector. In: ACM SIGMETRICS Performance Evaluation Review, vol. 40, pp. 199–210 (2012)
Shelke, S., Attar, V.: Source detection of rumor in social network-a review. Online Soc. Netw. Media 9, 30–42 (2019)
Wang, Z., Wang, C., Pei, J., Ye, X.: Multiple source detection without knowing the underlying propagation model. In: AAAI Conference on Artificial Intelligence (2017)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)
Yu, P.D., Tan, C.W., Fu, H.L.: Epidemic source detection in contact tracing networks: epidemic centrality in graphs and message-passing algorithms. IEEE J. Sel. Topics Signal Process. 16(2), 234–249 (2022)
Zang, W., Zhang, P., Zhou, C., Guo, L.: Locating multiple sources in social networks under the sir model: a divide-and-conquer approach. J. Comput. Sci. 10, 278–287 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Haddad, R.G., Figueiredo, D.R. (2023). Detecting Multiple Epidemic Sources in Network Epidemics Using Graph Neural Networks. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14197. Springer, Cham. https://doi.org/10.1007/978-3-031-45392-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-45392-2_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-45391-5
Online ISBN: 978-3-031-45392-2
eBook Packages: Computer ScienceComputer Science (R0)