In this paper, we present algorithms to find near-optimal sets of epidemic spreaders in complex networks. We extend the notion of local-centrality, a centrality measure previously shown to correspond with a node's ability to spread an epidemic, to sets of nodes by introducing combinatorial local centrality. Though we prove that finding a set of nodes that maximizes this new measure is NP-hard, good approximations are available. We show that a strictly greedy approach obtains the best approximation ratio unless P = NP and then formulate a modified version of this approach that leverages qualities of the network to achieve a faster runtime while maintaining this theoretical guarantee. We perform an experimental evaluation on samples from several different network structures which demonstrate that our algorithm maximizes combinatorial local centrality and consistently chooses the most effective set of nodes to spread infection under the SIR model, relative to selecting the top nodes using many common centrality measures. We also demonstrate that the optimized algorithm we develop scales effectively.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3973667 | PMC |
| http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0090303 | PLOS |
Publication Analysis
Top Keywords
Similar Publications
HIV Molecular Transmission Networks Among Students in Guangxi: Unraveling the Dynamics of Student-Driven HIV Epidemic.
Emerg Microbes Infect
January 2025
Guangxi Key Laboratory of AIDS Prevention Control and Translation, Guangxi Zhuang Autonomous Region Center for Disease Control and Prevention, Nanning, Guangxi, China.
In Guangxi, the number of newly diagnosed HIV-1 infections among students is continuously increasing, highlighting the need for a detailed understanding of local transmission dynamics, particularly focusing on key drivers of transmission. We recruited individuals newly diagnosed with HIV-1 in Nanning, Guangxi, and amplified and sequenced the HIV-1 pol gene to construct a molecular network. Bayesian phylogenetic analysis was utilized to identify migration events, and multivariable logistic regression was employed to analyze factors influencing clustering and high linkage.
View Article and Find Full Text PDFAsymptomatic carriage of intestinal protists is common in children in Lusaka Province, Zambia.
PLoS Negl Trop Dis
December 2024
Parasitology Reference and Research Laboratory, Spanish National Centre for Microbiology, Health Institute Carlos III, Majadahonda, Madrid, Spain.
Background: PCR-based screenings on the presence of diarrhoea-causing intestinal protist species are limited in Zambia, resulting in inaccurate current prevalence and epidemiological data. Sensitive PCR-based methods are particularly well suited for detecting subclinical infections in apparently healthy carriers.
Methodology: In this prospective cross-sectional study, we investigated the occurrence of the most common intestinal protists in an apparently healthy paediatric population (5-18 years) in Lusaka Province, Zambia.
Integrating graph and reinforcement learning for vaccination strategies in complex networks.
Sci Rep
December 2024
School of Computing, Queen's University, Kingston, Canada.
Article Synopsis
- - Pandemics like COVID-19 significantly impact society and the economy, necessitating effective and efficient vaccine distribution, especially during initial limited supplies.
- - Traditional methods for identifying key influencial nodes in virus transmission networks lack consistency and often overlook the collective influence of groups of nodes.
- - The paper proposes a new framework using Graph Neural Networks (GNN) and Deep Reinforcement Learning (DRL) to improve vaccination strategies by effectively targeting influential nodes and disrupting disease spread in complex networks.
Understanding the progress of COVID-19 transmission in a rural district: a social network approach.
PeerJ
December 2024
Public Health Development Unit, Department of Public Health, Selangor State Health Department, Shah Alam, Selangor, Malaysia.
Background: Social interactions within and between communities influenced the spread of COVID-19. By using social network analysis (SNA), we aimed to understand the effect of social interaction on the spread of disease in a rural district.
Method: A retrospective record review study using positive COVID-19 cases and contact-tracing data from an area in Malaysia was performed and analysed using the SNA method through R software and visualised by Gephi software.
Article Synopsis
- The U.S. swine industry faces disease spread risks due to structural issues, and integrating human movement data with animal movement models provides a more accurate understanding of these risks.
- An analysis of a year’s worth of farm visit data from three swine management companies revealed a highly connected network with 455 properties, demonstrating that human movements significantly enhance network connectivity compared to animal movements alone.
- The study suggests that certain properties act as 'hubs' making them potential points for disease spread, indicating that swine farm networks are more vulnerable to disease outbreaks than previously thought based solely on animal movement.
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!