Efficient Balanced Signed Biclique Search in Signed Bipartite Graphs

Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:
Journal Article
IEEE Transactions on Knowledge and Data Engineering, 2024, 36, (3), pp. 1069-1083
Issue Date:
Filename Description Size
Efficient_Balanced_Signed_Biclique_Search_in_Signed_Bipartite_Graphs.pdfPublished version2.45 MB
Adobe PDF
Full metadata record
Finding bicliques is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph G and two positive integers τ U, τ V, a subgraph S= =(US,VS,ES) of G is a balanced signed biclique if i) S is a biclique without any unstable motif, i.e., unbalanced butterfly, and ii |US|≥τU and |VS|≥τV. In this paper, we propose and investigate two important problems, i.e., maximal balanced signed biclique enumeration and maximum balanced signed biclique identification. Due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problems directly. For the enumeration task, to construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for large networks, optimized strategies are proposed to overcome the three limitations in the baseline method. For the identification task, we first propose a baseline method by leveraging the proposed enumeration framework. Moreover, employing novel optimizations, an anchor balanced bipartite graph based search framework is introduced to accelerate the search. Finally, extensive experiments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of the proposed techniques and model.
Please use this identifier to cite or link to this item: