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

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