Higher order monotonicity and submodularity of influence in social networks: from local to global

DOI10.1016/J.IC.2022.104864MaRDI QIDQ2672246zbMATH OpenOpenAlexFDO

Authors Wei Chen, Qiang Li, Xiaohan Shan, Xiaoming Sun, Jialin Zhang

Publication date 8 June 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.00666

zbMATH Keywords

general threshold modelhigher-order monotonicitysocial networkssubmodular

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30)

Abstract: Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity imply global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function $sigma(S)$ is monotone and submodular, where $S$ is a seed set and the spread function $sigma(S)$ denotes the expected number of active nodes at termination of a diffusion process starting from $S$. 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 adk if all the $ell$-th order differences of $f$ on all inputs have sign $(-1{)}^{ell+1}$ for every $ellleqk$. Note that AD-1 corresponds to monotonicity and AD-2 corresponds to monotonicity and submodularity. We propose a refined version of KKT's conjecture: in the general threshold model, local AD-k implies global AD-k. The original KKT conjecture corresponds to the case for AD-2, and the case for AD-1 is the trivial one of local monotonicity implying global monotonicity. By utilizing continuous extensions of set functions as well as social graph constructions, we prove the correctness of our conjecture when the social graph is a directed acyclic graph (DAG). Furthermore, we affirm our conjecture on general social graphs when $k=infty$.

Recommendations

• Submodularity of influence in social networks: from local to global
• On strict submodularity of social influence
• On general threshold and general cascade models of social influence

Cites work

• A threshold of ln n for approximating set cover
• Automata, Languages and Programming
• Equivalent representations of set functions
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5485445 (Why is no real title available?)
• Maximizing social influence in nearly optimal time
• On the approximability of influence in social networks
• Submodularity of influence in social networks: from local to global
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions

Cited in

(4)

• On general threshold and general cascade models of social influence
• On strict submodularity of social influence
• On the compounding of higher order monotonic pseudo-Boolean functions
• Submodularity of influence in social networks: from local to global

This page was built for publication: Higher order monotonicity and submodularity of influence in social networks: from local to global

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2672246)