Earticle

초록

영어

Clustering has an extensive and long history in a variety of scientific fields. Several recent studies of complex networks have suggested that the clustering analysis on networks has been an emerging research issue in data mining due to its variety of applications. Many graph clustering algorithms have been proposed in recent past, however, this clustering approach remains a challenging problem to solve real-world situation. In this work, we propose an aspiration criteria based graph clustering algorithm using stochastic local search for generating lower cost clustering results in terms of robustness and optimality for real-world complex network problems. In our proposed algorithm, all moves are meaningful and effective during the whole clustering process which indicates that moves are only accepted if the target node has neighbouring nodes in the destination cluster (moves to an empty cluster are the only exception to this instruction). An adaptive approach in our method is in incorporating the aspiration criteria for the best move (lower-cost changes) selection when the best non-tabu move involvements much higher cost compared to a tabued move then the tabued move is permitted otherwise the best non-tabu move is acceptable. Extensive experimentation with synthetic and real power-law distribution benchmark datasets show that our algorithm outperforms state-of-the-art graph clustering techniques on the basis of cost of clustering, cluster size, normalized mutual information (NMI) and modularity index of clustering results.

목차

Abstract
 1. Introduction
 2. Background
  2.1 Fundamentals of Restricted Neighborhood Search Clustering (RNSC)
  2.2 Aspiration Criteria
 3. Description of Aspiration Criteria Based Graph Clustering algorithm (ACOGCT)
  3.1 Overview of the Algorithm
  3.2 Comparative Features of RNSC and Proposed Algorithm
  3.3 Greedily Create an Initial Clustering Solution
  3.4 Move selection
  3.5 Application of a MOVE
  3.6 Cost Estimation
 4. Experimental Results and Discussions
  4.1 Performance Metrics
  4.2 Evaluation on Real-World Network Datasets
  4.3 Evaluation on Synthetic Dataset
  4.4 NMI Value on Real Power-law Distribution Graph
  4.5 Visualization of Real and Synthetic Power-law Graph and Clustering
 5. Conclusions
 References

키워드

저자

• Mousumi Dhara [ Department of Computer Engineering, IIT (BHU), Varanasi, India ]
• K. K. Shukla [ Department of Computer Engineering, IIT (BHU), Varanasi, India ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Advanced Science and Technology

• 간기

  월간

• pISSN

  2005-4238

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605