Finding near-optimal groups of epidemic spreaders in a complex network.
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 loca...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2014-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0090303&type=printable |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850191381042036736 |
|---|---|
| author | Geoffrey Moores Paulo Shakarian Brian Macdonald Nicholas Howard |
| author_facet | Geoffrey Moores Paulo Shakarian Brian Macdonald Nicholas Howard |
| author_sort | Geoffrey Moores |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-d7bc59eefe2b4aef8fed18350093e44c |
| institution | OA Journals |
| issn | 1932-6203 |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj-art-d7bc59eefe2b4aef8fed18350093e44c2025-08-20T02:14:56ZengPublic Library of Science (PLoS)PLoS ONE1932-62032014-01-0194e9030310.1371/journal.pone.0090303Finding near-optimal groups of epidemic spreaders in a complex network.Geoffrey MooresPaulo ShakarianBrian MacdonaldNicholas HowardIn 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.https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0090303&type=printable |
| spellingShingle | Geoffrey Moores Paulo Shakarian Brian Macdonald Nicholas Howard Finding near-optimal groups of epidemic spreaders in a complex network. PLoS ONE |
| title | Finding near-optimal groups of epidemic spreaders in a complex network. |
| title_full | Finding near-optimal groups of epidemic spreaders in a complex network. |
| title_fullStr | Finding near-optimal groups of epidemic spreaders in a complex network. |
| title_full_unstemmed | Finding near-optimal groups of epidemic spreaders in a complex network. |
| title_short | Finding near-optimal groups of epidemic spreaders in a complex network. |
| title_sort | finding near optimal groups of epidemic spreaders in a complex network |
| url | https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0090303&type=printable |
| work_keys_str_mv | AT geoffreymoores findingnearoptimalgroupsofepidemicspreadersinacomplexnetwork AT pauloshakarian findingnearoptimalgroupsofepidemicspreadersinacomplexnetwork AT brianmacdonald findingnearoptimalgroupsofepidemicspreadersinacomplexnetwork AT nicholashoward findingnearoptimalgroupsofepidemicspreadersinacomplexnetwork |