Efficient and effective algorithms for clustering uncertain graphs

doi:10.14778/3311880.3311884

Efficient and effective algorithms for clustering uncertain graphs

2019-02-01

0

PRE

AI

DOI：10.14778/3311880.3311884

原文链接

原文求助

摘要

En 中文

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.

Efficient and effective algorithms for clustering uncertain graphs

摘要

期刊

机构

引用论文