A family of graph-theory-driven algorithms for managing complex probabilistic graph data efficiently

Traditionally, a great deal of attention has been devoted to the problem of effectively modeling and querying probabilistic graph data. State-of-the-art proposals are not prone to deal with complex probabilistic data, as they essentially introduce simple data models (e.g., based on confidence intervals) and straightforward query methodologies (e.g., based on the reachability property). According to our vision, these proposals need to be extended towards achieving the definition of innovative models and algorithms capable of dealing with the hardness of novel requirements posed by managing complex probabilistic graph data efficiently. Inspired by this main motivation, in this paper we propose and experimentally assess an innovative family of graph-theory-driven algorithms for managing complex probabilistic graph data, whose main double-fold goal consists in enhancing the expressive power of the underlying probabilistic graph data model and the expressive power of graph queries. © 2011 ACM.