Paper Info
Title
Efficient Structural Clustering on Probabilistic Graphs
Abstract
Structural clustering is a fundamental graph mining operator which is not only able to find densely-connected clusters, but it can also identify hub vertices and outliers in the graph. Previous structural clustering algorithms are tailored to deterministic graphs. Many real-world graphs, however, are not deterministic, but are probabilistic in nature because the existence of the edge is often inferred using a variety of statistical approaches. In this paper, we formulate the problem of structural clustering on probabilistic graphs, with the aim of finding reliable clusters in a given probabilistic graph. Unlike the traditional structural clustering problem, our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph. We develop a dynamic programming algorithm with several powerful pruning strategies to efficiently compute the reliable structural similarities. With the reliable structural similarities, we adapt an existing solution framework to calculate the structural clustering on probabilistic graphs. Comprehensive experiments on five real-life datasets demonstrate the effectiveness and efficiency of the proposed approaches.
Year
DOI
Venue
2019
10.1109/tkde.2018.2872553
IEEE Transactions on Knowledge and Data Engineering
Keywords
Field
DocType
Probabilistic logic,Clustering algorithms,Reliability,Heuristic algorithms,Proteins,Electronic mail,Dynamic programming
Data mining,Cluster (physics),Graph,Dynamic programming,Vertex (geometry),Computer science,Outlier,Operator (computer programming),Probabilistic logic,Cluster analysis
Journal
Volume
Issue
ISSN
31
10
1041-4347
Citations 
PageRank 
References 
1
0.36
0
Authors
7
Name
Order
Citations
PageRank
Yuxuan Qiu110.36
Rong-Hua Li238133.77
Jianxin Li344348.67
Shaojie Qiao420125.93
Guoren Wang51366159.46
Jeffrey Xu Yu67018464.96
Rui Mao736841.23