Influence Maximization on Partially Observable Social Networks with Graph Reconstruction

Influence Maximization (IM) is one of the most studied problems in social network analysis and involves selecting a set of k users (seed set) from a social network to start an information diffusion and maximize the expected number of influenced users (influence spread). Despite its wide-ranging applications, from viral marketing to public health campaigns, the IM problem presents significant challenges since it has been proved to be NP-hard under most diffusion models. Moreover, real-world social networks are often only partially observable, with incomplete node and edge information due to privacy or data collection limitations. To address this issue we propose an adaptive multi-round approach that uses techniques of graph reconstruction. Specifically, from an inferred Kronecker generative parameter matrix, we first estimate the missing part of the network, then compute a seed set that also takes into account the nodes not present in the partial graph. By starting the information diffusion from this seed set, the framework will be able to reach new nodes not initially observable, thus expanding its knowledge of the partial graph and being able to compute a more accurate generative parameter matrix at the next step. This iterative process continues until the framework converges to an accurate reconstruction of the full graph or achieves a desired influence spread. We experimentally evaluate this framework on both synthetic and real-world network topologies. Results highlight its effectiveness and show how it is often better with respect to a baseline adaptive approach that does not reconstruct the partial network.