Tested Environment

• Ubuntu 16
• C++ 11
• GCC 5.4
• Boost
• cmake

Compile

$ cmake .
$ make

Parameters

./agenda action_name --algo <algorithm> [options]

• action:
  • query: static SSPPR query
  • build: build index, for FORA only
  • dynamic-ss: dynamic SSPPR query
• algo: which algorithm you prefer to run
  • baton: Baton
  • fora: FORA
  • partup: Agenda with partial update
  • lazyup: Agenda with lazy update
  • resacc: ResAcc
• options
  • --prefix <prefix>
  • --epsilon <epsilon>
  • --dataset <dataset>
  • --query_size <queries count>
  • --update_size <updates count>
  • --with_idx
  • --beta: controls the trade-off between random walk and forward push

Data

The example data format is in ./data/webstanford/ folder. The data for DBLP, Pokec, Orkut, LiveJournal, Twitter are not included here for size limitation reason. You can find them online.

Generate workloads

Generate query files for the graph data. Each line contains a node id.

$ ./agenda generate-ss-query --prefix <data-folder> --dataset <graph-name> --query_size <query count>

$ ./agenda gen-update --prefix <data-folder> --dataset <graph-name> --query_size <query count>

• Example:

$ ./agenda generate-ss-query --prefix ./data/ --dataset webstanford --query_size 1000

Indexing

Construct index files for the graph data using a single core.

• Example

For FORA index:

$ ./agenda build --prefix ./data/ --dataset webstanford --epsilon 0.5

For Baton and Agenda index:

$ ./agenda build --prefix ./data/ --dataset webstanford --epsilon 0.5 --baton

Query

Process queries.

$ ./agenda <query-type> --algo <algo-name> --prefix <data-folder> --dataset <graph-name> --result_dir <output-folder> --epsilon <relative error> --query_size <query count> --update_size<update count> [--with-idx --exact]

• Example:

For SSPPR query on static graphs

// FORA
$ ./agenda query --algo fora --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 200

// FORA+
$ ./agenda query --algo fora --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 200 --with_idx

// Agenda 
$ ./agenda query --algo genda --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 200 --with_idx

For SSPPR query on dynamic graphs:

// FORA
./agenda dynamic-ss --algo fora --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200  --with_idx

// FORA+
./agenda dynamic-ss --algo fora --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 

// Baton
./agenda dynamic-ss --algo baton --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 --with_idx

// ResAcc
$ ./agenda dynamic-ss --algo resacc --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 --with_idx

// Agenda
$ ./agenda dynamic-ss --algo lazyup --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 --with_idx

If you find this work useful, please cite our paper

Mo, Dingheng, and Siqiang Luo. "Agenda: Robust Personalized PageRanks in Evolving Graphs." 
In Proceedings of the 30th ACM International Conference on Information 
& Knowledge Management, pp. 1315-1324. 2021.

@inproceedings{mo2021agenda,
  title={Agenda: Robust Personalized PageRanks in Evolving Graphs},
  author={Mo, Dingheng and Luo, Siqiang},
  booktitle={Proceedings of the 30th ACM International Conference on Information \& Knowledge Management},
  pages={1315--1324},
  year={2021}
}

Acknowledgement

Part of the code is reused from FORA's codebase: https://github.com/wangsibovictor/fora