Stable community detection in signed bipartite graph : a bitruss-based model

Abstract

Signed bipartite graphs represent relationships between two sets of entities, including both positive and negative interactions, allowing for a more comprehensive modeling of real-world networks. In this work, we focus on the detection of cohesive subgraphs in signed bipartite graphs by leveraging the concept of balanced butterflies. A balanced butterfly is a cycle of length 4 that is considered stable if it contains an even number of negative edges. We propose a novel model called the balanced (k, ϵ)-bitruss, which provides a concise representation of cohesive signed bipartite subgraphs while enabling control over density (k) and balance (ϵ). We prove that finding the largest balanced (k, ϵ)-bitruss is NP-hard and cannot be efficiently approximated to a significant extent. Furthermore, we extend the unsigned butterfly counting framework to efficiently compute both balanced and unbalanced butterflies. Based on this technique, we develop two greedy heuristic algorithms: one that prioritizes followers and another that focuses on balanced support ratios. Experimental results demonstrate that the greedy approach based on balanced support ratios outperforms the follower-based approach in terms of both efficiency and effectiveness.

Date of Award	2023
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Lei CHEN (Supervisor)