A NEW SOLUTION METHOD FOR GRAPH CLUSTERING PROBLEM


Ordin B. , Ballı D. S.

Journal of Modern Technology and Engineering, vol.4, no.3, pp.211-225, 2019 (Refereed Journals of Other Institutions)

  • Publication Type: Article / Article
  • Volume: 4 Issue: 3
  • Publication Date: 2019
  • Title of Journal : Journal of Modern Technology and Engineering
  • Page Numbers: pp.211-225

Abstract

The purpose of the graph clustering problem is to divide the nodes of a given graph into clusters according to their similarities/distances. Graph clustering problems is NP-hard. In addition, the modularity is a quality measurement metric used for graph clustering and the modularity is strongly NP-complete. Therefore, it is very important to develop approximate and heuristics algorithms for graph clustering. This paper presents a new approach called the incremental graph clustering problem. The proposed method uses a ratio for each node of the given graph. The ratios are calculated by the adjacency matrix of the given graph. The proposed incremental approach is based on greedy, so it is uses collected information from previous iterations. It is illustrated that efficiency of the approach with computational experiments on 14 real world data sets in the literature. The results obtained by the incremental graph clustering algorithm and the k-spanning tree algorithm in the literature on 14 datasets are evaluated using by modularity quality metric for graph clustering. The values of this metric show the efficiency of the proposed algorithm, especially in large-scale data sets.