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.

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

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

python start.py

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

https://drive.google.com/file/d/1nh9XRyrqtKsaBDpLJri-SotpU3f713SX/view?usp=sharing

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

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

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}
}