[1]何洁月,沈斌.基于路径信息比较的图同构新算法[J].东南大学学报(自然科学版),2015,45(2):236-240.[doi:10.3969/j.issn.1001-0505.2015.02.007]
 He Jieyue,Shen Bin.Novel graph isomorphism algorithm based on path information comparison[J].Journal of Southeast University (Natural Science Edition),2015,45(2):236-240.[doi:10.3969/j.issn.1001-0505.2015.02.007]
点击复制

基于路径信息比较的图同构新算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
45
期数:
2015年第2期
页码:
236-240
栏目:
计算机科学与工程
出版日期:
2015-03-20

文章信息/Info

Title:
Novel graph isomorphism algorithm based on path information comparison
作者:
何洁月12沈斌1
1东南大学计算机科学与工程学院, 南京210096; 2东南大学计算机网络和信息集成教育部重点实验室, 南京210096
Author(s):
He Jieyue 12 Shen Bin 1
1School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China
关键词:
图同构 幂阶比较 大规模图 路径信息比较
Keywords:
graph isomorphism matrix power comparison large graph path information comparison
分类号:
TP301
DOI:
10.3969/j.issn.1001-0505.2015.02.007
摘要:
为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC算法.该算法依次比较各长度的路径信息,对邻接矩阵进行调整,从而实现了2个图的快速同构判定.为了减少路径信息的计算时间,引入Hash函数对PIC算法进行改进,从而得到了HPIC算法.实验结果表明,所提的2种算法均能够正确判定1×104对不同类型、不同大小的随机图是否同构,并且图同构判定的时间复杂度明显降低.HPIC算法的运行速度快于PIC算法;这2种算法在时间性能方面均优于CS算法,略劣于Nauty算法;但对于规则2维网孔图,Nauty算法失效,所提的2种算法则仍能快速进行图同构判定.
Abstract:
To solve the graph isomorphism problem in polynomial time, it is proved that the fact that the path information with same length of two isomorphism graphs must be the same is a more rigorous prerequisite for judging whether two graphs are isomorphism. Then, according to this prerequisite, the PIC(path information comparison)algorithm based on graph isomorphism comparison is proposed. In this algorithm, the path information with different lengths of two graphs is compared successively. The adjacent matrixes are adjusted based on the vertex path information in the comparing process and quick isomorphism of the two graphs is realized. By introducing the Hash function to improve the PIC algorithm, the HPIC(hash path information comparison)algorithm is proposed to reduce the computation time of the path information. The experiment results demonstrate that the two proposed algorithms can correctly judge whether the 1×104 pairs of figures with different types and sizes are isomorphism graphs, and the time complexity is obviouly reduced. The HPIC algorithm is faster than the PIC algorithm. Furthermore, these two algorithms are faster than the CS(circuit simulation)algorithm, but slightly slower than the Nauty algorithm. However, as for the regular two-dimensional meshes, the Nauty algorithm is invalid while the two proposed algorithms can still solve the graph isomorphism problem quickly.

参考文献/References:

[1] Bunke H, Riesen K. Recent advances in graph-based pattern recognition with applications in document analysis [J]. Pattern Recognition, 2011, 44(5):1057-1067.
[2] Dehmer M, Sivakumar L, Varmuza K. Uniquely discriminating molecular structures using novel eigenvalue-based descriptors [J]. Communications in Mathematical and Computer Chemistry, 2012, 67(3): 147-172.
[3] He J Y, Wang C Y, Qiu K P, et al. An novel frequent probability pattern mining algorithm based on circuit simulation method in uncertain biological networks[J]. BMC Systems Biology, 2014, 8(S3): S6.
[4] Torán J. On the hardness of graph isomorphism [J]. SIAM Journal on Computing, 2004, 33(5): 1093-1108.
[5] 许进,张军英,保铮.基于Hopfield网络的图的同构算法 [J].电子科学学刊, 1996, 18(S1): 116-121.
  Xu Jin, Zhang Junying, Bao Zheng. Graph isomorphism algorithm based on the Hopfield network[J]. China Journal of Electronics, 1996, 18(S1): 116-121.(in Chinese)
[6] Ullmann J R. An algorithm for subgraph isomorphism [J]. Journal of the Association for Computing Machinery, 1976, 23(1): 31-42.
[7] McKay B D, Piperno A. Practical graph isomorphism, Ⅱ [J]. Journal of Symbolic Computation, 2014, 60: 94-112.
[8] Shang H L, Li F, Tang X D, et al.A new algorithm for isomorphism determination of undirected graphs-circuit simulation method [J].Circuits Systems and Signal Processing, 2011, 30(5): 1115-1130.
[9] Foggia P, Sansone C, Vento M. A performance comparison of five algorithms for graph isomorphism [C]//Proceedings of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition. Napoli, Italy, 2001: 188-199.
[10] 赵愉, 李锋, 商慧亮. 同构图判定: 改进的电路模拟法[J]. 信息与电子工程, 2011, 9(4): 478-482.
  Zhao Yu, Li Feng, Shang Huiliang. Improved circuit simulation method for testing isomorphism [J]. China Information and Electronic Engineering, 2011, 9(4): 478-482.(in Chinese)
[11] Gori M, Maggini M, Sarti L. Exact and approximate graph matching using random walks [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(7): 1100-1111.
[12] Bondy J A, Murty U S R. Graph theory with applications [M]. London: Macmillan, 1976: 4-7.
[13] 谢科, 饶怀章. 图同构的充要条件[J]. 西南民族大学学报:自然科学版, 2011,37(5): 703-705.
  Xie Ke, Rao Huaizhang. Necessary and sufficient condition of graph isomorphism [J]. China Journal of Southwest University for Nationalities: Natural Science Edition, 2011, 37(5): 703-705.(in Chinese)

备注/Memo

备注/Memo:
收稿日期: 2014-11-08.
作者简介: 何洁月(1964—),女,博士,教授,Jieyuehe@seu.edu.cn.
基金项目: 江苏省自然科学基金资助项目(BK2012742).
引用本文: 何洁月,沈斌.基于路径信息比较的图同构新算法[J].东南大学学报:自然科学版,2015,45(2):236-240. [doi:10.3969/j.issn.1001-0505.2015.02.007]
更新日期/Last Update: 2015-03-20