首页|Stable structural clustering in uncertain graphs
Stable structural clustering in uncertain graphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
The uncertain graph is widely used to model and analyze graph data in which the relation between objects is uncertain. We here study the structural clustering in uncertain graphs. As an important method in graph clustering, structural clustering can not only discover the densely connected core vertices, but also the hub vertices and the outliers. We propose a new clustering model named stable structural clustering, to solve the problem existing in previous models that the mined core vertex is a 'real' core one in only a small amount of possible worlds of the uncertain graph. Specifically, we first propose the concept of prob-ability core reliability which measures the probability of a vertex being a core vertex in the uncertain graph. On the basis of probability core reliability, we propose the definition of stable core vertex and formulate the stable structural clustering problem. Comparing with other structural clustering models, the proposed stable structural clustering performs bet -ter in crucial indicators that reflect the quality of clustering. We develop two algorithms to calculate stable core vertex, a precise dynamic programming based algorithm and a sam-pling based algorithm with some effective pruning techniques, based on which we give our structural clustering algorithm. Extensive experiments show that comparing with other structural clustering algorithms in uncertain graphs, the stable structural clustering algo-rithms proposed can get better clustering to a certain extent.(c) 2021 Elsevier Inc. All rights reserved.
Uncertain graphStructural clusteringMonte Carlo samplingDynamic programmingEFFICIENTALGORITHM
NSTL
Elsevier
