基于结点匹配策略的赋权超图核值实验比较  

Experiment Comparison of Weighted Hypergraph Core Based on Node Matching Strategies

作　　者：冷明[1,2] 孙凌宇[1] 朱平[1] 边计年[2] 马昱春[2] 张亮[3] 

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

出　　处：《计算机工程》2013年第6期85-90,共6页Computer Engineering

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

摘　　要：分析赋权超图多水平粗化阶段的节点匹配策略,给出引入节点核值全局信息到超图的节点匹配过程,发挥节点核值导向性作用,改进仅利用边的权值、节点的度等局部信息进行结点选择的匹配策略,将图的核值理论扩展到超图,提出超图核值等相关概念及其形式化描述。基于ISPD98测试基准的18组超图,结合多水平粗化阶段的不同节点匹配策略,以节点的度和核值的最大值、累加和、分布密度为评估指标进行对比实验。结果表明,与传统节点匹配算法相比,该核值更能反映粗化节点在每组水平层粗化超图中的重要程度。This paper analyzes various matching strategies in the coarsening phase of the multilevel method. It proposes the matching strategy based on the core property of vertex which improves previous matching strategies based on the local information of vertex and plays its guidance role on the global information of core, and extends the core notion of graph to the hypergraph and presents the core notion of hypergraph and its formal description. It carries out the comparative experiment between the degree and core of vertex based on the various matching strategies of hypergraph partitioning for 18 hypergraphs of ISPD98 benchmark. Results show that the core of vertex can more nearly reflect the importance of nodes in the coarse hypergraph of each level than the degree of vertex.

关 键 词：赋权超图 匹配策略 核值 度 粗化阶段 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]