度序列在图结构相似研究中的应用

Applying Degree Sequence in the Study of Graph Structure Similarity

给出一个度序列的所有的度序列分解,研究了度序列的并、分度重合、分度撕裂、分解运算;给出特殊度序列匹配;用图同态运算和图的度序列来判断图同构,以及度序列的图结构的相似性:如果2个图的度序列相等,则它们有非平凡全同构度序列匹配;建立了度序列格(伴随图格)与普通格的一个等价关联。度序列格和图格为图结构的相似与匹配提供了“集合形式的相似与匹配”,使得点-点(图-图)之间的相似与匹配上升到集合-集合之间的相似与匹配,更加适合研究网络社区间的相似与匹配。提出了求解完备度序列、最近度序列、最小度序列、近似最近度序列、最近度序列邻居等几个尚待研究的问题。

This paper presents all the degree sequence decompositions of a degree sequence,studies the union,component coinciding,component splitting,and decomposition operations of the degree sequence;gives the special degree sequence matching;uses the graph homomorphism operation and the degree sequence of the graph to judge graph isomorphism,and the similarity of the graph structure of the degree sequence:If the degree sequences of two graphs are equal,then they have non-trivial isomorphism degree sequence matching;the degree sequence lattice is established(accompanying graphic lattice)is an equivalent association with ordinary lattices.Part of the solution to the problem of graph structure similarity is given,and further research questions are proposed.Degree sequence lattices and graph lattices provide“similarities in set form for the similarity and matching of graph structures”“and matching”,which makes the similarity and matching between vertex-vertex(graph-graph)rise to set-set similarity and matching,which is more suitable for studying the similarity and matching between network communities.Finally,we propose the perfect degree sequence and the closest sequence problem of degree sequence lattice,the shortest degree sequence problem of degree sequence lattice,approximate closest degree sequence problem,nearest degree sequence neighbor problem.We will focus on the aforementioned problems in the future.