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: 4860
Venue: SIGMOD
Year: 2014
Pagerank: 7.1602939e-05
Overall Rank: 3,738 | 74.36%
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,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.3095916e-05
3,723	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.1725638e-05
5,889	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	6.0496722e-05
5,890	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	6.0496722e-05
6,037	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.9990983e-05
9,062	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	5.3251649e-05
9,281	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.2933125e-05
9,665	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.2406724e-05
9,948	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	5.1915905e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
947	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00013041389
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
1,254	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.0001147266
2,977	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.9035901e-05
3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.3214417e-05
4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.4780097e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD
2	3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB
3	5,890	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB
4	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
5	1,254	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB
6	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
7	1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB
8	5,889	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB
9	6,037	On Uncertain Graphs Modeling and Queries	2015	VLDB
10	6,345	Clustering Uncertain Graphs	2018	VLDB