Efficient Structural Clustering in Large Uncertain Graphs
Efficient Structural Clustering in Large Uncertain Graphs
复制标题
DOI：
10.1109/icde48307.2020.00215
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Yongjiang Liang;Tingting Hu;Peixiang Zhao
中科院分区：
文献类型：
--
作者：
Yongjiang Liang;Tingting Hu;Peixiang Zhao
基于概率图模型的不确定图聚类已经引起了广泛的研究和广泛的应用。现有的结构聚类方法在很大程度上依赖于计算两两可靠的顶点之间的结构相似性，这已被证明是非常昂贵的，特别是在大型不确定图。在本文中，我们开发了一种新的，基于分解的方法，ProbSCAN，高效可靠的结构相似性计算与理论上提高了复杂性。我们进一步设计了一个具有成本效益的索引结构Ustory-Index，以及一系列强大的修剪策略，以加快不确定图中可靠的结构相似性计算。八个真实世界的不确定图的实验研究表明，我们提出的解决方案的有效性，实现了数量级的提高聚类效率，与国家的最先进的结构聚类方法在大型不确定图。
Clustering uncertain graphs based on the probabilistic graph model has sparked extensive research and widely varying applications. Existing structural clustering methods rely heavily on the computation of pairwise reliable structural similarity between vertices, which has proven to be extremely costly, especially in large uncertain graphs. In this paper, we develop a new, decomposition-based method, ProbSCAN, for efficient reliable structural similarity computation with theoretically improved complexity. We further design a cost-effective index structure UCNO-Index, and a series of powerful pruning strategies to expedite reliable structural similarity computation in uncertain graphs. Experimental studies on eight real-world uncertain graphs demonstrate the effectiveness of our proposed solutions, which achieves orders of magnitude improvement of clustering efficiency, compared with the state-of-the-art structural clustering methods in large uncertain graphs.