Path Analysis in Massive Networks

Download files
Access & Terms of Use
open access
Copyright: Peng, You
Altmetric
Abstract
Graph is a ubiquitous structure representing entities and their relationships applied in many areas such as social networks, web graphs, and biological networks. One of the fundamental tasks in graph analytics is to investigate the relations between two vertices (e.g., users, items and entities) such as how a vertex A influences another vertex B, or to what extent A and B are similar to each other, based on the graph topology structure. In this case, we need path analysis. In many real-life applications such as social networks, biological networks and E-commerce networks, various path analysis is of great importance for a deeper understanding and better management of such networks. However, the massive graph volume and rapid evolution present huge challenges, which need highly efficient solutions. In this thesis, we study four important problems in path analysis in massive networks, and designs efficient and scalable solutions. Firstly, we present a graph analytical system GraphS developed at Alibaba to efficiently detect constrained cycles in dynamic graphs, where cycle is a special case of paths. The system supports large graphs with hundreds of millions of edges and vertices, and allows ad-hoc continuous queries to identify constrained cycles in a fast changing graph in real-time. Secondly, we investigate the problem of hop-constrained s-t simple path enumeration, which is fundamental in graph analytics. By designing novel barrier-based techniques and join framework, we developed two efficient algorithms, namely BC-DFS and JOIN, which outperform the state-of-the-art in both the theoretical side and practical side. Thirdly, we study the problem of label-constrained reachability (LCR) query, which is fundamental in many applications. Our method could answer a billion-scale LCR query within microseconds. Finally, we formally define the problem of label constrained k reach and provide efficient and scalable solutions.
Persistent link to this record
Link to Publisher Version
Link to Open Access Version
Additional Link
Author(s)
Peng, You
Supervisor(s)
Lin, Xuemin
Zhang, Wenjie
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2020
Resource Type
Thesis
Degree Type
PhD Doctorate
UNSW Faculty
Files
download public version.pdf 3.4 MB Adobe Portable Document Format
Related dataset(s)