Stable Community Detection in Signed Bipartite Graph: A Bitruss-Based Model

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


MPhil Thesis Defence


Title: "Stable Community Detection in Signed Bipartite Graph: A Bitruss-Based
Model"

By

Mr. Kai Hiu CHUNG


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:                   Friday, 1 December 2023

Time:                   5:00pm - 7:00pm

Venue:                  Room 4475
                        lifts 25/26

Committee Members:      Prof. Lei Chen (Supervisor)
                        Prof. Bo Li (Chairperson)
                        Prof. Qiong Luo


**** ALL are Welcome ****