Effective Community Search on Large Attributed Bipartite Graphs

Zongyu XU, Yihao ZHANG, Long YUAN*, Yuwen QIAN, Zi CHEN, Mingliang ZHOU, Qin MAO, Weibin PAN*

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

2 Citations (Scopus)

Abstract

Community search over bipartite graphs has attracted significant interest recently. In many applications such as the user-item bipartite graph in e-commerce and customer-movie bipartite graph in movie rating website, nodes tend to have attributes. However, the previous community search algorithms on bipartite graphs ignore attributes, thus making them to return results with poor cohesion with respect to their node attributes. In this paper, we study the community search problem on attributed bipartite graphs. Given a query vertex q, we aim to find the attributed (α,β)-communities of G, where the structure cohesiveness of the community is described by the (α,β)-core model, and the attribute similarity of two groups of nodes in the subgraph is maximized. In order to retrieve attributed communities from bipartite graphs, we first propose a basic algorithm composed of two steps: the generation and verification of candidate keyword sets, and then two improved query algorithms Inc and Dec are proposed. Inc is proposed considering the anti-monotonicity property of attributed bipartite graphs, then we adopt different generating methods and verify the order of candidate keyword sets and propose the Dec algorithm. After evaluating our solutions on eight large graphs, the experimental results demonstrate that our methods are effective and efficient in querying the attributed communities on bipartite graphs.

Original languageEnglish
Article number2359002
Number of pages25
JournalInternational Journal of Pattern Recognition and Artificial Intelligence
Volume37
Issue number2
Early online date28 Jan 2023
DOIs
Publication statusPublished - Feb 2023
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2023 World Scientific Publishing Company.

Keywords

  • attributed graphs
  • bipartite graphs
  • Community search

Fingerprint

Dive into the research topics of 'Effective Community Search on Large Attributed Bipartite Graphs'. Together they form a unique fingerprint.

Cite this