Fast-skyline

Here is the source code of the Fast-Skyline algorithm described in (van Leeuwen & Ukkonen, SDM 2015). This implementation is intended to demonstrate the algorithm with the seed selection problem (influence maximisation), but with small modifications it should work for other purposes as well.

The algorithm is written in Javascript, and I am recommending to use node.js for running it. The source tarball contains a number of helper scripts to simplify testing the algorithm. Thses should work on any Unix-like platform. Windows users are unofortunately on their own for now.

The implementation is experimental, and may or may not work for serious use. It is available under the MIT license.

Installation

  1. Download node.js from http://nodejs.org and install it on your system. Make sure that node is in your PATH.
  2. Download Fast-Skyline from http://anttiukkonen.com/skyline/fast-skyline-0.1.tar.gz and unzip it into some directory. This provides the make_db.sh and find_skyline.sh scripts, as well the required .js files.

Running Fast-Skyline on ca-HepTh

  1. Download the ca-HepTh network from SNAP: http://snap.stanford.edu/data/ca-HepTh.html
  2. Unzip ca-HepTh.txt.gz into some directory to obtain SOMEDIR/ca-HepTh.txt.
  3. Enter the directory that was unzipped from the Fast-Skyline tarball.
  4. Run the make_db.sh script:
    5. ./make_db.sh SOMEDIR/ca-HepTh.txt 200 0.01 SOMEDIR/ca-HepTh.json
    This will pre-process the graph so that we can use the efficient influence estimation heuristic (Static Greedy) proposed by Cheng et al (CIKM 2013). This example will use 200 samples and a constant propagation probability of 0.01 on every edge. The output is stored in SOMEDIR/ca-HepTh.json.
  5. Run the find_skyline.sh script:
    6. ./find_skyline.sh SOMEDIR 50 output.txt
    This will read *all* .json files from SOMEDIR (therefore, make sure there is only ca-HepTh.json in SOMEDIR), and run Fast-Skyline as well as the regular greedy methods. Output (the skylines) is stored in output.txt.
  6. Done!