Clustering large probabilistic graphs using multi-population evolutionary algorithm

Zahid Halim*, Muhammad Waqas, Syed Fawad Hussain

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)


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 languageEnglish
Pages (from-to)78-95
Number of pages18
JournalInformation Sciences
Publication statusPublished - 1 Oct 2015

Bibliographical note

Publisher Copyright:
© 2015 Elsevier Inc. All rights reserved.


  • 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


Dive into the research topics of 'Clustering large probabilistic graphs using multi-population evolutionary algorithm'. Together they form a unique fingerprint.

Cite this