Skyline Community Search over Edge-Attributed Bipartite Graphs
For practitioners analyzing bipartite graphs with multi-dimensional edge attributes, this work provides a more expressive community model and efficient algorithms, though the problem is specialized.
The paper introduces a novel community model, edge-attributed skyline community (ESC), for bipartite graphs that considers multi-dimensional edge attributes, and develops efficient peeling and expanding algorithms to search for ESCs, achieving improved precision and diversity over prior methods on real-world datasets.
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.