IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY

Serkan Güldal

Araştırma Makalesi

5×5 AT ÇİZGESİ İÇİN MODÜLERLİK İLE AT İLİŞKİLERİ TANIMI

Yıl 2020, Cilt: 7 Sayı: 13, 104 - 114, 28.12.2020

Serkan Güldal

Öz

Modülerlik çok kullanılan çizge analiz tekniğidir. Modülerlik belirtilen ağı anlamlı ilişkili gruplara ayırır. Gruplar aynı gruptaki düğümler arasındaki ortak özelliklerin varlığını belirtir. Bu çalışmada 5 At Kaplama Problemi (5-AKP) çözüm arayışında 5×5 at çizgesi modülerlik ile analiz ediyoruz. Araştırmamız çözünürlüğün 0.1 ile 1.8 olduğu aralık için tamamlandı. Maksimum modülerlik puanı 0.8 çözünürlüğü için 0.3 bulundu. Buna ek olarak 0.1 5-AKP’nin bazı çözümlerini bulmak için ideal çözünürlüktür. Ayrıca, analizler 1.0 çözünürlüğünün 5-AKP’nin çözümleri bulmak için en optimize çözünürlük olduğunu gösterdi. Son olarak modülerlik 172 çözümden 1’den 7’ye kadar tanımlayabilmektedir.

Anahtar Kelimeler

At çizgesi, modülerlik, 5-AKP

Kaynakça

