Abstract
Determining valid clustering is an important research problem. This problem becomes complex if the underlying data has inherent uncertainties. The work presented in this paper deals with clustering large probabilistic graphs using multi-population evolutionary algorithm. The evolutionary algorithm (EA) initializes its multiple populations, each representing a deterministic version of the same probabilistic graph given to it as an input. Multiple deterministic versions of the same input graph are generated by applying different thresholds to the edges. Each chromosome of the multiple populations represents one complete clustering solution. For the purpose of clustering, EA is employed which is guided by pKwikCluster algorithm. The proposed approach is tested on two natively probabilistic graphs and nine synthetically converted probabilistic graphs using cluster validity indices of Davies-Bouldin index, Dunn index, and Silhouette coefficient. The proposed approach is also compared with two baseline clustering algorithms for uncertain data, Fuzzy-DBSCAN and uncertain K-mean and two state-of-the-art approaches for clustering probabilistic graphs. The results obtained suggest that the proposed solution gives better performance than the baseline methods and the state-of-the-art algorithms.
Original language | English |
---|---|
Pages (from-to) | 78-95 |
Number of pages | 18 |
Journal | Information Sciences |
Volume | 317 |
DOIs | |
Publication status | Published - 1 Oct 2015 |
Bibliographical note
Publisher Copyright:© 2015 Elsevier Inc. All rights reserved.
Keywords
- Clustering
- Graph mining
- Multi-population evolutionary algorithm
- Probabilistic graphs
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence