| 摘 要: 针对当二分图中一类节点的数量固定时,如何搜索另一类型节点数量排序为前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 |
