Efficient and Effective Algorithms for Clustering Uncertain Graphs

Summary: Clustering with probabilistic edges: formulates uncertain-graph k-median/k-center by maximizing node–center connection probabilities, establishes hardness, and achieves (1−1/e) and OPT_k^c approximations. Practical optimizations yield faster, higher-quality clustering than prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12183
Venue: VLDB
Year: 2019
Pagerank: 7.3095916e-05
Overall Rank: 3,559 | 75.59%
DOI: 10.14778/3311880.3311884

Incoming Non-self Citations Over Time

Authors

1. Kai Han (University of Science and Technology Beijing)
2. Fei Gui (University of Science and Technology Beijing)
3. Xiaokui Xiao (National University of Singapore)
4. Jing Tang (National University of Singapore)
5. Yuntian He (University of Science and Technology Beijing)
6. Zongmai Cao (University of Science and Technology Beijing)
7. He Huang (Soochow University)

BibTeX Citation

@article{han_vldb19,
        title = {{Efficient and Effective Algorithms for Clustering Uncertain Graphs}},
        author = {Han, Kai and Gui, Fei and Xiao, Xiaokui and Tang, Jing and He, Yuntian and Cao, Zongmai and Huang, He},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {6},
        pages = {667--680},
        doi = {10.14778/3311880.3311884},
        url = {https://doi.org/10.14778/3311880.3311884},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,723	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.1725638e-05
5,503	MEGA: Multi-View Semi-Supervised Clustering of Hypergraphs	2020	VLDB	6.1948574e-05
5,889	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	6.0496722e-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
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 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021436156
590	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.0001605572
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
1,478	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010651983
2,323	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.750808e-05
2,547	From Competition to Complementarity: Comparative Influence Diffusion and Maximization	2016	VLDB	8.4331576e-05
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
3,738	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.1602939e-05
4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.4780097e-05
5,168	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.3353772e-05
6,037	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.9990983e-05
6,345	Clustering Uncertain Graphs	2018	VLDB	5.9059861e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,741	Improvements on the k-center Problem for Uncertain Data	2018	PODS
2	4,672	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
3	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
4	5,889	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB
5	6,974	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB
6	1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB
7	5,556	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD
8	3,738	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD
9	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
10	6,345	Clustering Uncertain Graphs	2018	VLDB