Research Article
BibTex RIS Cite

The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm

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

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.

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.

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

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

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.

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.
There are 19 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Makaleler
Authors

Serkan Güldal

Michael Lıpscomb This is me

Murat Tanık This is me

Publication Date June 2, 2020
Submission Date March 23, 2020
Published in Issue Year 2020 Volume: 7 Issue: 12

Cite

APA Güldal, S., Lıpscomb, M., & Tanık, M. (2020). The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, 7(12), 14-23.
AMA Güldal S, Lıpscomb M, Tanık M. The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi. June 2020;7(12):14-23.
Chicago Güldal, Serkan, Michael Lıpscomb, and Murat Tanık. “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7, no. 12 (June 2020): 14-23.
EndNote Güldal S, Lıpscomb M, Tanık M (June 1, 2020) The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7 12 14–23.
IEEE S. Güldal, M. Lıpscomb, and M. Tanık, “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”, Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, vol. 7, no. 12, pp. 14–23, 2020.
ISNAD Güldal, Serkan et al. “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7/12 (June 2020), 14-23.
JAMA Güldal S, Lıpscomb M, Tanık M. The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi. 2020;7:14–23.
MLA Güldal, Serkan et al. “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, vol. 7, no. 12, 2020, pp. 14-23.
Vancouver Güldal S, Lıpscomb M, Tanık M. The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi. 2020;7(12):14-23.