Higher Order Monotonicity and Submodularity of Influence in Social Networks: From Local to Global

Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity implies global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function is monotone and submodular. The correctness of this conjecture has been proved by Mossel and Roch. In this paper, we first provide the concept AD-k (Alternating Difference-k) as a generalization of monotonicity and submodularity. Specifically, a set function f is called AD-k if all the l-th order differences of f on all inputs have sign (−1)^{l+1} for every l≤k. We propose a refined version of KKT’s conjecture: in the general threshold model, local AD-k implies global AD-k. We prove the correctness of our conjecture when the social graph is a DAG. Furthermore, we affirm our conjecture on general social graphs when k =∞.