Querying and mining complex graphs : uncertainty and multi-relations
Xiangyu Ke · 2019
Graphs are important data representations that can ubiquitously model objects and their relations in a wide diversity of real-word applications.Effective and efficient graph analytics provide users with a deeper understanding of what is behind the data, thus can benefit a lot of useful applications such as node classification, node recommendation, link prediction, etc. Nowadays, besides the rapid growth in the volume of graphs, the inherent complexity on graphs has attracted great attention from data management community.This thesis will therefore focus on querying and mining uncertain and multi-relation graphs.Uncertain graphs can characterize the inherent uncertainty in the data due to many reasons, including noisy measurements, inference and prediction models, and explicit manipulations.For example, in a road network, each road junction can be represented as a node, and each road segment can serve as an edge with a blocking (e.g., traffic jam) probability.Meanwhile, the multi-relation graphs, where multiple edges may exist between a same pair of nodes, are even more expressive.Using the same example of a road network, the probability of traffic jam occurrence may vary with time.Other examples include interaction conditions and transformation probabilities from a protein to many others in a protein-protein interaction network, the topics and the corresponding probabilities that a user may re-tweet her friends' posts, etc.The uncertainty and the multi-relations over graphs bring about additional complexities to graph querying and mining.In this thesis, I investigated the following research problems.First, I conducted an experimental analyses about six state-of-the-art s-t reliability algorithms.The s-t reliability measures the probability that a target node t is reachable from a source node s.We introduced the algorithms and provided several corrections or adaptions.Then I implemented all of them on a same code base, and conducted the evaluation with unified metrics, medium to large real-world datasets, and same query i