  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.
