Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2401.12895 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913063379140608 |
|---|---|
| author | Guo, Fangda Luo, Xuanpu Xu, Shiyuan Gao, Haowen Liu, Yanghao Shen, Huawei Cheng, Xueqi |
| author_facet | Guo, Fangda Luo, Xuanpu Xu, Shiyuan Gao, Haowen Liu, Yanghao Shen, Huawei Cheng, Xueqi |
| contents | Bipartite graphs, modeling relationships between two types of entities, are widely used in practical applications. Community search, a fundamental problem in bipartite graphs, has gained significant attention. However, existing studies focus on measuring structural cohesiveness between vertex sets while either ignoring edge attributes or considering only one-dimensional importance. In this paper, we introduce a novel community model, named edge-attributed skyline community (ESC), which preserves structural cohesiveness and captures the inherent dominance of multi-dimensional edge attributes in bipartite graphs. To search for ESCs, we developed an efficient peeling algorithm that iteratively deletes edges with the minimum attribute in each dimension. Additionally, we devised an expanding algorithm to reduce the search space and speed up the filtering of unpromising vertices using a proven upper bound. Extensive experiments on large-scale real-world datasets demonstrate the efficiency, effectiveness, and scalability of our approach. A case study compared with prior arts demonstrates that our design improves the precision and diversity of results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12895 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Skyline Community Search over Edge-Attributed Bipartite Graphs Guo, Fangda Luo, Xuanpu Xu, Shiyuan Gao, Haowen Liu, Yanghao Shen, Huawei Cheng, Xueqi Social and Information Networks Graphics Bipartite graphs, modeling relationships between two types of entities, are widely used in practical applications. Community search, a fundamental problem in bipartite graphs, has gained significant attention. However, existing studies focus on measuring structural cohesiveness between vertex sets while either ignoring edge attributes or considering only one-dimensional importance. In this paper, we introduce a novel community model, named edge-attributed skyline community (ESC), which preserves structural cohesiveness and captures the inherent dominance of multi-dimensional edge attributes in bipartite graphs. To search for ESCs, we developed an efficient peeling algorithm that iteratively deletes edges with the minimum attribute in each dimension. Additionally, we devised an expanding algorithm to reduce the search space and speed up the filtering of unpromising vertices using a proven upper bound. Extensive experiments on large-scale real-world datasets demonstrate the efficiency, effectiveness, and scalability of our approach. A case study compared with prior arts demonstrates that our design improves the precision and diversity of results. |
| title | Skyline Community Search over Edge-Attributed Bipartite Graphs |
| topic | Social and Information Networks Graphics |
| url | https://arxiv.org/abs/2401.12895 |