一种时间复杂度为O(m)的无向超图核值求解算法  

An O(m) Algorithm for Cores Decomposition of Undirected Hypergraph

作　　者：冷明[1,2] 孙凌宇[1] 边计年[2] 马昱春[2] 

机构地区：[1]井冈山大学计算机科学系,江西吉安343009 [2]清华大学计算机科学与技术系,北京100084

出　　处：《小型微型计算机系统》2013年第11期2568-2573,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61063007;61163062;61106030)资助;江西省科技支撑计划项目(20132BBE50048)资助;江西省自然科学基金项目(20132BAB201035)资助;江西省教育厅科学技术研究项目(GJJ13540;GJJ12474)资助

摘　　要：阐述了图核的全局信息在结点匹配中的应用,将图核理论扩展到超图上,提出了超图的核等相关概念,并给出了超图核值的形式化描述;分析了超图k水平p-核的构造性属性,给出了求解超图核值算法的基本步骤,进而讨论了降低时间复杂度的改进措施,提出了基于结点属性函数快速求解超图核值的算法框架;重点阐述了无向超图的改进压缩存储格式,将无向超图核值的求解算法从结点的度属性扩展到不同的结点属性函数,并给出了基于该存储格式的结点属性函数p5(v,U)核值求解算法,其时间复杂度为O(m),空间复杂度为O(n+m+z);最后,基于ISPD98测试基准的18组无向超图进行了结点的度和核值的求解对比实验,其数据对比表明:核值相比结点的度更能反映出结点在超图中的重要程度.The core notion of graph and its application in matching schemes is introduced, which can be extended to hypergraph. First-ly, the core notion of hypergraph is proposed and its formal description is presented. Secondly, we analyze the constructive property of p-core at level k and give the solution steps of cores decomposition for hypergraph. We also discuss the improvement of its time complexity and propose the outline of the rapid algorithm for cores decomposition based on the vertex property function of hyperg-raph. Thirdly, we describe the improved compressed storage format （ ICSF） of undirected hypergraph and promote the cores decom- position from the degree of vertex to the property function of vertex. Furthermore, we present the pseudocode of cores decomposition algorithm of vertex property functions p5 （v, U） based on the ICSF of undirected hypergraph, whose time complexity is O （m） and space complexity is O （ n ＋ m ＋ z ）. Finally, we carry out the comparative experiment between degree and core of vertex based on 18 hypergraphs of ISPD98 benchmark. The experiment and analysis show the core of vertex can more nearly reflect the importance of nodes in the hypergraph than the degree of vertex.

关 键 词：无向超图 核值 时间复杂度 算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]