Unveiling critical node-to-node relationships for complex network analysis

Download files
Access & Terms of Use
open access
Embargoed until 2023-10-06
Copyright: Chen, Xiaoshuang
Graphs are widely used to represent interactions (i.e., edges) between entities (i.e., nodes/vertices) in a large spectrum of applications, including social networks, biological protein-protein networks, and e-commerce networks. One fundamental task in graph analysis is to explore node-to-node relationships such as "how similar two proteins are in biological networks'' and "whether or not a user can influence another user in social networks''. In this thesis, we study the following three problems, which are of great importance in exploring these relationships. Firstly, we study the problem of role similarity computation. As one of the structural node similarity metrics, role similarity has the merit of indicating automorphism. However, existing algorithms cannot handle large-scale graphs. In this thesis, we propose an efficient algorithm StructSim, which admits a pre-computed index to query a node pair in O(k log D) time, where k is a small user-defined parameter, and D is the maximum node degree. To build the index efficiently, we further devise an FM-sketch-based technique that can handle billion-scale graphs. Secondly, we study how to quantify approximate simulation. Simulation and its variants are useful binary relations among nodes. However, all simulation variants are coarse "yes-or-no'' indicators that simply confirm or refute whether one node simulates another, which limits the scope of their utility. Therefore, it is meaningful to develop a fractional simulation measure to quantify the extent that a node simulates another. To this end, we propose a general fractional simulation computation framework that can be configured to quantify the extent of different simulation variants. Thirdly, we study the reachability problem on temporal bipartite graphs. Reachability, which studies if a node can reach the other node, has been extensively studied on (temporal) unipartite graphs, while it remains largely unexplored on temporal bipartite graphs. In this thesis, we study the temporal bipartite reachability problem. Specifically, a vertex u reaches a vertex w in a temporal bipartite graph if they are connected through a series of consecutive wedges with time constraints. We propose an index-based method to support fast reachability queries, and we also devise effective techniques to accelerate the index construction process.
Persistent link to this record
Link to Publisher Version
Link to Open Access Version
Additional Link
Chen, Xiaoshuang
Lin, Xuemin
Zhang, Ying
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
Resource Type
Degree Type
PhD Doctorate
UNSW Faculty
download public version.pdf 5.69 MB Adobe Portable Document Format
Related dataset(s)