S. Bai, G. Zhu, and J. Huang, "An Intelligent Algorithm for the (1,2,2)-Generalized Knight's Tour Problem," in 2013 Ninth International Conference on Computational Intelligence and Security, 2013, pp. 583-588.
H. Jian and B. Sen, "An Efficient Algorithm for the Generalized (1,k)-Knight's Tours Problem," in 2009 First International Workshop on Education Technology and Computer Science, 2009, vol. 1, pp. 697-701.
P. Hingston and G. Kendall, Ant Colonies Discover Knight's Tours. 2004, pp. 1213-1218.
S. Bai, X. Liao, X. Qu, and Y. Liu, "Generalized Knight's Tour Problem and Its Solutions Algorithm," in 2006 International Conference on Computational Intelligence and Security, 2006, vol. 1, pp. 570-573.
I. Parberry, "An Efficient Algorithm for the Knight's Tour Problem," Discrete Applied Mathematics, vol. 73, pp. 251-260, 03/01 1997.
J. Demaio and B. Mathew, "Which Chessboards have a Closed Knight's Tour within the Rectangular Prism?," Electr. J. Comb., vol. 18, 01/05 2011.
A. Kumar, "Non-crossing Knight's Tour in 3-Dimension," 03/29 2008.
P. Aliquippa and Pennsylvania, "THEMATIC KNIGHT'S TOUR QUOTES," 06/29 2020.
A. Philip, "A Generalized Pseudo-Knight?s Tour Algorithm for Encryption of an Image," IEEE Potentials, vol. 32, no. 6, pp. 10-16, 2013.
J. Kumar and S. Nirmala, "Securing the contents of document images using knight moves and genetic approach," in 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2015, pp. 1091-1095.
J. Delei, B. Sen, and D. Wenming, "An Image Encryption Algorithm Based on Knight's Tour and Slip Encryption-Filter," in 2008 International Conference on Computer Science and Software Engineering, 2008, vol. 1, pp. 251-255.
M. Singh, A. Kakkar, and M. Singh, "Image Encryption Scheme Based on Knight's Tour Problem," Procedia Computer Science, vol. 70, pp. 245-250, 12/31 2015.
Q. B. Hou, X. F. Yang, Y. S. Wang, and X. S. Huang, "An image scrambling algorithm based on wavelet transform and Knight's tour," vol. 41, pp. 369-375, 02/01 2004.
D. C. Fisher, "On the n x n Knight Cover Problem," Ars Comb., vol. 69, / 2003.
F. Rubin, "Improved Knight Coverings," Ars Comb., vol. 69, / 2003.
F. Rubin, "Knight Covers for the 50x50 Chessboard," presented at the Mathfest 2004, Providence RI, 2004.
F. Rubin, "A Family of Efficient Knight Covering Patterns," Journal of Recreational Mathematics, Article vol. 33, no. 3, pp. 165-175, 2005.
F. Rubin, "An Improved Method for Finding Knight Covers," Ars Comb., vol. 82, / 2007.
B. Lemaire, "Knights Covers on NxN Chessboards," J. Recr. Math., vol. 31, pp. 87-99, 2003.
A. H. Jackson and R. P. Pargas, "Solutions to the NxN Knights Covering Problem," J. Recr. Math. , vol. 23, pp. 255-267, 1991.
F. Wei, "Research on Knight Covering Based on Breadth First Search Algorithm," (in English), Applied Mechanic and Materials, vol. 686, pp. 377-380, 2014.
S. Güldal, M. Lipscomb, and M. M. Tanik, "Solving Knights Covering Problem: Backtracking, Permutation, Bipartite Graph, and Independent Set," presented at the Nineteenth Annual Early Career Technical Conference, Birmingham, Alabama USA, 2019.
S. Güldal, M. M. Tanik, and M. M. Lipscomb, "Solving Knights Covering Problem by a Hybrid Algorithm," presented at the IEEE SouthEastConn, Huntsville, Alabama, April 11 - 14 2019,
S. Güldal, "Connectives of Knights Covering Problem By Girvan-Newman Clustering," presented at the SDPS 2019 Workshop, Madrid, Spain, November 25-26 2019, 2019.
"Analysis of the Application of Artificial Intelligence in Computer Networks Technology," IOP Conference Series: Materials Science and Engineering, vol. 750, p. 012097, 03/24 2020.
C. Engström and S. Silvestrov, "PageRank for networks, graphs, and Markov chains," Theory of Probability and Mathematical Statistics, vol. 96, p. 1, 10/05 2018.
Y. L. Karpov, I. Volkova, A. A. Vylitok, L. Karpov, and Y. G. Smetanin, "Designing classes’ interfaces for neural network graph model," Proceedings of the Institute for System Programming of RAS, vol. 31, pp. 97-112, 10/01 2019.
M. Gençer, "Sosyal Ağ Analizi Yöntemlerine Bir Bakış," Yildiz Social Science Review, vol. 3, pp. 19-34, 12/15 2017.
P. Nerurkar, M. Chandane, and S. Bhirud, "Understanding attribute and social circle correlation in social networks," Turkish Journal of Electrical Engineering and Computer Sciences, vol. 27, pp. 1228-1242, 03/22 2019.
N. Almolhem, Y. Rahal, and M. Dakkak, "Social network analysis in Telecom data," Journal of Big Data, vol. 6, 12/01 2019.
M. E. J. Newman, "Modularity and community structure in networks," vol. 103, no. 23, pp. 8577-8582, 2006.
K. Kugler, L. Mueller, A. Graber, and M. Dehmer, "Integrative Network Biology: Graph Prototyping for Co-Expression Cancer Networks," PloS one, vol. 6, p. e22843, 07/29 2011.
B. Eckman and P. Brown, "Graph data management for molecular and cell biology," IBM Journal of Research and Development, vol. 50, pp. 545-560, 12/01 2006.
V. Gadiyaram, S. Vishveshwara, and S. Vishveshwara, From Quantum Chemistry to Networks in Biology: A Graph Spectral Approach to Protein Structure Analyses. 2019.
L. Johnsen, "Graph Analysis of Word Networks," http://ceur-ws.org/Vol-2021/, vol. 2021, 01/01 2017.
E. Hasanah and D. Agustiningsih, Analysis of “Halal” Word in Social Media Using Text Mining and Word Networking. 2020.
R. Ozcelik, G. Uludoğan, S. Parlar, Ö. Bakay, O. Ergelen, and O. Yildiz, User Interface for Turkish Word Network KeNet. 2019, pp. 1-4.
S. Valverde, B. Vidiella Rocamora, R. Montañez Martínez, A. Fraile, S. Sacristán, and F. García-Arenal, "Coexistence of nestedness and modularity in host–pathogen infection networks," Nature Ecology & Evolution, pp. 1-10, 03/09 2020.
T. Shiino, "Phylodynamic analysis of a viral infection network," Frontiers in microbiology, vol. 3, p. 278, 07/31 2012.
M. E. J. Newman, "Analysis of weighted networks," Physical Review E, vol. 70, no. 5, p. 056131, 11/24/ 2004.
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.
V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. J. J. o. s. m. t. Lefebvre, and experiment, "Fast unfolding of communities in large networks," vol. 2008, no. 10, p. P10008, 2008.
R. Lambiotte, J.-C. Delvenne, and M. J. a. p. a. Barahona, "Laplacian dynamics and multiscale modular structure in networks," 2008.

IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY

Yıl 2020, Cilt: 7 Sayı: 13, 104 - 114, 28.12.2020

Serkan Güldal

Öz

Modularity is a widely utilized technic to analyze graphs. The modularity divides the specified network into relational clusters. The clusters highlight the shared properties between the clustered nodes. In the present study, we analyze 5×5 knight graph by modularity to extract 5 Knight Covering Problem (5-KCP) solutions. Our investigation is completed for resolutions from 0.1 to 1.8. The maximum modularity score is 0.3 found for resolution 0.8. Moreover, resolution 0.1 is the best resolution to find more solutions of 5-KCP. Also, the analyses show resolution 1.0 is the best resolution to find the solutions of 5-KCP efficiently. Lastly, modularity extracts the solutions from 1 to 7 out of 172 solutions.

