The Effect of Scoring Factor for Leiden Algorithm

Yıl 2021, , 559 - 564, 30.06.2021

Serkan Güldal

https://doi.org/10.35414/akufemubid.870835

Öz

Leiden algorithm is a widely utilized algorithm to cluster network graphs. It divides the specified network into smaller clusters. The clusters are relatively dense networks of vertices. In the process, the networks are divided based on quality factors. In this study, we compare the result of the Leiden algorithm with changing quality factors, namely Modularity and Constant Potts Model (CPM). For our analysis, we used 3×3 knight graph. Our investigation is completed for resolutions from 0.1 to 4.0 for Modularity and from 0.1 to 1.0 for CPM. The maximum quality scores are 0.9 and 0.59375 for Modularity and CPM respectively. The continuous decrease in the quality was recorded for both cases with respect to the increasing resolution. Both scoring factors are followed similar trends, but CPM has a relatively rapid division of the specified graph.

Anahtar Kelimeler

Clustering, Graph, Leiden Algorithm, N-KCP

Leiden Algoritmasında Kalite Faktörünün Etkisi

Öz

Leiden algoritması, çizgeleri kümelemek için yaygın olarak kullanılan bir algoritmadır ve belirtilen çizgeyi daha küçük kümelere böler. Bu kümeler, nispeten yoğun düğüm çizgeleridir. Süreçte çizgeler kalite faktörlerine göre kümelenir. Bu çalışmada Leiden algoritmasını Modülerlik ve Sabit Potts Modeli (CPM) kalite faktörleri ile değişimini karşılaştırılmıştır. Analiz için 3×3 at çizgesi kullanıldı. İnceleme Modülerlik için 0,1'den 4,0'a ve CPM için 0,1'den 1,0'a kadar olan çözünürlükler için tamamlandı. Maksimum kalite puanları Modülerlik ve CPM için sırasıyla 0,9 ve 0,59375'tir. Kalitede artan çözünürlüğe göre her iki durumda da sürekli düşüş kaydedildi. Her iki puanlama faktörü de benzer eğilimler izlendi, ancak CPM nispeten konu edilen çizgeyi daha hızlı kümeledi.

Anahtar Kelimeler

Kümeleme, Çizge, Leiden Algoritması, N-AKP

Kaynakça

