Designing and finding beneficial community structures on social networks and beyond

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 con-notations 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. (2) Communities that exist in a probabilistic space who share common behaviours or characteristics, modelled via an uncertain bipartite network graph. In particular we ex-amine 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 safeguard 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 of Award	2024
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Lei CHEN (Supervisor)