作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (6): 85-90. doi: 10.3969/j.issn.1000-3428.2013.06.017

• 体系结构与软件技术 • 上一篇    下一篇

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

冷 明1,2,孙凌宇1,朱 平1,边计年2,马昱春2,张 亮3   

  1. (1. 井冈山大学计算机科学系,江西 吉安 343009;2. 清华大学计算机科学与技术系,北京 100084; 3. 江西警察学院,南昌 330103)
  • 收稿日期:2012-05-30 出版日期:2013-06-15 发布日期:2013-06-15
  • 作者简介:冷 明(1975-),男,副教授、博士、CCF会员,主研方向:VLSI算法设计;孙凌宇,副教授、硕士;朱 平,教授;边计年,教授、博士生导师;马昱春、张 亮,副教授
  • 基金资助:
    国家自然科学基金资助项目(61063007, 61163062, 61106030);江西省科技支撑计划基金资助项目(20132BBE50048);江西省自然科学基金资助项目(20132BAB201035);江西省教育厅科学技术研究基金资助项目(GJJ13540, GJJ12474)

Experiment Comparison of Weighted Hypergraph Core Based on Node Matching Strategies

LENG Ming 1,2, SUN Ling-yu 1, ZHU Ping 1, BIAN Ji-nian 2, MA Yu-chun 2, ZHANG Liang 3   

  1. (1. Department of Computer Science, Jinggangshan University, Ji’an 343009, China; 2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China; 3. Jiangxi Police College, Nanchang 330103, China)
  • Received:2012-05-30 Online:2013-06-15 Published:2013-06-15

摘要: 分析赋权超图多水平粗化阶段的节点匹配策略,给出引入节点核值全局信息到超图的节点匹配过程,发挥节点核值导向性作用,改进仅利用边的权值、节点的度等局部信息进行结点选择的匹配策略,将图的核值理论扩展到超图,提出超图核值等相关概念及其形式化描述。基于ISPD98测试基准的18组超图,结合多水平粗化阶段的不同节点匹配策略,以节点的度和核值的最大值、累加和、分布密度为评估指标进行对比实验。结果表明,与传统节点匹配算法相比,该核值更能反映粗化节点在每组水平层粗化超图中的重要程度。

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

Abstract: 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.

Key words: weighted hypergraph, matching strategy, core, degree, coarsening phase

中图分类号: