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: 7.005206e-05
Overall Rank: 3,820 | 74.32%
DOI: 10.1145/2588555.2593668

Incoming Non-self Citations Over Time

Authors

1. Panos Parchas (Hong Kong University of Science and Technology)
2. Francesco Gullo (Yahoo)
3. Dimitris Papadias (Hong Kong University of Science and Technology)
4. Francesco Bonchi (Yahoo)

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,632	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.1494448e-05
3,794	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.0172514e-05
5,754	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	6.0058421e-05
5,951	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	5.9366845e-05
6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8647415e-05
9,240	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	5.2056825e-05
9,452	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1745448e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-05
10,132	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	5.0751052e-05

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.00042936299
970	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00012772086
1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012208695
1,260	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011296964
3,036	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.731521e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1706333e-05
4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3332415e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD
2	3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB
3	5,754	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB
4	4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
5	1,260	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB
6	3,632	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
7	1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB
8	5,951	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB
9	6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB
10	6,475	Clustering Uncertain Graphs	2018	VLDB