Anahtar Kelimeler

Knight graph, Modularity, 5-KCP

Kaynakça

S. Bai, G. Zhu, and J. Huang, "An Intelligent Algorithm for the (1,2,2)-Generalized Knight's Tour Problem," in 2013 Ninth International Conference on Computational Intelligence and Security, 2013, pp. 583-588.
H. Jian and B. Sen, "An Efficient Algorithm for the Generalized (1,k)-Knight's Tours Problem," in 2009 First International Workshop on Education Technology and Computer Science, 2009, vol. 1, pp. 697-701.
P. Hingston and G. Kendall, Ant Colonies Discover Knight's Tours. 2004, pp. 1213-1218.
S. Bai, X. Liao, X. Qu, and Y. Liu, "Generalized Knight's Tour Problem and Its Solutions Algorithm," in 2006 International Conference on Computational Intelligence and Security, 2006, vol. 1, pp. 570-573.
I. Parberry, "An Efficient Algorithm for the Knight's Tour Problem," Discrete Applied Mathematics, vol. 73, pp. 251-260, 03/01 1997.
J. Demaio and B. Mathew, "Which Chessboards have a Closed Knight's Tour within the Rectangular Prism?," Electr. J. Comb., vol. 18, 01/05 2011.
A. Kumar, "Non-crossing Knight's Tour in 3-Dimension," 03/29 2008.
P. Aliquippa and Pennsylvania, "THEMATIC KNIGHT'S TOUR QUOTES," 06/29 2020.
A. Philip, "A Generalized Pseudo-Knight?s Tour Algorithm for Encryption of an Image," IEEE Potentials, vol. 32, no. 6, pp. 10-16, 2013.
J. Kumar and S. Nirmala, "Securing the contents of document images using knight moves and genetic approach," in 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2015, pp. 1091-1095.
J. Delei, B. Sen, and D. Wenming, "An Image Encryption Algorithm Based on Knight's Tour and Slip Encryption-Filter," in 2008 International Conference on Computer Science and Software Engineering, 2008, vol. 1, pp. 251-255.
M. Singh, A. Kakkar, and M. Singh, "Image Encryption Scheme Based on Knight's Tour Problem," Procedia Computer Science, vol. 70, pp. 245-250, 12/31 2015.
Q. B. Hou, X. F. Yang, Y. S. Wang, and X. S. Huang, "An image scrambling algorithm based on wavelet transform and Knight's tour," vol. 41, pp. 369-375, 02/01 2004.
D. C. Fisher, "On the n x n Knight Cover Problem," Ars Comb., vol. 69, / 2003.
F. Rubin, "Improved Knight Coverings," Ars Comb., vol. 69, / 2003.
F. Rubin, "Knight Covers for the 50x50 Chessboard," presented at the Mathfest 2004, Providence RI, 2004.
F. Rubin, "A Family of Efficient Knight Covering Patterns," Journal of Recreational Mathematics, Article vol. 33, no. 3, pp. 165-175, 2005.
F. Rubin, "An Improved Method for Finding Knight Covers," Ars Comb., vol. 82, / 2007.
B. Lemaire, "Knights Covers on NxN Chessboards," J. Recr. Math., vol. 31, pp. 87-99, 2003.
A. H. Jackson and R. P. Pargas, "Solutions to the NxN Knights Covering Problem," J. Recr. Math. , vol. 23, pp. 255-267, 1991.
F. Wei, "Research on Knight Covering Based on Breadth First Search Algorithm," (in English), Applied Mechanic and Materials, vol. 686, pp. 377-380, 2014.
S. Güldal, M. Lipscomb, and M. M. Tanik, "Solving Knights Covering Problem: Backtracking, Permutation, Bipartite Graph, and Independent Set," presented at the Nineteenth Annual Early Career Technical Conference, Birmingham, Alabama USA, 2019.
S. Güldal, M. M. Tanik, and M. M. Lipscomb, "Solving Knights Covering Problem by a Hybrid Algorithm," presented at the IEEE SouthEastConn, Huntsville, Alabama, April 11 - 14 2019,
S. Güldal, "Connectives of Knights Covering Problem By Girvan-Newman Clustering," presented at the SDPS 2019 Workshop, Madrid, Spain, November 25-26 2019, 2019.
"Analysis of the Application of Artificial Intelligence in Computer Networks Technology," IOP Conference Series: Materials Science and Engineering, vol. 750, p. 012097, 03/24 2020.
C. Engström and S. Silvestrov, "PageRank for networks, graphs, and Markov chains," Theory of Probability and Mathematical Statistics, vol. 96, p. 1, 10/05 2018.
Y. L. Karpov, I. Volkova, A. A. Vylitok, L. Karpov, and Y. G. Smetanin, "Designing classes’ interfaces for neural network graph model," Proceedings of the Institute for System Programming of RAS, vol. 31, pp. 97-112, 10/01 2019.
M. Gençer, "Sosyal Ağ Analizi Yöntemlerine Bir Bakış," Yildiz Social Science Review, vol. 3, pp. 19-34, 12/15 2017.
P. Nerurkar, M. Chandane, and S. Bhirud, "Understanding attribute and social circle correlation in social networks," Turkish Journal of Electrical Engineering and Computer Sciences, vol. 27, pp. 1228-1242, 03/22 2019.
N. Almolhem, Y. Rahal, and M. Dakkak, "Social network analysis in Telecom data," Journal of Big Data, vol. 6, 12/01 2019.
M. E. J. Newman, "Modularity and community structure in networks," vol. 103, no. 23, pp. 8577-8582, 2006.
K. Kugler, L. Mueller, A. Graber, and M. Dehmer, "Integrative Network Biology: Graph Prototyping for Co-Expression Cancer Networks," PloS one, vol. 6, p. e22843, 07/29 2011.
B. Eckman and P. Brown, "Graph data management for molecular and cell biology," IBM Journal of Research and Development, vol. 50, pp. 545-560, 12/01 2006.
V. Gadiyaram, S. Vishveshwara, and S. Vishveshwara, From Quantum Chemistry to Networks in Biology: A Graph Spectral Approach to Protein Structure Analyses. 2019.
L. Johnsen, "Graph Analysis of Word Networks," http://ceur-ws.org/Vol-2021/, vol. 2021, 01/01 2017.
E. Hasanah and D. Agustiningsih, Analysis of “Halal” Word in Social Media Using Text Mining and Word Networking. 2020.
R. Ozcelik, G. Uludoğan, S. Parlar, Ö. Bakay, O. Ergelen, and O. Yildiz, User Interface for Turkish Word Network KeNet. 2019, pp. 1-4.
S. Valverde, B. Vidiella Rocamora, R. Montañez Martínez, A. Fraile, S. Sacristán, and F. García-Arenal, "Coexistence of nestedness and modularity in host–pathogen infection networks," Nature Ecology & Evolution, pp. 1-10, 03/09 2020.
T. Shiino, "Phylodynamic analysis of a viral infection network," Frontiers in microbiology, vol. 3, p. 278, 07/31 2012.
M. E. J. Newman, "Analysis of weighted networks," Physical Review E, vol. 70, no. 5, p. 056131, 11/24/ 2004.
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.
V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. J. J. o. s. m. t. Lefebvre, and experiment, "Fast unfolding of communities in large networks," vol. 2008, no. 10, p. P10008, 2008.
R. Lambiotte, J.-C. Delvenne, and M. J. a. p. a. Barahona, "Laplacian dynamics and multiscale modular structure in networks," 2008.

