gSpan是一个频繁子图挖掘算法。
这个程序使用Python实现了gSpan算法。在实现时,参照了gboost。
在graphdata/graph.data数据上,在数次运行中,本程序和gboost的输出结果一致。
当前(时间:2016-10-29),gboost还不支持有向图的频繁子图挖掘。本程序实现了面向有向图的频繁子图挖掘,但是还没有全面测试过,正确性不敢保证。本程序的作者在graphdata/graph.data.directed.1和graph.data.simple.5两个数据集上,运行了数次,暂时还未发现错误。
$ python main.py [-s min_support] [-n num_graph] [-l min_num_vertices] [-u max_num_vertices] [-d] [-v] [-h] [-p] [-w] database_file_name
- 从./graphdata/graph.data中读取数据,挖掘支持度最少5000的频繁无向子图
$ python main.py -s 5000 ./graphdata/graph.data
- 从./graphdata/graph.data中读取数据,挖掘支持度最少5000的频繁无向子图,并将频繁子图可视化(需要安装matplotlib和networkx)
$ python main.py -s 5000 -p ./graphdata/graph.data
- 从./graphdata/graph.data中读取数据,挖掘支持度最少5000的频繁有向子图
$ python main.py -s 5000 -d ./graphdata/graph.data
- 查看帮助,输出各个参数的含义
$ python main.py -h
本程序的作者还写了基于Jupyter Notebook的代码,展示了程序的输出,并对图进行了可视化。详见main.ipynb。
gSpan: Graph-Based Substructure Pattern Mining, by X. Yan and J. Han. Proc. 2002 of Int. Conf. on Data Mining (ICDM'02).
gSpan的一个C++实现。