Araştırma Makalesi
BibTex RIS Kaynak Göster

The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm

Yıl 2020, Cilt: 7 Sayı: 12, 14 - 23, 02.06.2020

Öz

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.

Kaynakça

  • 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

Yıl 2020, Cilt: 7 Sayı: 12, 14 - 23, 02.06.2020

Öz

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.

Kaynakça

  • 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.
Toplam 19 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Serkan Güldal

Michael Lıpscomb Bu kişi benim

Murat Tanık Bu kişi benim

Yayımlanma Tarihi 2 Haziran 2020
Gönderilme Tarihi 23 Mart 2020
Yayımlandığı Sayı Yıl 2020 Cilt: 7 Sayı: 12

Kaynak Göster

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. Haziran 2020;7(12):14-23.
Chicago Güldal, Serkan, Michael Lıpscomb, ve Murat Tanık. “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7, sy. 12 (Haziran 2020): 14-23.
EndNote Güldal S, Lıpscomb M, Tanık M (01 Haziran 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, ve M. Tanık, “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”, Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, c. 7, sy. 12, ss. 14–23, 2020.
ISNAD Güldal, Serkan vd. “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7/12 (Haziran 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 vd. “The Modularity of Queen Graphs by Girvan-Newman Clustering Algorithm”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, c. 7, sy. 12, 2020, ss. 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.