Toplam 43 adet kaynakça vardır.

Ayrıntılar

Birincil Dil	İngilizce
Konular	Mühendislik
Bölüm	Makaleler
Yazarlar	Serkan Güldal 0000-0002-4247-0786
Yayımlanma Tarihi	28 Aralık 2020
Gönderilme Tarihi	9 Eylül 2020
Yayımlandığı Sayı	Yıl 2020 Cilt: 7 Sayı: 13

Kaynak Göster

APA	Güldal, S. (2020). IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, 7(13), 104-114.
AMA	Güldal S. IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi. Aralık 2020;7(13):104-114.
Chicago	Güldal, Serkan. “IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7, sy. 13 (Aralık 2020): 104-14.
EndNote	Güldal S (01 Aralık 2020) IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7 13 104–114.
IEEE	S. Güldal, “IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY”, Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, c. 7, sy. 13, ss. 104–114, 2020.
ISNAD	Güldal, Serkan. “IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi 7/13 (Aralık 2020), 104-114.
JAMA	Güldal S. IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi. 2020;7:104–114.
MLA	Güldal, Serkan. “IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY”. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi, c. 7, sy. 13, 2020, ss. 104-1.
Vancouver	Güldal S. IDENTIFICATION OF KNIGHTS’ RELATIONS FOR 5×5 KNIGHT GRAPH BY MODULARITY. Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi. 2020;7(13):104-1.

Kapak Resmi İndir

Makale Dosyaları

Tam Metin