Influence Maximization Under Generic Threshold-based Non-submodular Model
This work is significant for researchers and practitioners in social network analysis and marketing, as it provides a direct and efficient method for influence maximization under more realistic non-submodular diffusion models, which previously relied on approximations or bounds.
The paper addresses the challenge of influence maximization in social networks under non-submodular diffusion models, which are common in real-world scenarios but lack efficient direct solutions. The authors propose seed selection strategies based on network graphical properties within a generalized threshold-based model, the influence barricade model. They develop algorithms that strategically remove less-important nodes and select seeds from the remaining network, demonstrating the first graph-based approach to directly tackle non-submodular influence maximization.
As a widely observable social effect, influence diffusion refers to a process where innovations, trends, awareness, etc. spread across the network via the social impact among individuals. Motivated by such social effect, the concept of influence maximization is coined, where the goal is to select a bounded number of the most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. A rich body of research in this area is performed under statistical diffusion models with provable submodularity, which essentially simplifies the problem as the optimal result can be approximated by the simple greedy search. When the diffusion models are non-submodular, however, the research community mostly focuses on how to bound/approximate them by tractable submodular functions so as to estimate the optimal result. In other words, there is still a lack of efficient methods that can directly resolve non-submodular influence maximization problems. In this regard, we fill the gap by proposing seed selection strategies using network graphical properties in a generalized threshold-based model, called influence barricade model, which is non-submodular. Specifically, under this model, we first establish theories to reveal graphical conditions that ensure the network generated by node removals has the same optimal seed set as that in the original network. We then exploit these theoretical conditions to develop efficient algorithms by strategically removing less-important nodes and selecting seeds only in the remaining network. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence maximization.