Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs
Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs
复制标题
大型稀疏二部图的高效最大 Biclique 枚举
DOI：
10.14778/3529337.3529341
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Jianxin Li
中科院分区：
文献类型：
--
作者：
Lu Chen;Chengfei Liu;Rui Zhou;Jiajie Xu;Jianxin Li
最大二分图可以有效地揭示隐藏在二分图中的有意义的信息。最大 biclique 枚举 (MBE) 具有挑战性，因为最大 biclique 的数量随时间呈指数增长。最坏情况下二分图中的顶点数。然而，大型二部图通常非常稀疏，这与最坏情况相反，可能会导致快速 MBE 算法。未知的机会是利用稀疏性来大幅提高大型稀疏二分图的 MBE 效率。我们观察到，对于一个大型稀疏二部图，一个顶点
你
可能会收敛到同一顶点集中的几个顶点
你
通过其邻居，这表明顶点的枚举范围可能非常小。基于这一观察，我们提出了新的概念：单个顶点的单边核心性、每个顶点集的单边顺序以及大型稀疏二部图的单边收敛性（z），对于具有数亿条边的大型稀疏二部图，z可能是几千。使用单边顺序，每个单边核心度为 τ 的顶点最多只需要检查 2 个
τ
组合，以便可以枚举所有最大 bicliques，并且 τ 以 z 为界，这导致了一种新的 MBE 算法在
氧
*
(2
δ
）。然后，我们提出了一种批量枢轴技术来消除导致非最大 bicliques 的所有枚举，这保证了每个最大 bicliques 都报告在
氧
(z
e
)-延迟，其中
e
是边的数量。我们设计了新颖的数据结构，允许在可省略的空间中存储子图，以进一步加速 MBE。在合成和真实的大型数据集上进行了大量的实验，以证明我们提出的算法比现有算法更快、更具可扩展性。
Maximal bicliques are effective to reveal meaningful information hidden in bipartite graphs. Maximal biclique enumeration (MBE) is challenging since the number of the maximal bicliques grows exponentially w.r.t. the number of vertices in a bipartite graph in the worst case. However, a large bipartite graph is usually very sparse, which is against the worst case and may lead to fast MBE algorithms. The uncharted opportunity is taking advantage of the sparsity to substantially improve the MBE efficiency for large sparse bipartite graphs. We observe that for a large sparse bipartite graph, a vertex
u
may converge to a few vertices in the same vertex set as
u
via its neighbours, which reveals that the enumeration scope for a vertex could be very small. Based on this observation, we propose novel concepts: unilateral coreness for individual vertices, unilateral order for each vertex set and unilateral convergence (ζ) for a large sparse bipartite graph, ζ could be a few thousand for a large sparse bipartite graph with hundreds of million edges. Using the unilateral order, every vertex with τ unilateral coreness only needs to check at most 2
τ
combinations so that all maximal bicliques can be enumerated and τ is bounded by ζ, which leads to a novel MBE algorithm running in
O
*
(2
ζ
). We then propose a batch-pivots technique to eliminate all enumerations resulting in non-maximal bicliques, which guarantees that every maximal biclique is reported in
O
(ζ
e
)-delay, where
e
is the number of edges. We devise novel data structures that allow storing subgraphs at omissible space for further speeding up MBE. Extensive experiments are conducted on synthetic and real large datasets to justify that our proposed algorithm is faster and more scalable than the existing algorithms.
登录
查看更多内容
DOI：
10.1109/icde48307.2020.00063
发表时间：
2020-01
期刊：
2020 IEEE 36th International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Kai Wang;Xuemin Lin;Lu Qin;Wenjie Zhang;Ying Zhang
通讯作者：
Kai Wang;Xuemin Lin;Lu Qin;Wenjie Zhang;Ying Zhang
DOI：
10.1007/978-3-030-03599-0
发表时间：
2018-12
期刊：
--
影响因子：
--
作者：
Lijun Chang;Lu Qin
通讯作者：
Lijun Chang;Lu Qin
DOI：
10.1109/icde.2019.00017
发表时间：
2019-04
期刊：
2019 IEEE 35th International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
Lu Chen;Chengfei Liu;Kewen Liao;Jianxin Li;Rui Zhou
通讯作者：
Lu Chen;Chengfei Liu;Kewen Liao;Jianxin Li;Rui Zhou
DOI：
10.1007/978-3-030-39219-2_10
发表时间：
2020-02
期刊：
--
影响因子：
--
作者：
Arti Pandey;Gopika Sharma;N. Jain
通讯作者：
Arti Pandey;Gopika Sharma;N. Jain
影响因子：
14.9
作者：
Bu, DB;Zhao, Y;Chen, RS
通讯作者：
Chen, RS