Skip to content
/ FBRW Public

Implementation of our paper "An Efficient Approximate Algorithm for Single-Source Discounted Hitting Time Query" (DASFAA2020)

Notifications You must be signed in to change notification settings

thu-west/FBRW

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Code Contributor: Kaixin Liu

If you have any questions, feel free to contact me. My email is lkx17@mails.tsinghua.edu.cn.

Please cite our paper if you choose to use our code.

@inproceedings{DBLP:conf/dasfaa/LiuZX20b,
  author    = {Kaixin Liu and
               Yong Zhang and
               Chunxiao Xing},
  editor    = {Yunmook Nah and
               Bin Cui and
               Sang{-}Won Lee and
               Jeffrey Xu Yu and
               Yang{-}Sae Moon and
               Steven Euijong Whang},
  title     = {An Efficient Approximate Algorithm for Single-Source Discounted Hitting
               Time Query},
  booktitle = {Database Systems for Advanced Applications - 25th International Conference,
               {DASFAA} 2020, Jeju, South Korea, September 24-27, 2020, Proceedings,
               Part {III}},
  series    = {Lecture Notes in Computer Science},
  volume    = {12114},
  pages     = {237--254},
  publisher = {Springer},
  year      = {2020},
  url       = {https://doi.org/10.1007/978-3-030-59419-0\_15},
  doi       = {10.1007/978-3-030-59419-0\_15},
  timestamp = {Fri, 25 Sep 2020 12:46:11 +0200},
  biburl    = {https://dblp.org/rec/conf/dasfaa/LiuZX20b.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

Single Source Discounted Hitting Time

Tested Environment

  • Ubuntu
  • C++ 11
  • GCC 4.8
  • Boost
  • cmake

Compile

$ cmake .
$ make

Parameters

./fbrw action_name --algo <algorithm> [options]
  • action:
    • query
    • topk
    • generate-ss-query: generate queries file
    • gen-exact-topk: generate ground truth by power-iterations method
    • gen-exact-self: generate ground truth by backward propagation
  • algo: which algorithm you prefer to run
    • montecarlo: Monte Carlo
    • dne: Dynamic neighborhood expansion
    • fora_bippr: Fora and bippr
    • fbrw: FBRW
  • options
    • --prefix <prefix>
    • --epsilon <epsilon>
    • --dataset <dataset>
    • --query_size <queries count>
    • --k <top k>
    • --exact_ppr_path <directory to place generated ground truth>
    • --result_dir <directory to place results>

Data

The data for DBLP, Pokec, Livejournal, Twitter are not included here for size limitation reason. You can find them online.

Generate queries

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

$ ./fbrw generate-ss-query --prefix <data-folder> --dataset <graph-name> --query_size <query count>
  • Example:
$ ./fbrw generate-ss-query --prefix ./data/ --dataset pokec --query_size 500

Query

Process queries.

$ ./fbrw query --algo <algo-name> --prefix <data-folder> --dataset <graph-name> --result_dir <output-folder> --epsilon <relative error> --query_size <query count>
  • Example:
$ ./fbrw query --algo fbrw --prefix ./data/ --dataset pokec --epsilon 0.5 --query_size 20

Top-K

Process top-k queries.

$ ./fbrw topk --algo <algo-name> --prefix <data-folder> --dataset <graph-name> --result_dir <output-folder> --epsilon <relative error> --query_size <query count> --k <k>
  • Example
$ ./fbrw topk --algo fbrw --prefix ./data/ --dataset pokec --epsilon 0.5 --query_size 20 --k 500

Exact PPR (ground truth)

Construct ground truth for the generated queries.

$ ./fbrw gen-exact-topk --prefix <data-folder> --dataset <graph-name> --k <k> --query_size <query count> --exact_ppr_path <folder to save exact ppr>
$ ./fbrw gen-exact-self --prefix <data-folder> --dataset <graph-name> --k <k> --query_size <query count> --exact_ppr_path <folder to save exact ppr>
  • Example
$ mkdir ./exact
$ ./fbrw gen-exact-topk --prefix ./data/ --dataset pokec --k 500 --query_size 100 --exact_ppr_path ./exact/
$ ./fbrw gen-exact-self --prefix ./data/ --dataset pokec --k 500 --query_size 100 --exact_ppr_path ./exact/

About

Implementation of our paper "An Efficient Approximate Algorithm for Single-Source Discounted Hitting Time Query" (DASFAA2020)

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published