Effective and Efficient Clustering Methods for Correlated Probabilistic Graphs
Authors:
- 26 July 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 26 (5) , 1117-1130
Abstract
Recently, probabilistic graphs have attracted significant interests of the data mining community. It is observed that correlations may exist among adjacent edges in various probabilistic graphs. As one of the basic mining techniques, graph clustering is widely used in exploratory data analysis, such as data compression, information retrieval, image segmentation, etc. Graph clustering aims to divide data into clusters according to their similarities, and a number of algorithms have been proposed for clustering graphs, such as the pKwikCluster algorithm, spectral clustering, k-path clustering, etc. However, little research has been performed to develop efficient clustering algorithms for probabilistic graphs. Particularly, it becomes more challenging to efficiently cluster probabilistic graphs when correlations are considered. In this paper, we define the problem of clustering correlated probabilistic graphs. To solve the challenging problem, we propose two algorithms, namely the PEEDR and the CPGS clustering algorithm. For each of the proposed algorithms, we develop several pruning techniques to further improve their efficiency. We evaluate the effectiveness and efficiency of our algorithms and pruning methods through comprehensive experiments.Keywords
This publication has 21 references indexed in Scilit:
- Analysis of Agglomerative ClusteringAlgorithmica, 2012
- Efficient subgraph similarity search on large probabilistic graph databasesProceedings of the VLDB Endowment, 2012
- Distance-constraint reachability computation in uncertain graphsProceedings of the VLDB Endowment, 2011
- A generic framework for handling uncertain data with local correlationsProceedings of the VLDB Endowment, 2010
- Fast approximate spectral clustering2009
- Representing and Querying Correlated Tuples in Probabilistic Databases2007
- On mining cross-graph quasi-cliques2005
- Cluster graph modification problemsDiscrete Applied Mathematics, 2004
- On clusteringsJournal of the ACM, 2004
- Graph Clustering and Minimum Cut TreesInternet Mathematics, 2004