Measuring the value of accurate link prediction for network seeding
Merging two classic questions The influence-maximization literature seeks small sets of individuals whose structural placement in the social network can drive large cascades of behavior. Optimization efforts to find the best seed set often assume perfect knowledge of the network top...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109456 |
| _version_ | 1826215439701639168 |
|---|---|
| author | Wei, Yijin Spencer, Gwen |
| author2 | Massachusetts Institute of Technology. Center for Computational Engineering |
| author_facet | Massachusetts Institute of Technology. Center for Computational Engineering Wei, Yijin Spencer, Gwen |
| author_sort | Wei, Yijin |
| collection | MIT |
| description | Merging two classic questions
The influence-maximization literature seeks small sets of individuals whose structural placement in the social network can drive large cascades of behavior. Optimization efforts to find the best seed set often assume perfect knowledge of the network topology. Unfortunately, social network links are rarely known in an exact way. When do seeding strategies based on less-than-accurate link prediction provide valuable insight?
Our contribution
We introduce optimized-against-a-sample (OAS) performance to measure the value of optimizing seeding based on a noisy observation of a network. Our computational study investigates OAS under several threshold-spread models in synthetic and real-world networks. Our focus is on measuring the value of imprecise link information. The level of investment in link prediction that is strategic appears to depend closely on spread model: in some parameter ranges investments in improving link prediction can pay substantial premiums in cascade size. For other ranges, such investments would be wasted. Several trends were remarkably consistent across topologies. |
| first_indexed | 2024-09-23T16:29:02Z |
| format | Article |
| id | mit-1721.1/109456 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:29:02Z |
| publishDate | 2017 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1094562022-10-02T08:09:26Z Measuring the value of accurate link prediction for network seeding Wei, Yijin Spencer, Gwen Massachusetts Institute of Technology. Center for Computational Engineering Wei, Yijin Merging two classic questions The influence-maximization literature seeks small sets of individuals whose structural placement in the social network can drive large cascades of behavior. Optimization efforts to find the best seed set often assume perfect knowledge of the network topology. Unfortunately, social network links are rarely known in an exact way. When do seeding strategies based on less-than-accurate link prediction provide valuable insight? Our contribution We introduce optimized-against-a-sample (OAS) performance to measure the value of optimizing seeding based on a noisy observation of a network. Our computational study investigates OAS under several threshold-spread models in synthetic and real-world networks. Our focus is on measuring the value of imprecise link information. The level of investment in link prediction that is strategic appears to depend closely on spread model: in some parameter ranges investments in improving link prediction can pay substantial premiums in cascade size. For other ranges, such investments would be wasted. Several trends were remarkably consistent across topologies. 2017-05-31T14:28:22Z 2017-05-31T14:28:22Z 2017-05 2016-07 2017-05-19T04:11:25Z Article http://purl.org/eprint/type/JournalArticle 2197-4314 http://hdl.handle.net/1721.1/109456 Wei, Yijin and Spencer, Gwen. "Measuring the value of accurate link prediction for network seeding." Computational Social Networks 4, no. 1: 1-35 © 2017 The Author(s) en http://dx.doi.org/10.1186/s40649-017-0037-3 Computational Social Networks Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer International Publishing Springer International Publishing |
| spellingShingle | Wei, Yijin Spencer, Gwen Measuring the value of accurate link prediction for network seeding |
| title | Measuring the value of accurate link prediction for network seeding |
| title_full | Measuring the value of accurate link prediction for network seeding |
| title_fullStr | Measuring the value of accurate link prediction for network seeding |
| title_full_unstemmed | Measuring the value of accurate link prediction for network seeding |
| title_short | Measuring the value of accurate link prediction for network seeding |
| title_sort | measuring the value of accurate link prediction for network seeding |
| url | http://hdl.handle.net/1721.1/109456 |
| work_keys_str_mv | AT weiyijin measuringthevalueofaccuratelinkpredictionfornetworkseeding AT spencergwen measuringthevalueofaccuratelinkpredictionfornetworkseeding |