EUVIMEDEUVIMED entdecken
Crossref

Efficient Biclique Counting in Large Bipartite Graphs

Xiaowei Ye, Rong-Hua Li, Qiangqiang Dai, Hongchao Qin, Guoren Wang

Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-26

DOI: 10.1145/3588932 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Xiaowei Ye und 4 weiteren Autor:innen. Die Arbeit wurde bisher 21-mal zitiert (Crossref) und nennt 41 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A (p,q)-biclique is a complete subgraph (X,Y) that |X|=p, |Y|=q. Counting (p,q)-bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p,q)-bicliques for large p and q (e.g., p,q ≥ 10) is extremely difficult, because the number of (p,q)-bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p,q)-biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p,q)-bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p,q)-bicliques for all pairs of (p,q) using a combinatorial technique, instead of exhaustively enumerating all (p,q)-bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p,q)-bicliques for all pairs of (p,q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = min{p,q}). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.

Zitieren

APA

Ye, X., Li, R., Dai, Q., Qin, H., & Wang, G. (2023). Efficient Biclique Counting in Large Bipartite Graphs. Proceedings of the ACM on Management of Data, 1(1), 1-26. https://doi.org/10.1145/3588932

Vancouver

Ye X, Li R, Dai Q, Qin H, Wang G. Efficient Biclique Counting in Large Bipartite Graphs. Proceedings of the ACM on Management of Data. 2023;1(1):1-26. doi:10.1145/3588932

BibTeX
@article{Ye2023,
  author = {Ye, Xiaowei and Li, Rong-Hua and Dai, Qiangqiang and Qin, Hongchao and Wang, Guoren},
  title = {Efficient Biclique Counting in Large Bipartite Graphs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2023},
  volume = {1},
  number = {1},
  pages = {1--26},
  doi = {10.1145/3588932}
}
Kostenlos starten →