计算机科学 ›› 2018, Vol. 45 ›› Issue (8): 300-305.doi: 10.11896/j.issn.1002-137X.2018.08.054

• 交叉与前沿 • 上一篇    下一篇

仿高阶矩的结点不变量及其组成的图不变量

江顺亮, 葛芸, 唐祎玲, 徐少平, 叶发茂   

  1. 南昌大学信息工程学院 南昌330031
  • 收稿日期:2017-07-24 出版日期:2018-08-29 发布日期:2018-08-29
  • 作者简介:江顺亮(1965-),男,博士,教授,博士生导师,主要研究方向为算法设计与分析、计算机模拟与仿真、人工智能,E-mail:jiangshunliang@ncu.edu.cn; 葛 芸(1983-),女,博士生,讲师,主要研究方向为人工智能、机器视觉; 唐祎玲(1977-),女,博士生,讲师,主要研究方向为人工智能、图像处理,E-mail:tangyiling@ncu.edu.cn(通信作者); 徐少平(1976-),男,博士,教授,博士生导师,主要研究方向为机器视觉、计算机图形学; 叶发茂(1978-)男,博士,副教授,主要研究方向为数字图像处理、计算机图形学。
  • 基金资助:
    本文受2017中国国家自然科学基金(61662044)资助。

Node Invariants by Imitating High-order Moments and Their Graph Invariants

JIANG Shun-liang, GE Yun, TANG Yi-ling XU, Shao-ping, YE Fa-mao   

  1. School of Information Engineering,Nanchang University,Nanchang 330031,China
  • Received:2017-07-24 Online:2018-08-29 Published:2018-08-29

摘要: 借鉴高阶矩的方法,采用层序的计算框架,依据结点的连接距离和层序信息定义了20种结点不变量。这些结点不变量体现图整体的上下偏分布特性、整体不均匀性和整体平滑性,结点不变量中的每层结点度数平方之和反映了层内结点度数的分布情况。通过比较这些结点不变量的可区分结点数,发现每层结点度数平方之和明显改善了结点不变量的细分能力。把排序后的结点不变量组成一个矢量后作为图的不变量。计算结果表明,共有9种图不变量可以区分所有结点数N<25的非同构树和N<34的非同构同胚不可约树(没有度数为2的树),对于更多结点的树,还没有发现非同构树有相同图不变量的例子;把这些图不变量应用到非同构图(N<10),区分结果好于文献[8]中列出的22种图不变量的19种,而且文中9种图不变量的简并度不大,提高了随机图的同构测试性能。

关键词: 结点不变量, 树不变量, 图不变量, 图同构

Abstract: By the way of high-order moments and the level-order computing framework,twenty kinds of node invariants were defined with the connection distance and level-order information of nodes.These node invariants reflect overall bias distribution characteristics,non-uniformity and smoothness,while the sum of squares of nodal degree reflects the distribution of the nodal degrees in the level.By comparing the number of distinguishable nodes,it is found that the sum of squares of nodal degrees obviously improves the refining ability of node invariants.The node invariants are ordered to form a vector as the graph invariant.The calculation results show that there are nine graph invariants that can distinguish between all N<25 non-isomorphic tree and N<34 non-isomorphic irreducible tree (no 2-degree tree) without instance being found so far for non-isomorphic tree with the same graph invariants for trees with more nodes.The distinguished ability of nine graph invariants to non-isomorphic graphs (N<10) exceeds the 19 results of 22 graph invariants in reference [8],and the degeneracy of nine graph invariants is small,thus improving the performance of random graph isomorphism testing.

Key words: Graph invariants, Graph isomorphism, Node invariants, Tree invariants

中图分类号: 

  • TP301.6
