Skip to content
A C++ Library for Influence Maximization
C++ Python CMake
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
conan
docker
docs
include
test-data
test
tools
waftools
.clang-format
.clang-tidy
.gitignore
LICENSE.rst
Pipfile
Pipfile.lock
README.rst
conanfile.py
waf
wscript

README.rst

Ripples

Ripples is a software framework to study the Influence Maximization problem. The problem of Influence Maximization was introduced in 2001 by Domingos and Richardson [DR01] and later formulated as an optimization problem under the framework of submodular functions by Kempe et al. [KTR03].

Given a graph G, a network diffusion model M, and positive integer k, the influence maximization problem is the problem of selecting a set of seeds S of cardinality k such that \mathop{\mathbb{E}}[I(S)] is maximized, where I(S) is the influence function.

Our goal with Ripples is to provide tools implementing fast and scalable state-of-the-art approximation algorithms to solve the influence maximization problem.

[DR01]Pedro M. Domingos and Matthew Richardson. 2001. Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, San Francisco, CA, USA, August 26-29, 2001. ACM, 57–66.
[KTR03]Kempe, D., Kleinberg, J., & Tardos, É. (2003, August). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137-146). ACM.

How to cite

[Cluster19]Marco Minutoli, Mahantesh Halappanavar, Ananth Kalyanaraman, Arun Sathanur, Ryan Mcclure, Jason McDermott. 2019. Fast and Scalable Implementations of Influence Maximization Algorithms. In Proceedings of the IEEE Cluster 2019.

Quickstart with Conan

First of all we need to set up the Python environment needed.

$ pip install --user pipenv
$ pipenv --three
$ pipenv install
$ pipenv shell

Then we need to install dependencies:

$ conan create conan/waf-generator user/stable
$ conan create conan/trng user/stable
$ conan install .

Now we are ready to configure and build ripples:

$ ./waf configure --enable-mpi build
# or without MPI support
$ ./waf configure build

In the case you are a Mac OS user, you will need to install the LLVM toolchain through brew that comes with OpenMP support. Compiling Ripples than is as simple as:

$ ./waf configure --openmp-root=/usr/local/opt/llvm --enable-mpi build
# or without MPI support
$ ./waf configure --openmp-root=/usr/local/opt/llvm build

Quickstart with Docker

$ git clone <url-to-github>
$ cd ripples
$ docker-compose -f docker/docker-compose.yml pull head worker
$ docker-compose -f docker/docker-compose.yml up -d --scale worker=2
$ docker exec -u mpi -it docker_head_1 /bin/bash
$ cd $HOME/ripples
$ ./waf configure --enable-mpi build

To run the parallel IMM tool:

$ build/tools/imm  \
     -i test-data/karate.tsv \
     -p \
     -e 0.05 \
     -k 3 \
     -d IC \
     -o output.json

To run the MPI+OpenMP IMM tool on the docker cluster:

$  mpiexec --hosts=docker_worker_1,docker_worker_2 -np 2 build/tools/mpi-imm \
     -i test-data/karate.tsv \
     -e 0.05 \
     -k 3 \
     -d IC \
     -o output.json

Build Instructions

This project uses WAF as its build system. Building Ripples is a two-step process: configure the project and build the tools. Before attempting to build, be sure to have the following dependencies installed:

  • A compiler with C++14 support and OpenMP support.
  • Spdlog
  • JSON
  • TRNG4
  • An MPI library (optional)

The configure step can be invoked with:

$ ./waf configure

or optionally to enable the MPI implementations:

$ ./waf configure --enable-mpi

The build system offers options that can be used to help the configuration step locate dependencies (e.g., they are installed in unconventional paths). A complete list of the options can be obtained with:

$ ./waf configure --help

After the configuration step succeeds, the build step can be executed by running:

$ ./waf build

For more detailed instruction, please read :ref:`build:Step By Step Build Instructions`.

The tools compiled can be found under build/tools/. A complete set of command line options can be obtained through:

$ ./build/tools/<tool_name> --help

Ripples Team

Disclamer Notice

This material was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government nor the United States Department of Energy, nor Battelle, nor any of their employees, nor any jurisdiction or organization that has cooperated in the development of these materials, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness or any information, apparatus, product, software, or process disclosed, or represents that its use would not infringe privately owned rights.

Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government or any agency thereof, or Battelle Memorial Institute. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or any agency thereof.

PACIFIC NORTHWEST NATIONAL LABORATORY
operated by
BATTELLE
for the
UNITED STATES DEPARTMENT OF ENERGY
under Contract DE-AC05-76RL01830
You can’t perform that action at this time.