On strict submodularity of social influence (Q2025076)

This paper studies strict sub-modularity in social networks with general threshold model about the influence spread. The influence spread is the expected number of influenced nodes as a function with respect to the input seed set. For a network \(G\) with a general threshold diffusion model. Assume at each vertex \(v\), the threshold function \(f_v: 2^{N(v)}\rightarrow [0,1)\) is strictly increasing and strictly sub-modular, where \(N(v)\) is the set of in-neighbors of \(v\). It is shown that if \(G\) is \(k\)-connected, then the influence spread is strictly \(k\)-sub-modular. A greedy algorithm for monotone non-decreasing sub-modular maximization is described.