  Uncertain graphs are prevalent in several applications including
communications systems, biological databases and social networks. The ever
increasing size of the underlying data renders both graph storage and query
processing extremely expensive. Sparsification has often been used to reduce
the size of deterministic graphs by maintaining only the important edges.
However, adaptation of deterministic sparsification methods fails in the
uncertain setting. To overcome this problem, we introduce the first
sparsification techniques aimed explicitly at uncertain graphs. The proposed
methods reduce the number of edges and redistribute their probabilities in
order to decrease the graph size, while preserving its underlying structure.
The resulting graph can be used to efficiently and accurately approximate any
query and mining tasks on the original graph. An extensive experimental
evaluation with real and synthetic datasets illustrates the effectiveness of
our techniques on several common graph tasks, including clustering coefficient,
page rank, reliability and shortest path distance.
