blob: 938ccb25b2f4e5ad2b3757029b4c08381b0a159b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
Summary
=======
In this paper, the authors study the standard influence maximization problem:
assuming the independent cascade model (a random diffusion process in graphs),
the goal is to select a seed set of k nodes. While the traditional influence
maximization problem focuses on the maximizing the expected "cascade size"
(i.e. number of "infected" vertices at the end of the random process), the
authors note that this is not always desirable in risk-averse settings. The
contributions are:
* formulating a maximization problem where the objective function is the CVar
(conditional value at risk) risk measure
* providing a "multiplicative weight update" algorithm to solve the problem.
the algorithm is proved to find a solution within an additive 1/e approximation
of the optimal solution
* comparing their algorithm experimentally with the standard greedy algorithm
which maximizes the expected cascade size.
Comments
========
The problem is very interesting: a lot of effort has been put into maximizing
expected cascade size in the influence maximization problem, but little is
known as far as "worst case" or "risk measures" are concerned, and I think
there is a lot of value in obtaining these more nuanced results.
The experiments show very well that the resulting cascade size distribution is
very different when maximizing the Cvar metric as opposed to maximizing
expected size. It is also clear that the distribution obtained when maximizing
CVAR is more desirable in settings where risk needs to be mitigated.
The algorithm is interesting: the ideas are intuitive and standard (sampling
+ multiplicative updates) but to the best of my knowledge are not traditionally
used in the context of influence maximization.
My only concern is about the specific choice of objective function: I feel that
the CVAR metric is not very well motivated. Are there any ways to relate it to
the one used in [5] or [20] which seem more intuitive and easier to interpret?
The interpretability is made even harder by not choosing a single seed set
(fixed strategy) but choosing a distribution over seed sets (random strategy)
and maximizing the CVAR of this random strategy. Also, it would be interesting
to know more about the properties of the CVAR objective function: is it
convex/concave in the choice of the random strategy?
|
