Distributed (α, β)-Core Decomposition over Bipartite Graphs

Qing Liu, Xuankun Liao, Xin Huang, Jianliang Xu*, Yunjun Gao

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

2 Citations (Scopus)

Abstract

(α, β)-core is an important cohesive subgraph model for bipartite graphs. Given a bipartite graph G, the problem of (α, β)-core decomposition is to compute non-empty (α, β)-cores for all possible values of α and β. The state-of-the-art (α, β)-core decomposition algorithm is a peeling-based algorithm, which iteratively deletes the vertex from high degree to low degree. However, as the peeling-based algorithm is designed for centralized environments, it cannot be applied to distributed environments, where graphs are partitioned and stored in different machines. Motivated by this, in this paper, we study the distributed (α, β)-core decomposition problem, aiming to develop new algorithms to support (α, β)-core decomposition in distributed environments. To this end, first, we analyze the local properties of (α, β)-core, and devise n-order Bi-indexes for the vertex, which are iteratively defined using the vertex neighbors’ (n − 1)-order Bi-indexes. Next, we propose an algorithm for (α, β)-core decomposition through iteratively calculating n-order Bi-indexes for every vertex. To further improve the efficiency of the algorithm, we propose two optimizations. Then, we extend our proposed algorithms to different distributed graph processing frameworks to make them run in distributed environments. Finally, extensive experimental results on both real and synthetic bipartite graphs demonstrate the efficiency of our proposed algorithms.
Original languageEnglish
Title of host publicationProceedings - 2023 IEEE 39th International Conference on Data Engineering, ICDE 2023
Place of PublicationAnaheim, CA, USA
PublisherIEEE
Pages909-921
Number of pages13
ISBN (Electronic)9798350322279
ISBN (Print)9798350322286
DOIs
Publication statusPublished - 3 Apr 2023
Event39th IEEE International Conference on Data Engineering, ICDE 2023 - Anaheim, United States
Duration: 3 Apr 20237 Apr 2023
https://icde2023.ics.uci.edu/
https://ieeexplore.ieee.org/xpl/conhome/10184508/proceeding

Publication series

NameProceedings - International Conference on Data Engineering
Volume2023-April
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X

Competition

Competition39th IEEE International Conference on Data Engineering, ICDE 2023
Country/TerritoryUnited States
CityAnaheim
Period3/04/237/04/23
Internet address

Fingerprint

Dive into the research topics of 'Distributed (α, β)-Core Decomposition over Bipartite Graphs'. Together they form a unique fingerprint.

Cite this