二分图中高效计算top-n maximalα-biclique的方法研究  

Research of Efficient Computation of top-n maximalα-biclique on Bipartite Graph

作　　者：唐东杭 吴进高 徐建[1] TANG Donghang;WU Jingao;XU Jian(School of Computer,Hangzhou Dianzi University,Hangzhou 310018,China;Educational Technology Center of Zhejiang Province,Hangzhou 310061,China)

机构地区：[1]杭州电子科技大学计算机学院,浙江杭州310018 [2]浙江省教育技术中心,浙江杭州310061

出　　处：《软件工程》2024年第9期43-49,共7页Software Engineering

摘　　要：针对当二分图中一类节点的数量固定时,如何搜索另一类型节点数量排序为前n的maximalα-biclique的问题,提出了一种基础搜索算法和一种基于共同邻居概念的改进搜索算法。在使用(1,α)-core剪枝方法加快搜索的算法基础上,基于共同邻居搜索算法使用共同邻居的概念对算法进行了改进,该算法只遍历节点的二跳邻居,并利用节点顺序和最小阈值提高搜索效率。实验结果表明,两种算法都可以有效且高效地搜索节点数量排名为前n的maximalα-biclique。与基础搜索算法相比,基于共同邻居搜索算法的搜索效率提升了80%,在实际应用场景中更具优势。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.

关 键 词：(1 α)-core maximalα-biclique 共同邻居 节点顺序 

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