DBScholar

Back to papers

The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs

Summary: Proposes deterministic representative instances of uncertain graphs preserving expected vertex degrees to reflect topology. This enables graph analytics on the representative to approximate shortest-path, clustering and betweenness efficiently. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hc44b75218cb22936
Venue
SIGMOD
Year
2014
Pagerank
6.9787375e-05
Overall Rank
3,826 | 74.36%
DOI
10.1145/2588555.2593668

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{parchas_sigmod14,
        title = {{The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs}},
        author = {Parchas, Panos and Gullo, Francesco and Papadias, Dimitris and Bonchi, Francesco},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2593668},
        url = {https://dl.acm.org/doi/10.1145/2588555.2593668},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank Citing Paper Year Venue Pagerank
3,644 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.1224321e-05
3,804 Butterfly Counting on Uncertain Bipartite Graphs 2022 VLDB 6.9907371e-05
5,768 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 5.9831541e-05
5,966 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.9142578e-05
6,180 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.8425819e-05
9,275 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.1860131e-05
9,491 Sage: A System for Uncertain Network Analysis 2022 VLDB 5.1549931e-05
9,884 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1037285e-05
10,173 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.0559291e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042804864
974 On the Representation and Querying of Sets of Possible Worlds 1987 SIGMOD 0.0001272688
1,069 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012164865
1,266 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011256294
3,046 Injecting Uncertainty in Graphs for Identity Obfuscation 2012 VLDB 7.7023081e-05
3,612 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 7.1436297e-05
4,997 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB 6.3093118e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,568 Querying Big Graphs within Bounded Resources 2014 SIGMOD
2 3,612 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB
3 5,768 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB
4 4,997 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB
5 1,266 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB
6 3,644 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB
7 1,069 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB
8 5,966 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB
9 6,180 On Uncertain Graphs Modeling and Queries 2015 VLDB
10 6,489 Clustering Uncertain Graphs 2018 VLDB