[1]SAVAGE N.Graph matching in theory and practice[J].Communications of the ACM,2016,59(7):12-14.
[2]BABAI L.Graph Isomorphism in Quasipolynomial Time[OL].http://arxiv.org/abs/1512.03547.
[3]MCKAY B D,PIPERNO A.Practical graph isomorphism,II[J].Journal of Symbolic Computation,2014,60(1):94-112[4]HOU A M.Theory Research and Algorithm Design On Halmiltonian Cycle and Graph Isomorphism Problems[D].Guangzhou:South China University of Technology,2013.(in Chinese)侯爱民.哈密顿环与图同构问题的理论研究及算法设计[D].广州:华南理工大学,2013.
[5]PIEC S M,MALARZ K,KULAKOWSKI K,et al.How tocount trees[J].International Journal of Modern Physics C,2005,16(10):1527-1534.
[6]ZOU X X,DAI Q.A Vertex Refinement Method for Graph Isomorphism[J].Journal of Software,2007,18(2):213-219.(in Chinese)邹潇湘,戴琼.图同构中的一类顶点细分方法[J].软件学报,2007,18(2):213-219.
[7]GAMKRELIDZE A,VARAMASHVILI L,HOTZ G.New Invariants for the Graph Isomorphism Problem[J].Journal of Mathematical Sciences,2016,218(6):754-762.
[8]DEHMER M,GRABNER M,MOWSHOWITZ A,et al.An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants[J].Advances in Computational Mathematics,2013,39(2):311-325.
[9]BUSS S R.Alogtime algorithms for tree isomorphism,comparison,and canonization[M]∥Computational Logic and Preef Theory.Springer Berlin Heidelberg,1997:18-33.
[10]ZHANG B,TANG Y,WU J,et al.LD:A Polynomial Time Algorithm for Tree Isomorphism[J].Procedia Engineering,2011,15(8):2015-2020.
[11]ZHANG N.Research the Longest Path Length Based On the Degree Sequence of Non-isomorphic Undirected Tree[D].Huhehot:Inner Mongolia Normal University,2013.(in Chinese)张楠.基于度序列的非同构无向树的最长路径长度的研究[D].呼和浩特:内蒙古师范大学,2013.
[12]SCHMUCK N S,WAGNER S G,HUA W.Greedy trees,caterpillars,and Wiener-type graph invariants[J].Match Communications in Mathematical and in Computer Chemistry,2012,68(68):273-292.
[13]LOHREY M,MANETH S,PETERNEK F.Compressed Tree Canonization[C]∥International Colloquium on Automata,Languages,and Programming.Springer Berlin Heidelberg,2015:337-349.
[14]BRINKMANN G,COOLSAET K,GOEDGEBEUR J.House of Graphs:A database of interesting graphs[J].Discrete Applied Mathematics,2013,161(1/2):311-314.
[15]BABAI L,ERDOS P,SELKOW S M.Random Graph Isomor-phism[J].Siam Journal on Computing,1980,9(3):628-635.
[1] 项英倬, 魏强, 游凌, 石浩.
一种求解子图同构问题的改进遗传算法
Improved Genetic Algorithm for Subgraph Isomorphism Problem
计算机科学, 2019, 46(6A): 98-101.
[2] 项英倬, 谭菊仙, 韩杰思, 石浩.
图匹配技术研究
Survey of Graph Matching Algorithms
计算机科学, 2018, 45(6): 27-31. https://doi.org/10.11896/j.issn.1002-137X.2018.06.004
[3] 李丽萍,赵传荣,孔德仁,王芳.
基于图论的无监督区域遥感图像检索算法研究
Research on Unsupervised Regional Remote Sensing Image Retrieval Algorithm Based on Graph Theory
计算机科学, 2017, 44(7): 315-317. https://doi.org/10.11896/j.issn.1002-137X.2017.07.057
[4] 马元魁,白晓亮.
三角网格模型体素特征分割
Voxel Features Segmentation of Triangular Mesh Models
计算机科学, 2015, 42(10): 13-15.
[5] 郭鑫,董坚峰,周清平.
自适应云端的大规模导出子图提取算法
Large Scale Induced Subgraphs Mining Algorithm on Self Adaptive Cloud
计算机科学, 2014, 41(6): 155-160. https://doi.org/10.11896/j.issn.1002-137X.2014.06.030
[6] 张春英,张雪.
不确定属性图的子图同构及其判定算法
Uncertain Attribute Graph Sub-graph Isomorphism and its Determination Algorithm
计算机科学, 2013, 40(6): 242-246.
[7] 梁正平,谭佳加,程一群,马骁驰.
大型模型克隆检测技术研究
Research on Clone Detection for Large-scale Model
计算机科学, 2012, 39(4): 28-31.
[8] .
关于图同构复杂性的分析

计算机科学, 2006, 33(11): 219-221.
[9] .
改进的基于分解的子图同构算法

计算机科学, 2006, 33(1): 260-263.
[10] .
频繁子图挖掘算法综述

计算机科学, 2005, 32(10): 193-196.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!