Searching Personalized $k$-wing in Bipartite Graphs
Aman Abidi, Lu Chen, Rui Hong Zhou, Chengfei Liu · IEEE Transactions on Knowledge and Data Engineering · 2022
There are extensive studies focusing on the application scenario that all the bipartite cohesive subgraphs need to be discovered in a bipartite graph. However, we observe that, for some applications, one is interested in finding bipartite cohesive subgraphs containing a specific vertex. In this paper, we study a new query-dependent bipartite cohesive subgraph search problem based on$k$-wing model, named as personalized$k$-wing search problem. We study the$k$-wing equivalence relationship to summarize the edges of a bipartite graph$G$into groups. Therefore, all the edges of$G$are segregated into different groups, i.e.$k$-wing equivalence class, forming an efficient and wing number conserving index calledEquiWing-Graph. Further, we propose a more compact index,EquiWing-Tree, which is achieved by using our proposed$k$-butterfly looseapproach and discovered hierarchy properties. These indices are used to expedite the personalized$k$-wing search with a non-repetitive access to$G$, which leads to linear algorithms for searching the personalized$k$-wing. Moreover, we conduct a thorough study on the maintenance of the proposed indices for evolving bipartite graphs. We discover novel properties that help us localize the scope of the maintenance at a low cost. By exploiting the discoveries, we propose novel algorithms for maintaining the two indices, which substantially reduces the cost of maintenance. We perform extensive experimental studies in real-world graphs to validate the efficiency and effectiveness ofEquiWing-GraphandEquiWing-Treecompared to the baseline.