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

doi:10.3969/j.issn.1000-3428.2013.06.017

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

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

冷明^1,2，孙凌宇¹，朱平¹，边计年²，马昱春²，张亮³

(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 ¹, ZHU Ping ¹, BIAN Ji-nian ², MA Yu-chun ², ZHANG Liang ³

(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

摘要/Abstract

摘要： 分析赋权超图多水平粗化阶段的节点匹配策略，给出引入节点核值全局信息到超图的节点匹配过程，发挥节点核值导向性作用，改进仅利用边的权值、节点的度等局部信息进行结点选择的匹配策略，将图的核值理论扩展到超图，提出超图核值等相关概念及其形式化描述。基于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

中图分类号:

TP311

冷明, 孙凌宇, 朱平, 边计年, 马昱春, 张亮. 基于结点匹配策略的赋权超图核值实验比较[J]. 计算机工程, 2013, 39(6): 85-90.

LENG Meng, SUN Ling-Yu, SHU Beng, BIAN Ji-Nian, MA Yu-Chun, ZHANG Liang. Experiment Comparison of Weighted Hypergraph Core Based on Node Matching Strategies[J]. Computer Engineering, 2013, 39(6): 85-90.

参考文献

[1] Karypis G, Aggarwal R, Kumar V. Multilevel Hypergraph Partitioning: Applications in VLSI Domain[C]//Proc. of the 34th Design Automation Conference. New York, USA: ACM Press, 1998: 526-529.
[2] 刘建军, 祝一薇, 李新光, 等. 基于超图模型的图像目标识别[J]. 计算机工程, 2010, 36(21): 181-185.
[3] Lengauer T. Combinatorial Algorithms for Integrated Circuit Layout[M]. Berlin, Germany: Wiley-Teubner, 1990.
[4] Alpert C J, Kahng A B. Recent Directions in Netlist Parti- tioning, Integration[J]. The VLSI Journal, 1995, 19(2): 1-81.
[5] 孙凌宇, 冷明, 曾小荟, 等. 一种VLSI设计到无向赋权图的转换系统[J]. 微电子学与计算机, 2009, 26(7): 57-59.
[6] 孙凌宇, 冷明, 彭宣戈. 一种ISPD98电路网表到图的转换算法[J]. 井冈山学院学报: 自然科学, 2008, 29(4): 19-21.
[7] Kernighan B W, Lin Song. An Efficient Heuristic Procedure for Partitioning Graphs[J]. Bell System Technical Journal, 1970, 49(2): 291-307.
[8] 郭美云, 杨博, 陈志刚. 基于网格资源超图模型的可信任务调度[J]. 计算机工程, 2008, 34(13): 58-61.
[9] Pilkington J. Partitioning with Space Filling Curves[D]. San Diego, USA: University of California, 1994.
[10] Dongarra J, Fox G, Kennedy K, et al. Sourcebook of Parallel Computer[M]. San Francisco, USA: Morgan Kaufmann Publishers, 2003.
[11] 孙凌宇, 冷明, 郁松年. 基于谱方法的无向赋权图剖分算法[J]. 计算机应用研究, 2009, 26(6): 2086-2089.
[12] 孙凌宇, 冷明, 彭宣戈. 一种基于元胞自动机的无向图剖分优化算法[J]. 计算机工程与应用, 2008, 44(24): 46-49.
[13] Karypis G, Kumar V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs[J]. Siam Journal on Scientific Computing, 1998, 20(1): 359-392.
[14] Soufiane R. Hypergraph Cuts & Unsupervised Representation for Image Segmentation[J]. Fundamenta Informaticae, 2009, 96(1): 153-179.
[15] Karypis G, Aggarwal R, Kumar V, et al. Multilevel Hypergraph Partitioning: Applications in VLSI Domain[J]. IEEE Trans- actions on Very Large Scale Integration Systems, 1999, 7(1): 69-79.
[16] 冷明. 基于多水平方法的无向图剖分及其在VLSI设计中的应用研究[D]. 上海: 上海大学, 2008.
[17] 冷明, 孙凌宇, 郭恺强, 等. 赋权超图划分算法的电路划分实验比较研究[J]. 计算机工程与应用, 2012, 48(16): 74-79.
[18] David A P, Igor L M. Hypergraph Partitioning and Clustering[M]. [S. 1.]: CRC Press, 2007: 23-24.
[19] Seidman S B. Network Structure and Minimum Degree[J]. Social Networks, 1983, 5(1): 269-287.
[20] Batagelj V, Zaversnik M. Generalized Cores[J]. Journal of the ACM, 2001, 40(1): 799-809.
[21] Batagelj V, Zaversnik M. An O(m) Algorithm for Cores Decomposition of Networks[J]. Journal of the ACM, 2002, 41(1): 798-807.
[22] 孙凌宇, 冷明, 邓晓春, 等. 图压缩存储格式的核排序重边匹配算法[J]. 计算机工程与应用, 2011, 47(10): 41-47.
[23] 冷明, 孙凌宇, 边计年, 等. 一种时间复杂度为O(m)的无向超图核值求解算法[J]. 小型微型计算机系统, 2012, 33(12): 1014-1021.
[24] Alpert C J. The ISPD98 Circuit Benchmark Suite[C]//Proc. of ACM International Symposium of Physical Design. New York, USA: ACM Press, 1998: 80-85.
[25] 冷明, 孙凌宇, 郭恺强, 等. 一种ISPD98电路网表到赋权超图的转换算法[J]. 微电子学与计算机, 2011, 28(9): 111-115.
编辑索书志

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

Experiment Comparison of Weighted Hypergraph Core Based on Node Matching Strategies

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	李祥兵, 陈炼. 基于改进Faster?RCNN的自然场景人脸检测[J]. 计算机工程, 2021, 47(1): 210-216.
[2]	郝华颖, 赵昆, 苏攀, 张辉, 赵一天, 刘江. 一种基于改进ResU-Net的角膜神经分割算法[J]. 计算机工程, 2021, 47(1): 217-223.
[3]	刘瑄, 池明旻. 基于多粒度特征蒸馏的遥感图像场景分类研究[J]. 计算机工程, 2021, 47(1): 224-229,238.
[4]	徐龙壮, 彭力, 朱凤增. 多任务金字塔重叠匹配的行人重识别方法[J]. 计算机工程, 2021, 47(1): 239-245,254.
[5]	李宇霞, 孙永奇, 闫茹, 朱卫国. 基于CNN图像识别与语义可靠性的路径搜索方法[J]. 计算机工程, 2021, 47(1): 255-263,274.
[6]	王润涵, 李兵, 滕奇志. 基于卷积神经网络的岩心FIB-SEM图像分割算法[J]. 计算机工程, 2021, 47(1): 264-274.
[7]	王嘉庆, 梅礼晔, 张俊华. 基于深度学习的手骨X射线图像骨龄评估[J]. 计算机工程, 2021, 47(1): 291-297.
[8]	李兰, 郑雨薇, 魏少玮, 胡克勇. 基于注意力机制的商家招牌分类研究[J]. 计算机工程, 2021, 47(1): 305-311.
[9]	姜妍, 张立国. 面向深度学习模型的对抗攻击与防御方法综述[J]. 计算机工程, 2021, 47(1): 1-11.
[10]	闫帅明, 卜旭辉, 朱盼盼, 梁嘉琪. 一种数据丢包情况下的交叉口排队长度均衡控制方法[J]. 计算机工程, 2021, 47(1): 21-29.
[11]	韩虎, 赵启涛, 孙天岳, 刘国利. 面向社交媒体评论的上下文语境讽刺检测模型[J]. 计算机工程, 2021, 47(1): 66-71.
[12]	余恒, 王让定, 严迪群, 张雪垣. 基于采样值排序的音频可逆隐写算法[J]. 计算机工程, 2021, 47(1): 123-128,138.
[13]	龙恳, 李伟, 鲁江丽, 蒋明均, 隆泉. 基于匹配理论的NOMA异构网络资源分配算法[J]. 计算机工程, 2021, 47(1): 165-171.
[14]	辛伟瑶, 李剑, 王小亮, 李禹剑. 基于深度学习的地下浅层震源定位方法[J]. 计算机工程, 2020, 46(9): 292-297.
[15]	崔坤坤, 樊绍胜. 基于动态双窗口的机器人视觉导航与特征识别方法[J]. 计算机工程, 2020, 46(9): 313-320.