EUVIMEDEUVIMED entdecken
Crossref

Efficient Computation of Hyper-Triangles on Hypergraphs

Haozhe Yin, Kai Wang, Wenjie Zhang, Ying Zhang, Ruijia Wu, Xuemin Lin

Proceedings of the VLDB Endowment · 2024-11 · 18 (3) · 729-742

DOI: 10.14778/3712221.3712238 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 07.04.2025. Verfasst von Haozhe Yin und 5 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 61 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Hypergraphs, which use hyperedges to capture groupwise interactions among different entities, have gained increasing attention recently for their versatility in effectively modeling real-world networks. In this paper, we study the problem of computing hyper-triangles (formed by three fully-connected hyperedges), which is a basic structural unit in hypergraphs. Although existing approaches can be adopted to compute hyper-triangles by exhaustively examining hyperedge combinations, they overlook the structural characteristics distinguishing different hyper-triangle patterns. Consequently, these approaches lack specificity in computing particular hyper-triangle patterns and exhibit low efficiency. In this paper, we unveil a new formation pathway for hyper-triangles, transitioning from hyperedges to hyperwedges before assembling into hyper-triangles, and classify hyper-triangle patterns based on hyperwedges. Leveraging this insight, we introduce a two-step framework to reduce the redundant checking of hyperedge combinations. Under this framework, we propose efficient algorithms for computing a specific pattern of hyper-triangles. Approximate algorithms are also devised to support estimated counting scenarios. Furthermore, we introduce a fine-grained hypergraph clustering coefficient measurement that can reflect diverse properties of hypergraphs based on different hyper-triangle patterns. Extensive experimental evaluations conducted on 11 real-world datasets validate the effectiveness and efficiency of our proposed techniques.

Zitieren

APA

Yin, H., Wang, K., Zhang, W., Zhang, Y., Wu, R., & Lin, X. (2024). Efficient Computation of Hyper-Triangles on Hypergraphs. Proceedings of the VLDB Endowment, 18(3), 729-742. https://doi.org/10.14778/3712221.3712238

Vancouver

Yin H, Wang K, Zhang W, Zhang Y, Wu R, Lin X. Efficient Computation of Hyper-Triangles on Hypergraphs. Proceedings of the VLDB Endowment. 2024;18(3):729-742. doi:10.14778/3712221.3712238

BibTeX
@article{Yin2024,
  author = {Yin, Haozhe and Wang, Kai and Zhang, Wenjie and Zhang, Ying and Wu, Ruijia and Lin, Xuemin},
  title = {Efficient Computation of Hyper-Triangles on Hypergraphs},
  journal = {Proceedings of the VLDB Endowment},
  year = {2024},
  volume = {18},
  number = {3},
  pages = {729--742},
  doi = {10.14778/3712221.3712238}
}
Kostenlos starten →