• 首页
  • 期刊简介
  • 编委会
  • 投稿指南
  • 收录情况
  • 杂志订阅
  • 联系我们
引用本文:唐东杭,吴进高,徐 建.二分图中高效计算top-n maximal α-biclique的方法研究[J].软件工程,2024,27(9):43-49.【点击复制】
【打印本页】   【下载PDF全文】   【查看/发表评论】  【下载PDF阅读器】  
←前一篇|后一篇→ 过刊浏览
分享到: 微信 更多
二分图中高效计算top-n maximal α-biclique的方法研究
唐东杭1, 吴进高2, 徐 建1
(1.杭州电子科技大学计算机学院, 浙江 杭州 310018;
2.浙江省教育技术中心, 浙江 杭州 310061)
tangtang@hdu.edu.cn; wujg@zjedu.gov.cn; jian.xu@hdu.edu.cn
摘 要: 针对当二分图中一类节点的数量固定时,如何搜索另一类型节点数量排序为前n 的maximal α-biclique的问题,提出了一种基础搜索算法和一种基于共同邻居概念的改进搜索算法。在使用(1,α)-core剪枝方法加快搜索的算法基础上,基于共同邻居搜索算法使用共同邻居的概念对算法进行了改进,该算法只遍历节点的二跳邻居,并利用节点顺序和最小阈值提高搜索效率。实验结果表明,两种算法都可以有效且高效地搜索节点数量排名为前n 的maximal α-biclique。与基础搜索算法相比,基于共同邻居搜索算法的搜索效率提升了80%,在实际应用场景中更具优势。
关键词: (1,α)-core;maximal α-biclique;共同邻居;节点顺序
中图分类号: TP391    文献标识码: A
Research of Efficient Computation of top-n maximal α-biclique on Bipartite Graph
TANG Donghang1, WU Jingao2, XU Jian1
(1.School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China;
2.Educational Technology Center of Zhejiang Province, Hangzhou 310061, China)
tangtang@hdu.edu.cn; wujg@zjedu.gov.cn; jian.xu@hdu.edu.cn
Abstract: This paper proposes a basic search algorithm and an improved search algorithm based on the concept of common neighbors to address the problem of how to search for the top-n maximal α-biclique in bipartite graphs when the number of nodes in one type is fixed. On the basis of using the (1, α)-core pruning method to accelerate the search algorithm, the common neighbors search algorithm enhances efficiency by only traversing the two-hop neighbors of the nodes and utilizing node order and a minimum threshold. Experimental results show that both algorithms can effectively and efficiently search for the top-n maximal α-biclique. Compared to the basic search algorithm, the common neighbors search algorithm improves search efficiency by 80% , making it more advantageous in practical application scenarios.
Keywords: (1,α)-core; maximal α-biclique; common neighbor; node order


版权所有:软件工程杂志社
地址:辽宁省沈阳市浑南区新秀街2号 邮政编码:110179
电话:0411-84767887 传真:0411-84835089 Email:semagazine@neusoft.edu.cn
备案号:辽ICP备17007376号-1
技术支持:北京勤云科技发展有限公司

用微信扫一扫

用微信扫一扫