Research Article
BibTex RIS Cite

The Effect of Scoring Factor for Leiden Algorithm

Year 2021, Volume: 21 Issue: 3, 559 - 564, 30.06.2021

Serkan Güldal

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

Abstract

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.

Keywords

Clustering Graph Leiden Algorithm N-KCP

References

  • 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.

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

Year 2021, Volume: 21 Issue: 3, 559 - 564, 30.06.2021

Serkan Güldal

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

Abstract

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.

Keywords

Kümeleme Çizge Leiden Algoritması N-AKP

References

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

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Serkan Güldal 0000-0002-4247-0786

Publication Date June 30, 2021
Submission Date January 29, 2021
Published in Issue Year 2021 Volume: 21 Issue: 3

Cite

APA Güldal, S. (2021). The Effect of Scoring Factor for Leiden Algorithm. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, 21(3), 559-564. https://doi.org/10.35414/akufemubid.870835
AMA Güldal S. The Effect of Scoring Factor for Leiden Algorithm. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi. June 2021;21(3):559-564. doi:10.35414/akufemubid.870835
Chicago Güldal, Serkan. “The Effect of Scoring Factor for Leiden Algorithm”. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 21, no. 3 (June 2021): 559-64. https://doi.org/10.35414/akufemubid.870835.
EndNote Güldal S (June 1, 2021) The Effect of Scoring Factor for Leiden Algorithm. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 21 3 559–564.
IEEE S. Güldal, “The Effect of Scoring Factor for Leiden Algorithm”, Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, vol. 21, no. 3, pp. 559–564, 2021, doi: 10.35414/akufemubid.870835.
ISNAD Güldal, Serkan. “The Effect of Scoring Factor for Leiden Algorithm”. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 21/3 (June 2021), 559-564. https://doi.org/10.35414/akufemubid.870835.
JAMA Güldal S. The Effect of Scoring Factor for Leiden Algorithm. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi. 2021;21:559–564.
MLA Güldal, Serkan. “The Effect of Scoring Factor for Leiden Algorithm”. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, vol. 21, no. 3, 2021, pp. 559-64, doi:10.35414/akufemubid.870835.
Vancouver Güldal S. The Effect of Scoring Factor for Leiden Algorithm. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi. 2021;21(3):559-64.
 Download Cover Image