Capturing and leveraging collective behavior for large-scale social networks analysis
Creators: name: HUANG, Shixun
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 460502
subject: Data mining and knowledge discovery
classificationCode: 460506
subject: Graph, social and multimedia data
classificationCode: 460509
subject: Query processing and optimisation

description: Online social networks have been important parts of our daily life and provide a wealth of information for us to study social phenomena and human behavior. People's behavior in social networks is collective to a large extent since individual decision making is not made in isolation, and people interact with each other with their intentions and beliefs reflecting their real-world counterparts. Investigation of collective behavior is beneficial for various social network analysis and tasks. However, the intricate dependency between individual decision making, which becomes more obvious in large-scale social networks with complex and dynamic structures, pose challenges for effectively and efficiently capturing and even utilizing collective behavior. This thesis will tackle these challenges on the basis of collective behavior in three forms, namely information
diffusion in networks, community formation in networks and evolution in networks, which embrace the dependency between individual behavior under different contexts and comprehensively unveil the unanticipated and complex nature of collective behavior.

First, we investigate how to efficiently and effectively capture individual decision making on receiving information from others and further propagating it in the information diffusion flow, which is quite difficult due to the its inter-dependency and becomes much more complex and intractable when relationships between individuals are dynamically changing. We propose novel sampling and graph compression techniques to efficiently estimate individual influence spread with low memory footprints and theoretical guarantees, and utilize the estimation results to find trendsetters or the most influential users over a certain period of time in evolving social networks. Second, we study how to capture the statistics of significant and frequent interaction patterns between individuals which consist of biased and dependent individual interactions, and are the building blocks of higher-order organization or communities in networks. Mining such patterns is a resource consuming process due to their large appearance in large-scale networks
with complex structures, and we take the first step to mine these patterns with novel sampling techniques in a very efficient way that the sampled information can be leveraged by different graph partitioning kernels to produce accurate higher-order communities with theoretical guarantees. Third, we investigate how individual decisions with regard to interactions with others are made, which is highly dependent on each other and impacted by the dynamic relationships between individuals in fast evolving networks. We propose a novel graph representation learning method which efficiently captures complex temporal dependency between individuals to extract the impact factors driving individual interaction tendency towards others, and then leverage the information being captured to predict evolution in the network and boost the performance in multiple downstream tasks. We conduct extensive experiments on various real-world networks to demonstrate the effectiveness, efficiency and scalability of our proposed methods under each
of these three research directions.

To summarize, this thesis provides new ways to efficiently and effectively capture dependency of individual decision making in different forms of collective behavior in large-scale networks with complex and dynamic structures, and exploits collective behavior to benefit different downstream network analysis and tasks.