# [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] 点击复制 基于路径信息比较的图同构新算法() 分享到： var jiathis_config = { data_track_clickback: true };

45

2015年第2期

236-240

2015-03-20

## 文章信息/Info

Title:
Novel graph isomorphism algorithm based on path information comparison

1东南大学计算机科学与工程学院, 南京210096; 2东南大学计算机网络和信息集成教育部重点实验室, 南京210096
Author(s):
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:

TP301
DOI:
10.3969/j.issn.1001-0505.2015.02.007

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)