Clustering Uncertain Graphs

Summary: Introduces k-center clustering for uncertain graphs, optimizing minimum or average probabilistic connectivity to cluster centers across possible worlds. Proves NP-hardness and provides efficient approximation algorithms with guarantees and controllable clustering granularity. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: heeab03f872790cec
Venue: VLDB
Year: 2018
Pagerank: 5.7736095e-05
Overall Rank: 6,475 | 56.47%
DOI: 10.1145/3164135.3164143

Incoming Non-self Citations Over Time

Authors

1. Matteo Ceccarello (University of Padova)
2. Carlo Fantozzi (University of Padova)
3. Andrea Pietracaprina (University of Padova)
4. Geppino Pucci (University of Padova)
5. Fabio Vandin (University of Padova)

BibTeX Citation

@article{ceccarello_vldb18,
        title = {{Clustering Uncertain Graphs}},
        author = {Ceccarello, Matteo and Fantozzi, Carlo and Pietracaprina, Andrea and Pucci, Geppino and Vandin, Fabio},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {4},
        number = {11},
        pages = {472--484},
        doi = {10.1145/3164135.3164143},
        url = {https://doi.org/10.1145/3164135.3164143},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,632	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.1494448e-05
4,460	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.5894687e-05
9,452	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1745448e-05
11,312	X-Blossom: Massive Parallelization of Graph Maximum Matching	2025	VLDB	4.9793485e-05
11,770	Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem	2023	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
65	Freebase: A Collaboratively Created Graph Database For Structuring Human Knowledge	2008	SIGMOD	0.00038222149
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
320	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021143147
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,491	k-Clustering with Comparison and Distance Oracles	2024	PODS
2	6,950	Exceeding Expectations and Clustering Uncertain Data	2009	PODS
3	4,732	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD
4	7,114	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB
5	5,951	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB
6	2,304	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
7	1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB
8	6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB
9	3,820	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD
10	3,632	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB