diff options
| -rw-r--r-- | cikm-2016-197.txt | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/cikm-2016-197.txt b/cikm-2016-197.txt new file mode 100644 index 0000000..2bdb7f5 --- /dev/null +++ b/cikm-2016-197.txt @@ -0,0 +1,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. |