| Presentation | 2017-04-21 Evaluation of the Robustness of Influence Maximization Algorithms against Random Perturbations to Influence Spread Probability Sho Tsugawa, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Given a social network, an influence maximization algorithm aims to find a set of influential (seed) nodes in the network such that the expected number of nodes influenced by the seed nodes is maximized under the given cascade model. Most influence maximization algorithms assume that ground-truth influence spread probabilities are available. In reality, however, it is natural to assume that there exists a gap between actual influence spread probability and the influence spread probability used in the influence maximization algorithms. In this paper, we examine the robustness of existing influence maximization algorithms against non-adversarial perturbations of influence spread probabilities. Our results show that the performance of state-of-the-art approximation andheuristic algorithms may be significantly degraded, and lightweight heuristic algorithms can sometimes outperform state-of-the-art algorithms when the perturbations are large. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Social network / Influence maximization / Viral marketing / Robustness |
| Paper # | CQ2017-11 |
| Date of Issue | 2017-04-13 (CQ) |
| Conference Information | |
| Committee | CS / CQ |
|---|---|
| Conference Date | 2017/4/20(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Chitose Institute of Science and Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Network Serice, Service Quality, SDN (Software-Defined Networking), NFV (Network Functions. Virtualization), Network Virtualization, Cloud, Contents Delivery, etc |
| Chair | Tetsuya Yokotani(Kanazawa Inst. of Tech.) / Kyoko Yamori(Asahi Univ.) |
| Vice Chair | Hidenori Nakazato(Waseda Univ.) / Takanori Hayashi(NTT) / Hideyuki Shimonishi(NEC) |
| Secretary | Hidenori Nakazato(NTT) / Takanori Hayashi(Kyushu Univ.) / Hideyuki Shimonishi(Osaka Univ.) |
| Assistant | / Hirantha Abeysekera(NTT) / Norihiro Fukumoto(KDDI R&D Labs.) |
| Paper Information | |
| Registration To | Technical Committee on Communication Systems / Technical Committee on Communication Quality |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Evaluation of the Robustness of Influence Maximization Algorithms against Random Perturbations to Influence Spread Probability |
| Sub Title (in English) | |
| Keyword(1) | Social network |
| Keyword(2) | Influence maximization |
| Keyword(3) | Viral marketing |
| Keyword(4) | Robustness |
| 1st Author's Name | Sho Tsugawa |
| 1st Author's Affiliation | University of Tsukuba(Univ. of Tsukuba) |
| 2nd Author's Name | Hiroyuki Ohsaki |
| 2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| Date | 2017-04-21 |
| Paper # | CQ2017-11 |
| Volume (vol) | vol.117 |
| Number (no) | CQ-5 |
| Page | pp.pp.53-58(CQ), |
| #Pages | 6 |
| Date of Issue | 2017-04-13 (CQ) |