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.

Publications

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 set up the conan profile:

$ conan profile new default --detect
$ conan profile update settings.compiler.libcxx=libstdc++11 default
$ conan profile update env.CC=$(which gcc) default
$ conan profile update env.CXX=$(which g++) default

Next, we need to install dependencies:

$ conan create conan/waf-generator user/stable
$ conan create conan/trng user/stable
$ conan create conan/metall user/stable
$ conan create conan/memkind user/stable
$ conan install --install-folder build .

To enable Memkind or Metall please replace the conan install command with one of:

$ conan install --install-folder build . -o memkind=True
$ conan install --install-folder build . -o metal=True

Now we are ready to configure and build ripples:

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

To enable Memkind or Metal configure and build ripples with:

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

For Memkind just replace --enable-metall with --enable-memkind.

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_release
# or without MPI support
$ ./waf configure --openmp-root=/usr/local/opt/llvm build_release

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++17 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_release

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

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

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

Allocate RRRSets Using Metall

Ripples + Metall has another mode that allocates intermediate data (called RRRSets) using Metall.

To enable the mode, define ENABLE_METALL_RRRSETS macro (e.g., insert #define ENABLE_METALL_RRRSETS at the beginning of tools/imm.cc).

The storage directory can be specified with --rr-store-dir=<PATH> argument when executing imm.

Ripples Team

• Marco Mintutoli
• Mahantesh Halappanavar
• Ananth Kalyanaraman
• Maurizio Drocco
• Reece Neff

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