Yu-Ching Lu a and Goutam Chakrabortya, b a Graduate School of Software Information Science, Iwate Prefectural University, Iwate, Japan
b Sendai Foundation of Applied Information Sciences, Japan
Download Citation:
|
Download PDF
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.ABSTRACT
Keywords:
Graph clustering; social network analysis; multi-objective optimization; genetic algorithm.
Share this article with your colleagues
REFERENCES
ARTICLE INFORMATION
Received:
2019-05-23
Revised:
2020-01-28
Accepted:
2020-03-26
Available Online:
2020-06-01
Lu, Y.C., Chakraborty, G. 2020. Improving efficiency of graph clustering by genetic algorithm using multi-objective optimization. International Journal of Applied Science and Engineering, 17, 157–173. https://doi.org/10.6703/IJASE.202005_17(2).157
Cite this article: