Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2016

Abstract

Influence Maximization is the problem of finding a fixed size set of nodes, which will maximize the expected number of influenced nodes in a social network. The number of influenced nodes is dependent on the influence strength of edges that can be very noisy. The noise in the influence strengths can be modeled using a random noise or adversarial noise model. It has been shown that all random processes that independently affect edges of the graph can be absorbed into the activation probabilities themselves and hence random noise can be captured within the independent cascade model. On the other hand, similar to He et al., we consider the adversarial noise where influence strength for an edge can belong to any point in the interval: [pu,v, pu,v] and the exact values are chosen by an adversary from this interval. The problems of evaluating robustness of a given solution and computing robust optimal solutions have received scant attention in the literature and are of key interest in this paper. Specifically, we aim to minimize (over all available seed sets) the maximum (over all instantiations of influence strengths) regret. Concretely, the key contributions are: (1) We show that maximum regret for a given solution is attained when influence strength on each of the edges is set to one of the extreme values of the influence strength intervals on edges. (2) We provide a novel way of considering samples that accounts for the noise in influence strength on all edges. (3) We develop a framework which provides an approach to get an optimal regret solution and more importantly a metric to evaluate robustness of a given solution based on the regret optimal solution. (4) Finally, we show results on evaluating the robustness of the well known greedy approach. Surprisingly, even without considering noise in influence strengths explicitly, greedy approach achieves highly robust solutions on small-medium scale social network instances.

Keywords

Influence maximization, Regret, Column Generation, Optimization

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

AAMAS '16: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, Singapore, May 9-13

First Page

1395

Last Page

1396

ISBN

9781450342391

Publisher

IFAAMAS

City or Country

Richland, SC

Copyright Owner and License

Publisher

Additional URL

https://dl.acm.org/citation.cfm?id=2937177

Download

Share

COinS