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

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

TL;DR

This paper introduces "Alternating Difference-k" (AD-k) as a generalization of monotonicity and submodularity to study influence spread in social networks. They propose and prove a conjecture that if a network's local influence properties (threshold functions) satisfy AD-k, then the global influence spread function also exhibits AD-k properties, particularly for Directed Acyclic Graphs (DAGs). This work extends previous findings and offers a more nuanced understanding of influence dynamics.

What Problem Does This Paper Address?

Understanding how information, ideas, or products spread through social networks is a fundamental problem in various fields, from marketing to public health. Researchers often model this using "propagation models," with the General Threshold (GT) model being a broad and powerful framework. A key conjecture by Kempe, Kleinberg, and Tardos (KKT) stated that if the local "threshold functions" of individual nodes (which determine if a node becomes active based on its neighbors) are monotone and submodular, then the overall "spread function" (predicting the total number of active nodes) is also monotone and submodular. This conjecture was proven, but it only covers basic properties.

This paper asks: can we generalize this understanding to "higher orders" of influence? Specifically, what if we consider more complex local properties beyond simple monotonicity and submodularity? The authors aim to extend the KKT conjecture to a more general property called "Alternating Difference-k" (AD-k), which captures higher-order relationships in set functions. They investigate whether local AD-k properties of individual nodes imply global AD-k properties of the entire network's influence spread.

Methods

The core of this paper is the introduction and formalization of the Alternating Difference-k (AD-k) property for set functions. This property generalizes monotonicity (AD-1) and submodularity (AD-2). A set function $f$ is AD-k if its $l$-th order differences have a sign of $(-1)^{l+1}$ for all $l \le k$.

The authors then propose a refined conjecture: in the general threshold model, if each node's threshold function is AD-k, then the global spread function is also AD-k. They prove this conjecture for two important cases:

  1. Directed Acyclic Graphs (DAGs): They first prove the conjecture for layered graphs, a specific type of DAG, by constructing a new layered graph and analyzing the activation probabilities. This result is then generalized to all DAGs.
  2. General Graphs for AD-∞: They prove the conjecture for any graph when $k = \infty$, which essentially means the property holds for all orders of differences. This proof relies on the connection between the general threshold model and the triggering model, and uses properties of set functions and their Mobius inversion.

Key techniques include:

  • Formal definition of AD-k: Extending the concept of differences of set functions.
  • Graph transformations: Constructing new layered graphs from DAGs to leverage existing results.
  • Multilinear extensions: Using continuous extensions of set functions to analyze their properties.
  • Mobius inversion: A mathematical tool to relate different set function representations.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of propagation models rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Generalizing Influence Properties: AD-k provides a powerful framework to capture more complex, higher-order relationships in influence spread beyond simple monotonicity and submodularity. This allows for a more nuanced analysis of network dynamics.
  • Local-to-Global Principle Holds for AD-k: The paper demonstrates that the KKT conjecture's spirit extends to higher-order properties. If individual nodes behave in a certain "alternating difference" way, the entire network's influence spread will also exhibit this behavior.
  • DAGs as a Tractable Case: The proof for DAGs highlights that structural properties of the network can significantly simplify the analysis of influence spread. Layered graphs, in particular, offer a structured way to prove the conjecture.
  • AD-∞ as a Universal Property: The proof for $k=\infty$ suggests that for very high orders of difference, the local-to-global implication holds universally, regardless of graph structure. This is a strong theoretical result.

Key Results

  • Definition of AD-k: A formal definition of Alternating Difference-k (AD-k) for set functions is introduced, generalizing monotonicity and submodularity.
  • Conjecture: The authors propose and prove that in the general threshold model, if threshold functions are locally AD-k, then the spread function is globally AD-k.
  • Proof for DAGs: The conjecture is proven to be correct for any graph that is a Directed Acyclic Graph (DAG).
  • Proof for AD-∞: The conjecture is proven to be correct for any graph when $k = \infty$.
  • Connection to Triggering Model: The work leverages the equivalence between certain general threshold models and triggering models, especially when AD-∞ properties are involved.

Limitations and Future Work

  • General Graphs for Finite k: The paper proves the conjecture for DAGs and for $k=\infty$ on general graphs. A significant open problem is to prove or disprove the conjecture for finite $k$ (where $3 \le k \le n-1$) on general graphs.
  • Algorithmic Implications: While AD-k provides theoretical insights, its direct impact on designing more efficient influence maximization algorithms for finite $k$ remains an open question. The authors suggest exploring this for future work, noting the gap between AD-2 and AD-∞.
  • Approximation Ratios: The paper discusses that AD-k might not necessarily lead to better approximation ratios for problems like Max-k-Cover, which is a special case. This suggests that while AD-k is a powerful theoretical tool, its practical benefits in optimization might be limited in some contexts.

Summary updated

BibTeX
@article{chen2022higher,
  author = {Wei Chen and Qiang Li and Xiaohan Shan and Xiaoming Sun and Jialin Zhang},
  title = {{Higher order monotonicity and submodularity of influence in social networks: From local to global}},
  journal = {Inf. Comput.},
  year = {2022},
  doi = {10.1016/j.ic.2022.104864},
}
Figure