Worst-case scenarios for greedy, centrality-based network protection strategies

The task of allocating preventative resources to a computer network in order to protect against the spread of viruses is addressed. Virus spreading dynamics are described by a linearized SIS model and protection is framed by an optimization problem which maximizes the rate at which a virus in the ne...

Full description

Saved in:
Bibliographic Details
Main Authors: Zarghamy, Michael, Preciadoy, Victor
Format: Conference Proceeding
Language:English
Subjects:
Computers
Eigenvalues and eigenfunctions
Equations
Immune system
Resource management
Tin
Vectors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 6
container_issue
container_start_page 1
container_title
container_volume
creator Zarghamy, Michael
Preciadoy, Victor
description The task of allocating preventative resources to a computer network in order to protect against the spread of viruses is addressed. Virus spreading dynamics are described by a linearized SIS model and protection is framed by an optimization problem which maximizes the rate at which a virus in the network is contained given finite resources. One approach to problems of this type involve greedy heuristics which allocate all resources to the nodes with large centrality measures. We address the worst case performance of such greedy algorithms be constructing networks for which these greedy allocations are arbitrarily inefficient. An example application is presented in which such a worst case network might arise naturally and our results are verified numerically by leveraging recent results which allow the exact optimal solution to be computed via geometric programming.
doi_str_mv 10.1109/CISS.2014.6814076
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_6814076</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>6814076</ieee_id><sourcerecordid>6814076</sourcerecordid><originalsourceid>FETCH-LOGICAL-i208t-54b26c5b214e0794e2804a70bdc1a733fab13fd3b2ae40c7058fc813d3cfb8e93</originalsourceid><addsrcrecordid>eNotj01LAzEYhONBUGt_gHjJD3DXNx-7SY6y-FEo9FDFY0myb0q0bkoSkP57F-xphpmHgSHkjkHLGJjHYbXdthyYbHvNJKj-gtwwqYwRAKy_IstSvmC2Zq5BX5PNZ8qlNt4WpMXjZHNMhYaU6T4jjqcHOoc120Osp8bN1EgnrL8pf9NjThV9jWmiZSYq7iOWW3IZ7KHg8qwL8vHy_D68NevN62p4WjeRg65NJx3vfec4kwjKSOQapFXgRs-sEiJYx0QYheMWJXgFnQ5eMzEKH5xGIxbk_n83IuLumOOPzafd-bP4A6AUTmc</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Worst-case scenarios for greedy, centrality-based network protection strategies</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Zarghamy, Michael ; Preciadoy, Victor</creator><creatorcontrib>Zarghamy, Michael ; Preciadoy, Victor</creatorcontrib><description>The task of allocating preventative resources to a computer network in order to protect against the spread of viruses is addressed. Virus spreading dynamics are described by a linearized SIS model and protection is framed by an optimization problem which maximizes the rate at which a virus in the network is contained given finite resources. One approach to problems of this type involve greedy heuristics which allocate all resources to the nodes with large centrality measures. We address the worst case performance of such greedy algorithms be constructing networks for which these greedy allocations are arbitrarily inefficient. An example application is presented in which such a worst case network might arise naturally and our results are verified numerically by leveraging recent results which allow the exact optimal solution to be computed via geometric programming.</description><identifier>EISBN: 1479930016</identifier><identifier>EISBN: 9781479930012</identifier><identifier>DOI: 10.1109/CISS.2014.6814076</identifier><language>eng</language><publisher>IEEE</publisher><subject>Computers ; Eigenvalues and eigenfunctions ; Equations ; Immune system ; Resource management ; Tin ; Vectors</subject><ispartof>2014 48th Annual Conference on Information Sciences and Systems (CISS), 2014, p.1-6</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/6814076$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54920</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/6814076$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Zarghamy, Michael</creatorcontrib><creatorcontrib>Preciadoy, Victor</creatorcontrib><title>Worst-case scenarios for greedy, centrality-based network protection strategies</title><title>2014 48th Annual Conference on Information Sciences and Systems (CISS)</title><addtitle>CISS</addtitle><description>The task of allocating preventative resources to a computer network in order to protect against the spread of viruses is addressed. Virus spreading dynamics are described by a linearized SIS model and protection is framed by an optimization problem which maximizes the rate at which a virus in the network is contained given finite resources. One approach to problems of this type involve greedy heuristics which allocate all resources to the nodes with large centrality measures. We address the worst case performance of such greedy algorithms be constructing networks for which these greedy allocations are arbitrarily inefficient. An example application is presented in which such a worst case network might arise naturally and our results are verified numerically by leveraging recent results which allow the exact optimal solution to be computed via geometric programming.</description><subject>Computers</subject><subject>Eigenvalues and eigenfunctions</subject><subject>Equations</subject><subject>Immune system</subject><subject>Resource management</subject><subject>Tin</subject><subject>Vectors</subject><isbn>1479930016</isbn><isbn>9781479930012</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2014</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj01LAzEYhONBUGt_gHjJD3DXNx-7SY6y-FEo9FDFY0myb0q0bkoSkP57F-xphpmHgSHkjkHLGJjHYbXdthyYbHvNJKj-gtwwqYwRAKy_IstSvmC2Zq5BX5PNZ8qlNt4WpMXjZHNMhYaU6T4jjqcHOoc120Osp8bN1EgnrL8pf9NjThV9jWmiZSYq7iOWW3IZ7KHg8qwL8vHy_D68NevN62p4WjeRg65NJx3vfec4kwjKSOQapFXgRs-sEiJYx0QYheMWJXgFnQ5eMzEKH5xGIxbk_n83IuLumOOPzafd-bP4A6AUTmc</recordid><startdate>20140301</startdate><enddate>20140301</enddate><creator>Zarghamy, Michael</creator><creator>Preciadoy, Victor</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>20140301</creationdate><title>Worst-case scenarios for greedy, centrality-based network protection strategies</title><author>Zarghamy, Michael ; Preciadoy, Victor</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i208t-54b26c5b214e0794e2804a70bdc1a733fab13fd3b2ae40c7058fc813d3cfb8e93</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2014</creationdate><topic>Computers</topic><topic>Eigenvalues and eigenfunctions</topic><topic>Equations</topic><topic>Immune system</topic><topic>Resource management</topic><topic>Tin</topic><topic>Vectors</topic><toplevel>online_resources</toplevel><creatorcontrib>Zarghamy, Michael</creatorcontrib><creatorcontrib>Preciadoy, Victor</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Xplore (Online service)</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Zarghamy, Michael</au><au>Preciadoy, Victor</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Worst-case scenarios for greedy, centrality-based network protection strategies</atitle><btitle>2014 48th Annual Conference on Information Sciences and Systems (CISS)</btitle><stitle>CISS</stitle><date>2014-03-01</date><risdate>2014</risdate><spage>1</spage><epage>6</epage><pages>1-6</pages><eisbn>1479930016</eisbn><eisbn>9781479930012</eisbn><abstract>The task of allocating preventative resources to a computer network in order to protect against the spread of viruses is addressed. Virus spreading dynamics are described by a linearized SIS model and protection is framed by an optimization problem which maximizes the rate at which a virus in the network is contained given finite resources. One approach to problems of this type involve greedy heuristics which allocate all resources to the nodes with large centrality measures. We address the worst case performance of such greedy algorithms be constructing networks for which these greedy allocations are arbitrarily inefficient. An example application is presented in which such a worst case network might arise naturally and our results are verified numerically by leveraging recent results which allow the exact optimal solution to be computed via geometric programming.</abstract><pub>IEEE</pub><doi>10.1109/CISS.2014.6814076</doi><tpages>6</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier EISBN: 1479930016
ispartof 2014 48th Annual Conference on Information Sciences and Systems (CISS), 2014, p.1-6
issn
language eng
recordid cdi_ieee_primary_6814076
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Computers
Eigenvalues and eigenfunctions
Equations
Immune system
Resource management
Tin
Vectors
title Worst-case scenarios for greedy, centrality-based network protection strategies
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T13%3A24%3A25IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Worst-case%20scenarios%20for%20greedy,%20centrality-based%20network%20protection%20strategies&rft.btitle=2014%2048th%20Annual%20Conference%20on%20Information%20Sciences%20and%20Systems%20(CISS)&rft.au=Zarghamy,%20Michael&rft.date=2014-03-01&rft.spage=1&rft.epage=6&rft.pages=1-6&rft_id=info:doi/10.1109/CISS.2014.6814076&rft.eisbn=1479930016&rft.eisbn_list=9781479930012&rft_dat=%3Cieee_6IE%3E6814076%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i208t-54b26c5b214e0794e2804a70bdc1a733fab13fd3b2ae40c7058fc813d3cfb8e93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=6814076&rfr_iscdi=true