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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
Summary
=======
This paper analyzes the influence maximization problem under a coordination
game model: nodes can choose between two behaviors (A and B) and derive
a positive payoff whenever their behavior matches with one of their neighbor
(the payoffs can be node-dependent and behavior-dependent). At each time step,
nodes adopt the behavior which maximizes the total utility derived from their
neighbors. Assuming that at t=0, all nodes have behavior A, the influence
maximization problem consists in selecting a seed set of at most k nodes which
are forced to adopt behavior B so as to maximize the number of nodes with
behavior B at time step n. Given this question, the authors show:
* NP-hardness of solving influence maximization
* submodularity of the objective function which directly implies a (1-1/e) approximation algorithm
* #P-hardness of computing the objective function
* convergence of the game to a nash equilibrium or a 2-periodic process
* good behavior of the greedy algorithm (both in terms of influence spread and running time) when tested on social network datasets
Strengths and weaknessess
=========================
As noted in the paper, the coordination game model was introduced in prior work
to model the spread of behaviors in social networks, but a systematic analysis
of the influence maximization problem under this model was still missing. In
particular, it is interesting to see that the hardness results (both for the
optimization problem and computing the objective function) which were known
under other models (such as independent cascade and linear threshold) also hold
in the cooperative game model.
Unfortunately, apart from the proof of NP-hardess of influence maximization
under the simple CG model, it seems that the remaining results follow almost
immediately from the fact that the CG model can be seen as an instance of the
LT model and by adapting already existing results and proofs for this setting.
Specifically:
* the general CG model (with random payoffs) is a specific instance of the
linear threshold model where the weights on the edges adjacent to node u have
weight 1/deg(u) and where the distribution of the tresholds is non-uniform.
Note that the non-uniform case for the LT model was already discussed in
[22].
* there is no real algorithmic contribution, since the suggested algorithm is
the standard greedy algorithm augmented with the heuristics from [19, 7].
More locally, I found a few places where the exposition could be either
simplified or clarified:
* it is never said explicitely whether the graphs considered are directed or
not. Some of the proofs seem to rely on the fact that the graph is undirected,
but if the results hold in boths cases, it should be clearly stated. If the
entire paper is about undirected graphs, then denoting edges by {u, v} instead
of (u,v) would be clearer.
* in the proof of Theorem 1, what is shown is a reduction to the
following existence problem: for a given graph, does there exist a seed set of
size less than k (and not, as stated, the associated minimization problem).
Note that this doesn't affect the correctness of the proof, since this problem
can in turn be reduced to the maximization influence problem
* in the proof of Theorem 1, it seems that the proof still holds without
the branching nodes, which would simplify the proof quite a bit.
* still in the proof of Theorem 1, the fact that the proof for general delta
(as opposed to delta=0.5) is omitted is a bit frustrating. While I believe the
result holds in general, a link to a full version of the paper with a complete
proof would be appreciated.
* as stated above, Lemma 1 follows almost immeditately from [22]. Its proof
could be shortened a lot by simply observing that the activation function is
the composition of a monotone concave function and an additive function: by
well-known properties of submodular functions, this implies that the
composition is monotone and submodular.
Conclusion
==========
Weak reject (-1): while the influence maximization problem under the cooperative
game model is interesting, its tight proximity with the LT model relatively
weakens the novelty of the results which overall seem too incremental to
justify a paper.
|
