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: h8b4b0c5f25b142be
Venue: VLDB
Year: 2019
Pagerank: 7.1494448e-05
Overall Rank: 3,632 | 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,794	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	7.0172514e-05
5,599	MEGA: Multi-View Semi-Supervised Clustering of Hypergraphs	2020	VLDB	6.0711441e-05
5,951	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	5.9366845e-05
9,240	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	5.2056825e-05
9,452	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1745448e-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 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
320	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021143147
589	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00015905948
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
1,474	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010556999
2,086	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0689711e-05
2,587	From Competition to Complementarity: Comparative Influence Diffusion and Maximization	2016	VLDB	8.2550609e-05
3,036	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.731521e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1706333e-05
3,820	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.005206e-05
4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3332415e-05
5,290	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.1937978e-05
6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8647415e-05
6,475	Clustering Uncertain Graphs	2018	VLDB	5.7736095e-05

Semantically Similar Papers

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