Name
Title | ||
|---|---|---|
The pursuit of a good possible world: extracting representative instances of uncertain graphs |
Abstract | ||
|---|---|---|
Data in several applications can be represented as an uncertain graph, whose edges are labeled with a probability of existence. Exact query processing on uncertain graphs is prohibitive for most applications, as it involves evaluation over an exponential number of instantiations. Even approximate processing based on sampling is usually extremely expensive since it requires a vast number of samples to achieve reasonable quality guarantees. To overcome these problems, we propose algorithms for creating deterministic representative instances of uncertain graphs that maintain the underlying graph properties. Specifically, our algorithms aim at preserving the expected vertex degrees because they capture well the graph topology. Conventional processing techniques can then be applied on these instances to closely approximate the result on the uncertain graph. We experimentally demonstrate, with real and synthetic uncertain graphs, that indeed the representative instances can be used to answer, efficiently and accurately, queries based on several properties such as shortest path distance, clustering coefficient and betweenness centrality. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2588555.2593668 | SIGMOD Conference |
Keywords | Field | DocType |
uncertain graph,graphs and networks,possible world,representative,query processing | Data mining,Shortest path problem,Vertex (geometry),Graph property,Computer science,Betweenness centrality,Sampling (statistics),Clique-width,Clustering coefficient,Topological graph theory | Conference |
Citations | PageRank | References |
11 | 0.57 | 24 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panos Parchas | 1 | 14 | 0.96 |
| Francesco Gullo | 2 | 483 | 32.63 |
| Dimitri Papadias | 3 | 7277 | 424.19 |
| Francesco Bonchi | 4 | 4173 | 200.47 |