EUVIMEDEUVIMED entdecken
Crossref

gCore: Exploring Cross-Layer Cohesiveness in Multi-Layer Graphs

Dandan Liu, Zhaonian Zou

Proceedings of the VLDB Endowment · 2023-07 · 16 (11) · 3201-3213

DOI: 10.14778/3611479.3611519 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 24.08.2023. Verfasst von Dandan Liu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 37 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

As multi-layer graphs can give a more accurate and reliable picture of the complex relationships between entities, cohesive subgraph mining, a fundamental task in graph analysis, has been studied on multi-layer graphs in the literature. However, existing cohesive subgraph models are designated for special multi-layer graphs such as multiplex networks and heterogeneous information networks. In this paper, we propose generalized core (gCore), a new notion of cohesive subgraph on general multi-layer graphs without any predefined constraints on the interconnections between vertices. The gCore model considers both the intra-layer and cross-layer cohesiveness of vertices. Three related problems are studied in this paper including gCore search (GCS), gCore decomposition (GCD), and gCore indexing (GCI). A polynomial-time algorithm based on the peeling paradigm is proposed to solve the GCS problem. By considering the containment among gCores, a "tree of trees" data structure called KP-tree is designed for efficiently solving the GCD problem and serving as a compact storage and index of all gCores. Several advanced lossless compaction techniques including node/subtree elimination, subtree transplant, and subtree merge are proposed to help reduce the storage overhead of the KP-tree and speed up the process of solving GCD and GCI. Besides, a KP-tree-based GCS algorithm is designed, which can retrieve any gCore in linear time in the size of the gCore and the height of the KP-tree. The experiments on 10 real-world graphs verify the effectiveness of the gCore model and the efficiency of the proposed algorithms.

Zitieren

APA

Liu, D., & Zou, Z. (2023). gCore: Exploring Cross-Layer Cohesiveness in Multi-Layer Graphs. Proceedings of the VLDB Endowment, 16(11), 3201-3213. https://doi.org/10.14778/3611479.3611519

Vancouver

Liu D, Zou Z. gCore: Exploring Cross-Layer Cohesiveness in Multi-Layer Graphs. Proceedings of the VLDB Endowment. 2023;16(11):3201-3213. doi:10.14778/3611479.3611519

BibTeX
@article{Liu2023,
  author = {Liu, Dandan and Zou, Zhaonian},
  title = {gCore: Exploring Cross-Layer Cohesiveness in Multi-Layer Graphs},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {11},
  pages = {3201--3213},
  doi = {10.14778/3611479.3611519}
}
Kostenlos starten →