International Journal of Applied Science and Engineering
Published by Chaoyang University of Technology

Yu-Ching Lu a and Goutam Chakrabortya, b

Graduate School of Software Information Science, Iwate Prefectural University, Iwate, Japan
Sendai Foundation of Applied Information Sciences, Japan


 

Download Citation: |
Download PDF


ABSTRACT


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.


Keywords: Graph clustering; social network analysis; multi-objective optimization; genetic algorithm.


Share this article with your colleagues

 


REFERENCES


  1. [1] Brin, S. and Pag, L. 1998. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30: 107–117. [Publisher Site]

  2. [2] Yutaka, M. 2003. Prediction and Discovering Small World Network. Society of Artificial Intelligence, 18, 3.

  3. [3] Yutaka, M. 2005. Network Structure and its Emergence. Proceedings of AAAI, 11–14.

  4. [4] Newman, M. E. J. 2010. Networks: An Introduction, Oxford. [Publisher Site]

  5. [5] Telesford, Q. K., Joyce, K. E., Hayasaka, S., Burdette, J. H. and Laurienti, P. J. 2011. The Ubiquity of Small-World Networks. Brain Connect, 1, 5: 67–375. [Publisher Site]

  6. [6] Vincent, L., Clrot, F. and Creff, N. 2015. K-means Clustering on a Classifier induced Representation Space: Application to Customer Contact Personalization. Real World Data Mining Applications Springer, 139–153. [Publisher Site]

  7. [7] Yuasa, M. and Hayama, S. 2012. Node Classification Method for Complex Network and its Application. Society of Artificial Intelligence, 111–120. [Publisher Site]

  8. [8] Leicht, E. A., Holme, P. and Newman, M. E. J. 2006. Vertex similarity in networks. Physical Review, 73, 026120. [Publisher Site]

  9. [9] Blondel, V. D., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E. 2008. Fast Unfolding of Communities in Large Networks. Statistical Mechanics: Theory and Experiment[Publisher Site]

  10. [10] Chakraborty, G., Sato, N. 2017. A Reliable Graph Clustering Method Using Genetic Algorithm. International Symposium on Nonlinear Theory and Applications, Cancun, Mexico.

  11. [11] Erd˝os, P. and R´enyi, A. 1959. On Random Graphs. Publicationes Mathematicae, 6: 290–297.
     
  12. [12] Watts, D. J. and Strogatz, S. H. 1998. Collective Dynamics of ’Small-World’ Networks. Nature, 393. [Publisher Site]
     
  13. [13] Barab´, A., Albert, L. A. and Albert, R. 1999. Emergence of Scaling in Random Networks. Science, 286, 5439: 509–512. [Publisher Site]

  14. [14] S. E. 2007. Graph Clustering. Computer Science Review, 1, 1: 27–64. [Publisher Site]

  15. [15] Mitchell, M. 1998. An Introduction to Genetic Algorithms, MIT press, ISBN: 0262631857. [Publisher Site]

  16. [16] Ghosal, A. K., Das, N., Bhattacharjee, S. and Chakraborty, Goutam. 2019. A Fast Parallel Genetic Algorithm Based Approach for Community Detection in Large Networks. Conference on Communication Systems and Networks, Bengaluru, India. [Publisher Site]

  17. [17] Palla, G., Derenyi, I., Farkas, I. and Vicsek, T. 2005. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 435: 814–818. [Publisher Site]

  18. [18] Clauset, A., Newman, M. E. J. and Moore, C. 2004. Finding Community Structure in Very Large Networks. Physical Review, 066111. [Publisher Site]

  19. [19] Hafez, A. I., Ghali, N. I., Hassanien, A. E. and Fahmy, A. A. 2012. Genetic Algorithms for Community Detection in Social Networks. Conference on Intelligent Systems Design and Applications, 460–465. [Publisher Site]

  20. [20] Shang, R., Bai, J., Jiao, L. and Jin, C. 2013. Community Detection based on Modularity and An Improved Genetic Algorithm. Physica A: Statistical Mechanics and its Applications, 392, 5: 1215–1231. [Publisher Site]

  21. [21] Lancichinetti, A., Fortunato, S. and Radicchi, F. 2008. Benchmark Graphs for Testing Community Detection Algorithms. Physical Review, 78, 046110. [Publisher Site]

  22. [22] Mitchell, M. 1998. An Introduction to Genetic Algorithms. MIT press, ISBN: 0262631857. [Publisher Site]


ARTICLE INFORMATION


Received: 2019-05-23
Revised: 2020-01-28
Accepted: 2020-03-26
Publication Date: 2020-06-01


Cite this article:

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


We use cookies on this website to improve your user experience. By using this site you agree to its use of cookies.