Designing and Finding Beneficial Community Structures on Social Networks and Beyond

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


PhD Thesis Defence


Title: "Designing and Finding Beneficial Community Structures on Social 
Networks and Beyond"

By

Mr. Alexander Tiannan ZHOU


Abstract:

On graphs, the problem of community search is the task of identifying closely 
connected entities which could be considered as part of a larger collective. 
However, in the real world not all communities of similar sizes are considered 
equal from both the perspective of the network operator as well as their users. 
In modern community research, the task now involves being able to distinguish 
between different collections of tightly connected users via additional 
semantic information provided by the network.
 
In this thesis we examine three tasks of modelling communities with beneficial 
connotations on non-standard graphs: (1) Communities consisting of a diverse 
user make-up regardless of underlying demographic information, where we utilise 
a multi-partite graph model with a lower limit in terms of the numbers of 
groups involved rather than a strict value that was previously utilised as the 
norm. (2) Communities that exist in a probabilistic space who share common 
behaviours or characteristics, modelled via an uncertain bipartite network 
graph. In particular we examine the bitruss structure which uses the butterfly 
motif, which was previously undefined on uncertain bipartite graphs, as a 
foundational building block. (3) Communities of users who largely trust each 
other without devolving into an 'echo-chamber' on the signed graph model. Our 
structure introduced a minimum level of disagreement which may be used to 
represent a potential `push-back' valve to deploy against misinformation or 
blind trust.

We discuss the logic behind the overarching design of our subgraph structures 
(and how they specifically relate to real-world requirements) as well describe 
the algorithms we propose to find them.


Date:                   Friday, 31 May 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Prof. Yilong HAN (PHYS)

Committee Members:      Prof. Lei CHEN (Supervisor)
                        Prof. Qiong LUO
                        Prof. Ke YI
                        Prof. Can YANG (MATH)
                        Prof. Haibo HU (PolyU)