PIANO (or DISCO): Influence Maximization Meets Graph Embedding and Deep Learning
Since its introduction in 2003, the influence maximization (im) problem has drawn significant research attention in the literature. The aim of im is to select a set of k users who can influence the most individuals in the social network. The problem is proved to be NP-hard. A large number of approximate algorithms have been proposed to address this problem. The state-of-the-art algorithms estimate the expected influence of nodes based on sampled diffusion paths. As the number of required samples have been recently proved to be lower bounded by a particular threshold, which depends on a presetting tradeoff between the accuracy and efficiency, the result quality of these traditional solutions is hard to be further improved without sacrificing efficiency. We present an orthogonal and novel paradigm to address the im problem by leveraging deep learning models to estimate the expected influence. Specifically, we present a novel framework called disco that incorporates graph embedding and deep reinforcement learning techniques to address this problem.
This repository contains the source code for implementing our PIANO framework, which is published in IEEE Transactions on Computational Social Systems. Anyone using this source code, please cite our work using the bibtex as follows...
@article{piano_tcss_lh,
author = {Hui Li and
Mengting Xu and
Sourav S Bhowmick and
Joty Shafiq Rayhan and
Changsheng Sun and
Jiangtao Cui},
title = {PIANO: Influence Maximization Meets Deep Reinforcement Learning},
journal = {{IEEE} Trans. Comput. Soc. Syst.},
volume = {},
number = {},
pages = {},
year = {2022},
}
===============================================================================
The following instruction describes how to use the code.
Get the source code, and install all the dependencies.
-
Download and install CUDA.
-
Download and install Intel MKL. Add the tool box's to your system path.
{path_to_your_intel_root/name_of_parallel_tool_box}/bin/psxevars.sh
-
Build static library
cd graphnn/ cp make_common.example make_common # modify configurations in make_common file make
-
Build the IM-DQN library:
cd code/IM_DQN/IMlib/ cp Makefile.example Makefile make
Now you are all set with the C++ backend.
Take the DBLP dataset as example, we generated different training data using different sampling algorithms. The training dataset should be stored in DISCO-KDD/code/data
. If you want to test other data set, you should put the data in the same path.
Change the parameters int the IM-train.sh
, and then run the training script.
cd DISCO-KDD/code/IM_DQN
sh IM-train.sh
To run the test, using the IM-test.sh
, you can change the parameters in the script, make sure the parameters are same as those in IM-train.sh
.
cd DISCO-KDD/code/IM_DQN
./IM-test.sh
After that, PIANO will gives the solution, as the node selection sequence. And the influence of the nodes selected can be determined by evaluate.py
. evaluate.py
in the DISCO-KDD/code/data
.
This PIANO framework is partly based on the graph_comb_opt with MIT license.