Structural centrality measures are often used to approximate or predict dynamical influence in a network. The recently proposed Expected Force of Infection (ExF) measures the entropy of all potential transmission paths starting at a node, effectively characterizing a node's role in epidemic diffusion processes. However, this promising metric has seen limited adoption mainly due to an inefficient formulation and the lack of an open-source implementation. In this paper, we present a novel cluster-centric, parallel algorithm enhancing ExF's efficiency and scalability. Compared to the simple parallel version of the original formulation of the ExF our efficient, open-source GPU implementation enables key nodes detection at previously intractable scales, with speed-ups of up to 300x on networks with up to 44 million edges. Leveraging on our algorithm, we compare the ExF with other well-known centrality metrics, upon six real and synthetic contact networks. The ExF emerges as the best of the considered metrics in a few, important tasks: it predicts the likelihood of a global epidemic and its diffusion speed, based on the centrality of the seed node; and it predicts how many other infections will occur as a consequence, in some sense, of a specific node having caught the disease.

Scaling Expected Force: Efficient Identification of Key Nodes in Network-Based Epidemic Models

Ceccarello M.
Formal Analysis
;
2024

Abstract

Structural centrality measures are often used to approximate or predict dynamical influence in a network. The recently proposed Expected Force of Infection (ExF) measures the entropy of all potential transmission paths starting at a node, effectively characterizing a node's role in epidemic diffusion processes. However, this promising metric has seen limited adoption mainly due to an inefficient formulation and the lack of an open-source implementation. In this paper, we present a novel cluster-centric, parallel algorithm enhancing ExF's efficiency and scalability. Compared to the simple parallel version of the original formulation of the ExF our efficient, open-source GPU implementation enables key nodes detection at previously intractable scales, with speed-ups of up to 300x on networks with up to 44 million edges. Leveraging on our algorithm, we compare the ExF with other well-known centrality metrics, upon six real and synthetic contact networks. The ExF emerges as the best of the considered metrics in a few, important tasks: it predicts the likelihood of a global epidemic and its diffusion speed, based on the centrality of the seed node; and it predicts how many other infections will occur as a consequence, in some sense, of a specific node having caught the disease.
2024
EUROMICRO WORKSHOP ON PARALLEL AND DISTRIBUTED PROCESSING
EUROMICRO WORKSHOP ON PARALLEL AND DISTRIBUTED PROCESSING
File in questo prodotto:
File Dimensione Formato  
Scaling_Expected_Force_Efficient_Identification_of_Key_Nodes_in_Network-Based_Epidemic_Models.pdf

Accesso riservato

Tipologia: Published (publisher's version)
Licenza: Accesso privato - non pubblico
Dimensione 402.07 kB
Formato Adobe PDF
402.07 kB Adobe PDF Visualizza/Apri   Richiedi una copia
2306.00606v1.pdf

accesso aperto

Tipologia: Preprint (submitted version)
Licenza: Altro
Dimensione 574.08 kB
Formato Adobe PDF
574.08 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3541891
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact