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.0018898e-05
Overall Rank: 3,821 | 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,633	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.1460604e-05
3,797	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.0139295e-05
5,756	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	6.002999e-05
5,952	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	5.9338741e-05
6,164	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8619652e-05
9,250	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	5.2032182e-05
9,461	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1720952e-05
9,847	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1206606e-05
10,136	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	5.0727027e-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.00042926566
971	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00012766663
1,064	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012202916
1,261	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011291616
3,037	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.727861e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1672388e-05
4,971	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3302434e-05

Semantically Similar Papers

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