Efficient and effective algorithms for clustering uncertain graphs
Authors:
Open Access
- 1 February 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 12 (6) , 667-680
Abstract
We consider the edge uncertainty in an undirected graph and study the k -median (resp. k -center) problems, where the goal is to partition the graph nodes into k clusters such that the average (resp. minimum) connection probability between each node and its cluster's center is maximized. We analyze the hardness of these problems, and propose algorithms that provide considerably improved approximation guarantees than the existing studies do. Specifically, our algorithms offer (1 -- 1/e)-approximations for the k -median problem and (OPTck)-approximations for the k -center problem, where OPTck is the optimal objective function value for k -center. In addition, our algorithms incorporate several non-trivial optimizations that significantly enhance their practical efficiency. Extensive experimental results demonstrate that our algorithms considerably outperform the existing methods on both computation efficiency and the quality of clustering results.Keywords
This publication has 55 references indexed in Scilit:
- Submodular Function Maximization2014
- Effective and Efficient Clustering Methods for Correlated Probabilistic GraphsIEEE Transactions on Knowledge and Data Engineering, 2013
- Distance-constraint reachability computation in uncertain graphsProceedings of the VLDB Endowment, 2011
- Minimum Data-Latency-Bound $k$-Sink Placement Problem in Wireless Sensor NetworksIEEE/ACM Transactions on Networking, 2011
- Ontology integration to identify protein complex in protein interaction networksProteome Science, 2011
- k-nearest neighbors in uncertain graphsProceedings of the VLDB Endowment, 2010
- Computational approaches for detecting protein complexes from protein interaction networks: a surveyBMC Genomics, 2010
- Concentration Inequalities and Martingale Inequalities: A SurveyInternet Mathematics, 2006
- Functional organization of the yeast proteome by systematic analysis of protein complexesNature, 2002
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985