DrBC

This is a TensorFlow implementation of DrBC, as described in our paper:

Fan, Changjun and Zeng, Li and Ding, Yuhui and Chen, Muhao and Sun, Yizhou and Liu, Zhong[Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach] (CIKM 2019)

The code folder is organized as follows:

• models/: contains the model to obtain the results in the paper
• src/: set of c source codes used in the paper
• c source files:
  • /src/lib/PrepareBatchGraph.cpp: Prepare the batch graphs used in the tensorflow codes.
  • /src/lib/graph.cpp: basic structure for graphs.
  • /src/lib/graphUtil.cpp: Compute the collective influence functions.
  • /src/lib/graph_struct.cpp: Linked list data structure for sparse graphs.
  • /src/lib/metrics.cpp: Compute the metrics functions such as topk accuracy and kendal tau distance.
  • /src/lib/utils.cpp: Compute nodes' betweenness centrality.
• visualize/: contains the figures used in the paper

In order to make our program be more efficient,we write C extensions for Python based on Cython which is an optimized static compiler for Python programming language, the binding files for C codes are listed as follows:

• cython files:
  • /PrepareBatchGraph.pyx: Cython bindings of PrepareBatchGraph.cpp.
  • /PrepareBatchGraph.pxd: Header file of PrepareBatchGraph.pyx.
  • /graph.pyx: Cython bindings of graph.cpp.
  • /graph.pxd: Header file of graph.pyx.
  • /graphUtil.pyx: Cython bindings of graphUtil.cpp.
  • /graphUtil.pxd: Header file of graphUtil.pyx.
  • /graph_struct.pyx: Cython bindings of graph_struct.cpp.
  • /graph_struct.pxd: header file of graph_struct.pyx.
  • /metrics.pyx: Cython bindings of metrics.cpp.
  • /metrics.pxd: Header file of metrics.pyx.
  • /utils.pyx: Cython bindings of utils.cpp.
  • /utils.pxd: Header file of utils.pyx.

1. Build

Get the source code, and install all the dependencies.

git clone https://github.com/FFrankyy/DrBC.git
pip install -r requirements.txt

Makefile

python setup.py build_ext -i

2.Training

Adjust hyper-parameters in BetLearn.py, and run the following to train the model

python start.py

3.Reproducing the results that reported in the paper

Here is the link to the dataset that was used in the paper:

https://drive.google.com/file/d/1nsVX8t5EP3JaTjfeHPf74N21jSDUA8dJ/view?usp=sharing

The model to obtain the results in the paper is in the fold './models/'

4.Baselines implementations

For RK and k-BC, we use the following implementations:

https://github.com/ecrc/BeBeCA

For KADABRA, we use:

https://github.com/natema/kadabra

For ABRA, we use the codes in the original paper. For node2vec, we use:

https://github.com/snap-stanford/snap/tree/master/examples/node2vec

4.Reference

Please cite our work if you find our code/paper is useful to your work.

@inproceedings{fan2019learning,
  title={Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach},
  author={Fan, Changjun and Zeng, Li and Ding, Yuhui and Chen, Muhao and Sun, Yizhou and Liu, Zhong},
  booktitle={Proc. 2019 ACM Int. Conf. on Information and Knowledge Management (CIKM’19)},
  year={2019},
  organization={ACM}
}