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: 11946
Venue: VLDB
Year: 2018
Pagerank: 5.9059861e-05
Overall Rank: 6,345 | 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,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.3095916e-05
4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.7407122e-05
9,281	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.2933125e-05
10,919	X-Blossom: Massive Parallelization of Graph Maximum Matching	2025	VLDB	5.093636e-05
11,458	Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem	2023	VLDB	5.093636e-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.00038697603
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021436156
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

Semantically Similar Papers

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