Scalable Influence Estimation in Continuous-Time Diffusion Networks

We are surrounded by social and information share networks, over which diffusions of information, events, virus, takes place constantly. We can often observe that after some influential users adopt certain new product or idea, they actively influence the behaviors of their friends, which in turn makes more friends of friends adopt the product through word-of-mouth.

The specific questions we seek to address in this NIPS 2013 paper is to accurately estimate the number of follow-ups which can be triggered by a given set of earlier influential users, and then to identify a set of influential users, to whom we will give promotions, in order to trigger the largest expected number of follow-ups as soon as possible ? These questions are interesting for that advertisers who want to have an efficient and effective campaign for their new products. But, they are also very challenging in that these questions are time sensitive . Intuitively, 1000 buyers in a day will be much better than 1000 buyers in a year. Furthermore, the solution must be scalable enough to deal with large real-world networks.

About ConTinEst

ConTinEst is a scalable randomized algorithm for influence estimation in continuous-time diffusion networks. It can estimate the influence of every node in a network with $|\mathcal{V}|$ nodes and $|\mathcal{E}|$ edges to an accuracy of $n=\epsilon$ using $O(1/\epsilon^2)$ randomizations and $\tilde{O}(n|\mathcal{E}| + n|\mathcal{V}|)$ computations. When used as a subroutine in a greedy influence maximization approach, ConTinEst is guaranteed to find a set of $C$ nodes with the influence of at least $(1 - 1/e)OPT - 2C\epsilon$, where $OPT$ is the optimum value. Experiments on both synthetic and real-world data show that ConTinEst can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence.

Papers

Scalable Influence Estimation in Continuous-Time Diffusion Networks (Outstanding Paper Award , full oral presentation). Nan Du, Le Song, Manuel Gomez Rodriguez, and Hongyuan Zha. Neural Information Processing Systems (NIPS). Dec. 5 - Dec. 10, 2013, Lake Tahoe, Nevada, USA. [PAPER] [SLIDE][POSTER][Bibtex]

Download

Terms of agreement. We appreciate your interest in our research. The C++ implementation is provided and maintained for our research projects conducted in the School of Computational Science and Engineering at Georgia Institute of Technology. All rights of the source code implementations are reserved. Comments, bugs, and suggestions, if any, can be directed to Nan Du (dunan AT gatech.edu). Redistributions and use of them in source or binary forms, with or without modification, are permitted only to academic purposes. If you use this code, or any part of it, please cite our paper as

This code is provided free for non-commercial use under the terms of the GNU General Public License. The current version is the 1.0 and has been released on August 27, 2013. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. It is understood that by downloading any item from this Web page and the pages linked to by this page, one has entirely understood and fully acknowledged to agree all of the terms.

Download ConTinEst !

Documentation

Input network format. We include a sample network (1,024 nodes) in the implementation. The input file "std_weibull_DAG_core-1024-1-network.txt" consists of two blocks separated by a blank line. The node ID starts from 0 to 1,023. In the 1st block, each line has the format

In the 2nd block, each line represents a directed edge from node ID1 to node ID2 with the following format.

Because we assume the most general form for the pairwise transmission function, for the simplicity of the demo code, we take the Weibull Distribution as the transmission function with the two parameters shape and scale, respectively. When $shape = 1.0$, it is reduced to the exponential distribution; When $shape = 2.0$, it is equivalent to the Rayleigh Distribution. A valid network format can be the following.

The implementation consists of the following five classes

• Graph encapsulates basic graph operations based on the adjacent-list representation.
• ConTinEst encapsulates the implementation for influence estimation and maximization.
• Simulation encapsulates the implementation for naive sampling method.
• SimpleRNG implements several basic density functions.
• TestModules implements basic unit tests.

Class Graph

Graph has the following properties.

• N : number of nodes.
• nodes : array of nodes, each of which stores a set of parents and children, respectively.
• edge_weight : stores the sampled transmission time for each edge.
• edge_parameter : stores the parameters of the transmission function for each edge.
• RNG : generates samples from the Weibull distribution.
• filename : the input graph file name.

Graph has the following methods.

Class ConTinEst

ConTinEst has the following properties.

• m_num_samples : number of sampled sets of pairwise transmission times.
• m_num_rankings : number of sampled sets of random labels per node.
• m_TableList : stores the least-label list for each node given a particular set of transmission times and a specific set of random labels.
• m_keys : stores the random labels for each node given a particular set of transmission times for each edge.
• m_RNG : generates samples from the Weibull distribution.
• *m_G_inverse : pointer to a preloaded graph object.

ConTinEst has the following methods.

Compile on Linux/MacOS

To compile the sources, simply type the following to get the executable file with the name execute

Run the demo on Linux/MacOS

To run the demo code within the directory ConTinEst, simply type

The demo code first loads the network file and calculate the least-label lists for each node.

Then, it finds the node with the maximum out-degree.

Next, it compares the estimated influence at different time given by ConTinEst with that given by the naive simulation for the node with the largest out-degree.

Finally, it selects the 10 sources that can achieve the largest expected number of infected nodes by time 10.