General threshold model influence function property proved true
The Local-to-Global AD-k Conjecture is Resolved
Social and Information Networks
Summary
This paper proves a mathematical guess about how influence spreads in networks. If every small part of a network behaves with a certain pattern called AD-k, then the entire network's influence also follows that pattern, no matter how it's connected. The proof uses advanced math tools including Mobius inversion and decision trees, and introduces a new way to think about probabilities with negative values. This work confirms a long-standing idea about influence spreading and could help in understanding complex network behaviors.
What this means in practice
- •For network modelers: Design accurate influence models that guarantee certain mathematical properties in social and information networks.
- •For algorithm developers: Develop algorithms for influence maximization with guarantees based on AD-k properties in possibly cyclic graphs.
A theory result. No direct application yet.
Authors
Wei Chen
Abstract
AD-k stands for Alternating Differences through order k, and it is a property of set functions denoting that the first order difference of the set function is nonnegative (a.k.a. monotnocity), the second order difference is nonpositive (submodularity), and so on with signs alternating through order k. Chen et al. [1] conjectured that in an influence diffusion model called the general threshold model originally defined by Kempe et al. [2], if every local influence function is AD-k, then the global influence spread function is also AD-k, for any (possibly cyclic) directed graph and any k. This paper provides a complete proof showing that the conjecture is true. The proof utilizes Mobius inversion and decision tree partition method and extends the probability distribution of node triggering sets into a generalized algebraic structure allowing negative weights for triggering sets. The extension to negative-weighted triggering sets may be of independent interest.