• Ahlgren P, Chen Y, Colliander C, van Eck NJ. 2019. Community Detection Using Citation Relations and Textual Similarities in a Large Set of PubMed Publications. Paper presented at the ISSI.
• Aliquippa P, Pennsylvania, 2020. Thematic Knight's Tour Quotes
• Bai S, Liao X, Qu X, Liu Y. 2006, 3-6 Nov. 2006. Generalized Knight's Tour Problem and Its Solutions Algorithm. Paper presented at the 2006 International Conference on Computational Intelligence and Security.
• Bai S, Zhu G, Huang J. 2013, 14-15 Dec. 2013. An Intelligent Algorithm for the (1,2,2)-Generalized Knight's Tour Problem. Paper presented at the 2013 Ninth International Conference on Computational Intelligence and Security.
• Bastian M, Heymann S, Jacomy M. 2009. Gephi: an open source software for exploring and manipulating networks. Paper presented at the International AAAI Conference on Weblogs and Social Media.
• Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre EJJosmt, experiment, 2008. Fast unfolding of communities in large networks. 2008 (10), P10008.
• Boy JDJJoOSS, 2020. textnets: A Python package for text analysis with networks. 5 (54), 2594.
• Clifford T, Bruce J, Matta J. 2019. Using node-based resilience clustering to predict and analyze medical data. Paper presented at the 2019 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB).
• Delei J, Sen B, Wenming D. 2008, 12-14 Dec. 2008. An Image Encryption Algorithm Based on Knight's Tour and Slip Encryption-Filter. Paper presented at the 2008 International Conference on Computer Science and Software Engineering.
• Delvenne J-C, Schaub MT, Yaliraki SN, Barahona M. 2013. The stability of a graph partition: A dynamics-based framework for community detection. In Dynamics On and Of Complex Networks, Volume 2, 221-242, Springer.
• Demaio J, Mathew B, 2011. Which Chessboards have a Closed Knight's Tour within the Rectangular Prism? Electr. J. Comb., 18. doi:10.37236/495
• Devi JC, Poovammal EJPCS, 2016. An analysis of overlapping community detection algorithms in social networks. 89 349-358. Dong R, Yuan G-CJBb, 2020. GiniClust3: a fast and memory-efficient tool for rare cell type identification. 21 1-7.
• Esmailian P, Jalili M, 2015. Community Detection in Signed Networks: the Role of Negative ties in Different Scales. Scientific Reports, 5 (1), 14339. doi:10.1038/srep14339
• Fisher DC, 2003. On the n x n Knight Cover Problem. Ars Comb., 69.
• Gibbs H, Liu Y, Pearson CA, Jarvis CI, Grundy C, Quilty BJ, Diamond C, Eggo RMJNc, 2020. Changing travel patterns in China during the early stages of the COVID-19 pandemic. 11 (1), 1-9.
• Girvan M, Newman MEJ, 2002. Community structure in social and biological networks. 99 (12), 7821-7826. doi:10.1073/pnas.122653799 %J Proceedings of the National Academy of Sciences
• Güldal S. (2019). Connectives of Knights Covering Problem By Girvan-Newman Clustering. Paper presented at the SDPS 2019 Workshop, Madrid, Spain.
• Güldal S, 2020. Identification of Knights’ Relations For 5×5 Knight Graph by Modularity. Journal of Engineering Science of Adiyaman University 7(13), 104-114.
• Güldal S, Lipscomb M, Tanik MM. (2019). Solving Knights Covering Problem: Backtracking, Permutation, Bipartite Graph, and Independent Set. Paper presented at the Nineteenth Annual Early Career Technical Conference, Birmingham, Alabama USA.
• Güldal S, Tanik MM, Lipscomb MM. Solving Knights Covering Problem by a Hybrid Algorithm. Paper presented at the IEEE SouthEastConn, Huntsville, Alabama.
• Hingston P, Kendall G. (2004). Ant Colonies Discover Knight's Tours (Vol. 3339).
• Hou QB, Yang XF, Wang YS, Huang XS, 2004. An image scrambling algorithm based on wavelet transform and Knight's tour. 41, 369-375.
• Jackson AH, Pargas RP, 1991. Solutions to the NxN Knights Covering Problem. Journal of Recreational Mathematics 23, 255-267.
• Jian H, Sen B. 2009, 7-8 March 2009. An Efficient Algorithm for the Generalized (1,k)-Knight's Tours Problem. Paper presented at the 2009 First International Workshop on Education Technology and Computer Science.
• Kumar A, 2008. Non-crossing Knight's Tour in 3-Dimension.
• Kumar J, Nirmala S. 2015, 10-13 Aug. 2015. Securing the contents of document images using knight moves and genetic approach. Paper presented at the 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI).
• Lambiotte R, Delvenne J-C, Barahona MJapa, 2008. Laplacian dynamics and multiscale modular structure in networks.
• Lemaire B, 2003. Knights Covers on NxN Chessboards. J. Recr. Math., 31, 87-99.
• Li B, Gould J, Yang Y, Sarkizova S, Tabaka M, Ashenberg O, Rosen Y, Slyper M, Kowalczyk MS, Villani A-CJNM, 2020. Cumulus provides cloud-based data analysis for large-scale single-cell and single-nucleus RNA-seq. 17 (8), 793-798.
• Miura T, Asatani K, Sakata I. 2020. Classifying Sleeping Beauties and Princes Using Citation Rarity. Paper presented at the International Conference on Complex Networks and Their Applications.
• Newman MEJ, 2004. Analysis of weighted networks. Physical Review E, 70 (5), 056131. doi:10.1103/PhysRevE.70.056131
• Parberry I, 1997. An Efficient Algorithm for the Knight's Tour Problem. Discrete Applied Mathematics, 73, 251-260. doi:10.1016/S0166-218X(96)00010-8
• Pasimeni F, 2020. The Origin of the Sharing Economy Meets the Legacy of Fractional Ownership.
• Philip A, 2013. A Generalized Pseudo-Knight?s Tour Algorithm for Encryption of an Image. IEEE Potentials, 32 (6), 10-16. doi:10.1109/MPOT.2012.2219651
• Rubin F, 2003. Improved Knight Coverings. Ars Combinatoria, 69.
• Rubin F. (2004). Knight Covers for the 50x50 Chessboard. Paper presented at the Mathfest 2004, Providence RI.
• Rubin F, 2005. A Family of Efficient Knight Covering Patterns. Journal of Recreational Mathematics, 33 (3), 165-175.
• Rubin F, 2007. An Improved Method for Finding Knight Covers. Ars Combinatoria, 82.
• Singh M, Kakkar A, Singh M, 2015. Image Encryption Scheme Based on Knight's Tour Problem. Procedia Computer Science, 70, 245-250. doi:10.1016/j.procs.2015.10.081
• Traag VA, Van Dooren P, Nesterov YJPRE, 2011. Narrow scope for resolution-limit-free community detection. 84 (1), 016114.
• Traag VA, Waltman L, van Eck NJ, 2019. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9 (1), 5233-5233. doi:10.1038/s41598-019-41695-z
• van Laarhoven T, Marchiori EJC, 2013. An axiomatic study of objective functions for graph clustering.
• Van Laarhoven T, Marchiori EJTJoMLR, 2014. Axioms for graph clustering quality functions. 15 (1), 193-215.
• Wang C, Wang F, ssOnega TJTiG, Network optimization approach to delineating health care service areas: Spatially constrained Louvain and Leiden algorithms.
• Wei F, 2014. Research on Knight Covering Based on Breadth First Search Algorithm. Applied Mechanic and Materials, 686, 377-380.