高效搜索大规模二分图中最大的k个s-双团,提升实际应用效率。
Efficient Top-k s-Biplexes Search over Large Bipartite Graphs
- 提出分支算法MVBP,突破传统指数级枚举瓶颈。
- 在亚马逊评分数据集上,参数d2仅67,远小于顶点总数300万。
- 适合需要快速找最大s-双团的工业场景,如推荐系统分析。
在二分图中,若子图内每个顶点在对侧最多缺少s个邻居,则称其为s-双团。现有方法需枚举所有s-双团,但实际中只需找最大的k个。本文提出拓扑-最大k个s-双团搜索(TBS)问题,旨在找出顶点数最多的k个极大s-双团。证明该问题是NP-hard。提出分支算法MVBP,突破简单2^n枚举。进一步引入2跳分解、单侧边界和渐进搜索三项优化技术,形成FastMVBP算法,时间复杂度为O*(γ_s^{d_2}),其中γ_s<2,d_2远小于图顶点数。在8个真实与合成数据集上实验表明,该算法性能比基准高三个数量级,如在拥有超过300万顶点的AmazonRatings数据集中,d_2仅为67。
原文摘要 · Abstract (English)
In a bipartite graph, a subgraph is an $s$-biplex if each vertex of the subgraph is adjacent to all but at most $s$ vertices on the opposite set. The enumeration of $s$-biplexes from a given graph is a fundamental problem in bipartite graph analysis. However, in real-world data engineering, finding all $s$-biplexes is neither necessary nor computationally affordable. A more realistic problem is to identify some of the largest $s$-biplexes from the large input graph. We formulate the problem as the {\em top-$k$ $s$-biplex search (TBS) problem}, which aims to find the top-$k$ maximal $s$-biplexes with the most vertices, where $k$ is an input parameter. We prove that the TBS problem is NP-hard for any fixed $k\ge 1$. Then, we propose a branching algorithm, named MVBP, that breaks the simple $2^n$ enumeration algorithm. Furthermore, from a practical perspective, we investigate three techniques to improve the performance of MVBP: 2-hop decomposition, single-side bounds, and progressive search. Complexity analysis shows that the improved algorithm, named FastMVBP, has a running time $O^*(γ_s^{d_2})$, where $γ_s<2$, and $d_2$ is a parameter much smaller than the number of vertex in the sparse real-world graphs, e.g. $d_2$ is only $67$ in the AmazonRatings dataset which has more than $3$ million vertices. Finally, we conducted extensive experiments on eight real-world and synthetic datasets to demonstrate the empirical efficiency of the proposed algorithms. In particular, FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。