The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm

Year 2020, Volume: 7 Issue: 12, 14 - 23, 02.06.2020

Serkan Güldal , Michael Lıpscomb Murat Tanık

Abstract

The clustering of a given data set is a technique widely utilized data analysis method by data scientists for technological applications. Some portion of the analysis define the relations between data, and strong relations are identified as sub-communities by means of clustering algorithms. The collected functional relations between the clusters’ nodes extract the uninvestigated network properties. In this study, we investigated the relational properties of Queen graphs (graph representation of N-Queens problem) by the Girvan-Newman Clustering algorithm. Our investigation showed that the highly symmetric degree of nodes does not lead the symmetry in the sub-communities. While the distinct number of degrees increases with respect to board size, the number of subcommunities increases irregularly. Additionally, the maximum modularity score increases slower than the number of subcommunities.

Keywords

Girvan-Newman, Queens Graph, N-Queens Problem

Vezir Graflarının Girvan Newman Kümeleme Algoritması ile Modülerliği

Abstract

Kümeleme veri bilimcileri tarafından teknolojik uygulamalar için yaygın olarak kullanılan veri analiz tekniğidir. Yapılan analizlerin bir kısmı veriler arasındaki ilişkiyi tanımlamaktadır ve güçlü ilişkiler, kümeleme algoritmaları aracılığıyla alt kümeler oluşturur. Kümelerin düğümleri arasındaki işlevsel ilişkiler, araştırılmamış ağ özelliklerini ortaya çıkarmaktadır. Bu çalışmada, Girvan-Newman Kümeleme algoritması ile Vezir graflarının (N-Vezir problemi graf gösterimi) ilişkisel özelliklerini araştırdık. Araştırmamız yüksek simetrik düğümlerin alt topluluklarda simetriye yol açmadığını gösterdi. Tahta büyüklüğüne göre farklı düğüm dereceleri artarken, oluşan alt kümelerin sayısı da düzensiz olarak artmaktadır. Ayrıca, maksimum modülerlik puanı alt topluluk sayısından daha yavaş artış göstermektedir.

Keywords

Girvan-Newman, Vezir Grafları, N-Vezir Problemi

References

• C. F. Gauß, H. C. Schumacher, and C. A. F. Peters, Briefwechsel zwischen. Altona: Esch, 1860.
• J. Gingsburg, "Gauss's arithmetrization of the problem of n queens," Scripta Math. 5, pp. 63-66, 1939.
• G. Polya, "Uber die 'doppelt-periodischen' losungen des n-damen-problems," Mathematische Unterhaltungen und Spiele, pp. 364-374, 1918.
• É. Lucas, Recreations mathematiques. Vol. 4. Paris: Blanchard, 1960.
• V. Torggler, P. Aumann, H. Ritsch, and W. Lechner, "A Quantum N-Queens Solver," Quantum, vol. 3, 03/02 2018.
• F. Souza and F. Mello, "N-Queens Problem Resolution Using the Quantum Computing Model," IEEE Latin America Transactions, vol. 15, pp. 534-540, 03/01 2017.
• A. Draa, S. Meshoul, H. Talbi, and M. Batouche, "A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem," Int. Arab J. Inf. Technol., vol. 7, pp. 21-27, 01/01 2010.
• S. Ss, R. Stephen, and V. Irudayaraj, "Survey on N-Queen Problem with Genetic Algorithm," INTERNATIONAL JOURNAL OF COMPUTER SCIENCES AND ENGINEERING, vol. 6, pp. 54-58, 03/01 2018.
• S. Nag and U. Sarkar, "An Adaptive Genetic Algorithm for Solving N-Queens Problem," 12/21 2017.
• E. Cengiz, S. Seyed, and T. Murat, "Different perspectives of the N-Queens problem," in Proceedings of the, A. C. M. annual conference Communications, ACM, 2 Penn Plaza, Suite 701, New York, NY 10121-0701, USA, 1992.
• Z. Wang, D. Huang, J. Tan, T. Liu, K. Zhao, and L. Li, "A parallel algorithm for solving the n-queens problem based on inspired computational model," (in English), Bio Systems, vol. 131, pp. 22-9, 2015.
• M. Girvan and M. E. J. Newman, "Community structure in social and biological networks," vol. 99, no. 12, pp. 7821-7826, 2002.
• S. Güldal, "Connectives of Knights Covering Problem By Girvan-Newman Clustering," presented at the SDPS 2019 Workshop, Madrid, Spain, 25-26, November 2019,
• M. E. J. J. T. E. P. J. B. Newman, "Detecting community structure in networks," journal article vol. 38, no. 2, pp. 321-330, March 01 2004.
• S. C. J. P. Johnson, "Hierarchical clustering schemes," journal article vol. 32, no. 3, pp. 241-254, September 01 1967.
• M. E. J. Newman, "Fast algorithm for detecting community structure in networks," Physical Review E, vol. 69, no. 6, p. 066133, 06/18/ 2004.
• L. Lee Johnson, C. B. Borkowf, and P. A. Shaw, "Chapter 21 - Hypothesis Testing," in Principles and Practice of Clinical Research (Third Edition), J. I. Gallin and F. P. Ognibene, Eds. Boston: Academic Press, 2012, pp. 255-270.
• G. Ouyang, D. K. Dey, and P. J. J. o. C. Zhang, "Clique-Based Method for Social Network Clustering," journal article April 02 2019.
• M. Bastian, S. Heymann, and M. Jacomy, "Gephi: an open source software for exploring and manipulating networks," in International AAAI Conference on Weblogs and Social Media, 2009.