文章詳目資料

International Journal of Applied Science and Engineering Scopus

  • 加入收藏
  • 下載文章
篇名 Improving Efficiency of Graph Clustering by Genetic Algorithm Using Multi-Objective Optimization
卷期 17:2
作者 Yu-Ching LuGoutam Chakraborty
頁次 157-173
關鍵字 Graph clusteringsocial network analysismulti-objective optimizationgenetic algorithmScopus
出刊日期 202005
DOI 10.6703/IJASE.202005_17(2).157

中文摘要

英文摘要

Information networks, like social networks on the internet, evolve naturally without constraint on degree or connectivity. The distribution of degree of such network is exponential, with a few nodes having a large degree, forming what is called a scale-free network. Scale-free networks form communities, or clusters of nodes. Discovering such clusters is the most important step for analysis of the information network. This is a NP-hard problem. Recently, genetic algorithm based works are reported, where the optimum number of clusters evolve automatically. The optimization criterion, the modularity index, is used as the fitness function of the chromosome. We observed that, if the diameter of the clusters are constrained to a lower value, during evolution of genetic search, a faster convergence is achieved. We used a multi-objective genetic search with two optimization criteria: the modularity index (the higher the better), and the largest diameter (the lower the better) of the communities defined by a chromosome. Simulation results, using network with known communities, show that using this multi-objective GA the result is stable, and achieves better modularity compared to the most often used Louvain algorithm.

相關文獻