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

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

作　　者：江顺亮[1] 葛芸[1] 唐祎玲[1] 徐少平[1] 叶发茂[1] JIANG Shun-liang;GE Yun;TANG Yi-ling;XU Shao-ping;YE Fa-mao(School of Information Engineering,Nanchang University,Nanchang 330031,China)

机构地区：[1]南昌大学信息工程学院,南昌330031

出　　处：《计算机科学》2018年第8期300-305,共6页Computer Science

基　　金：2017中国国家自然科学基金(61662044)资助

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]