On uncertain graphs modeling and queries

摘要: Large-scale, highly-interconnected networks pervade both our society and the natural world around us. Uncertainty, on other hand, is inherent in underlying data due to a variety of reasons, such as noisy measurements, lack precise information needs, inference prediction models, or explicit manipulation, e.g., for privacy purposes. Therefore, uncertain, probabilistic, graphs are increasingly used represent linked many emerging application scenarios, they have recently become hot topic database research community. While classical graph algorithms reachability shortest path queries #P-complete, hence, more expensive uncertain graphs; various complex also over networks, pattern matching, diffusion, influence maximization queries. In this tutorial, we discuss sources their applications, uncertainty modeling, well complexities algorithmic advances processing context We emphasize current challenges highlight some future directions.