Skip to main content
Top
Published in:

01-12-2020 | Original Article

Correspondence analysis-based network clustering and importance of degenerate solutions unification of spectral clustering and modularity maximization

Author: Masaomi Kimura

Published in: Social Network Analysis and Mining | Issue 1/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Methods to find clusters in a network have been studied extensively because clustering has practical importance in many applications. Commonly used methods include spectral clustering and Newman’s modularity maximization. However, there has been no unified view of the two methods. In this study, we introduce an innovative guiding principle based on correspondence analysis to obtain node coordinates and discuss its equivalence to spectral clustering and Newman’s modularity. Besides, we discuss a degeneration case and its significance.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
go back to reference Abdi H, Bera M (2017) Correspondence analysis. Springer, New York, pp 1–12 Abdi H, Bera M (2017) Correspondence analysis. Springer, New York, pp 1–12
go back to reference Akbas E, Zhao P (2019) Graph clustering based on attribute-aware graph embedding. In: Security to community detection in social networking platforms. ASONAM 2017, Lecture notes in social networks. Springer, pp 109–131 (2019) Akbas E, Zhao P (2019) Graph clustering based on attribute-aware graph embedding. In: Security to community detection in social networking platforms. ASONAM 2017, Lecture notes in social networks. Springer, pp 109–131 (2019)
go back to reference Cao S, Lu W, Xu Q (2016) Deep neural networks for learning graph representations. In: Schuurmans D, Wellman MP (eds) Proceedings of the thirtieth AAAI conference on artificial intelligence, February 12–17, 2016, Phoenix, Arizona, USA. AAAI Press, pp 1145–1152 Cao S, Lu W, Xu Q (2016) Deep neural networks for learning graph representations. In: Schuurmans D, Wellman MP (eds) Proceedings of the thirtieth AAAI conference on artificial intelligence, February 12–17, 2016, Phoenix, Arizona, USA. AAAI Press, pp 1145–1152
go back to reference Chouchane A, Boutemine O, Bouguessa M (2019) On detecting multidimensional communities. In: Security to community detection in social networking platforms. ASONAM 2017, lecture notes in social networks, pp 45–78 Chouchane A, Boutemine O, Bouguessa M (2019) On detecting multidimensional communities. In: Security to community detection in social networking platforms. ASONAM 2017, lecture notes in social networks, pp 45–78
go back to reference Fortunato S, Barthelemy M (2007) Resolution limit in community detection. Proc Natl Acad Sci 104(1):36–41CrossRef Fortunato S, Barthelemy M (2007) Resolution limit in community detection. Proc Natl Acad Sci 104(1):36–41CrossRef
go back to reference Ge R, Jin C, Kakade SM, Netrapalli P, Sidford A (2016) Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis. CoRR abs/1604.03930 Ge R, Jin C, Kakade SM, Netrapalli P, Sidford A (2016) Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis. CoRR abs/1604.03930
go back to reference Hayashi C (1992) Quantification method III or correspondence analysis in medical science. Ann Cancer Res Ther 1(1):17–21CrossRef Hayashi C (1992) Quantification method III or correspondence analysis in medical science. Ann Cancer Res Ther 1(1):17–21CrossRef
go back to reference Hill MO (1974) Correspondence analysis: a neglected multivariate method. J R Stat Soc Ser C (Appl Stat) 23(3):340–354MathSciNet Hill MO (1974) Correspondence analysis: a neglected multivariate method. J R Stat Soc Ser C (Appl Stat) 23(3):340–354MathSciNet
go back to reference Hirschfeld HO (1935) A connection between correlation and contingency. In: Mathematical proceedings of the cambridge philosophical society, vol 31. Cambridge University Press, pp 520–524 Hirschfeld HO (1935) A connection between correlation and contingency. In: Mathematical proceedings of the cambridge philosophical society, vol 31. Cambridge University Press, pp 520–524
go back to reference Huang Z, Mamoulis N (2017) Heterogeneous information network embedding for meta path based proximity. CoRR abs/1701.05291 Huang Z, Mamoulis N (2017) Heterogeneous information network embedding for meta path based proximity. CoRR abs/1701.05291
go back to reference Jia Y, Zhang Q, Zhang W, Wang X (2019) Communitygan: community detection with generative adversarial nets Jia Y, Zhang Q, Zhang W, Wang X (2019) Communitygan: community detection with generative adversarial nets
go back to reference Kimura M (20119) Cab-nc: the correspondence analysis based network clustering method. In: 2019 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 538–539 Kimura M (20119) Cab-nc: the correspondence analysis based network clustering method. In: 2019 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 538–539
go back to reference Mellinger M (1987) Correspondence analysis: the method and its application. Chemom Intell Lab Syst 2(1):61–77 (Proceedings of the Multivariate Statistical Workshop for Geologists and Geochemists)MathSciNetCrossRef Mellinger M (1987) Correspondence analysis: the method and its application. Chemom Intell Lab Syst 2(1):61–77 (Proceedings of the Multivariate Statistical Workshop for Geologists and Geochemists)MathSciNetCrossRef
go back to reference Newman MEJ (2013) Spectral methods for community detection and graph partitioning. Phys Rev E 88(4):042822CrossRef Newman MEJ (2013) Spectral methods for community detection and graph partitioning. Phys Rev E 88(4):042822CrossRef
go back to reference Newman MEJ (2016) Equivalence between modularity optimization and maximum likelihood methods for community detection. Phys Rev E 94(5):052315CrossRef Newman MEJ (2016) Equivalence between modularity optimization and maximum likelihood methods for community detection. Phys Rev E 94(5):052315CrossRef
go back to reference Nishisato S, Nishisato S (1980) Analysis of categorical data: dual scaling and its applications. University of Toronto Press, TorontoCrossRef Nishisato S, Nishisato S (1980) Analysis of categorical data: dual scaling and its applications. University of Toronto Press, TorontoCrossRef
go back to reference Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: online learning of social representations. In: Macskassy SA, Perlich C, Leskovec J, Wang W, Ghani R (eds) The 20th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’14, New York, NY, USA. ACM, pp 701–710. https://doi.org/10.1145/2623330.2623732 Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: online learning of social representations. In: Macskassy SA, Perlich C, Leskovec J, Wang W, Ghani R (eds) The 20th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’14, New York, NY, USA. ACM, pp 701–710. https://​doi.​org/​10.​1145/​2623330.​2623732
go back to reference Rosenberg A, Hirschberg J (2007) V-measure: a conditional entropy-based external cluster evaluation measure. In: Eisner J (ed) EMNLP-CoNLL 2007, proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning, June 28–30, 2007, Prague, Czech Republic. ACL, pp 410–420 Rosenberg A, Hirschberg J (2007) V-measure: a conditional entropy-based external cluster evaluation measure. In: Eisner J (ed) EMNLP-CoNLL 2007, proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning, June 28–30, 2007, Prague, Czech Republic. ACL, pp 410–420
go back to reference Sarkar S, Dong A (2011) Community detection in graphs using singular value decomposition. Phys Rev E 83(4):046114CrossRef Sarkar S, Dong A (2011) Community detection in graphs using singular value decomposition. Phys Rev E 83(4):046114CrossRef
go back to reference Tanaka Y (1979) Review of the methods of quantification. Environ Health Perspect 32:113–123CrossRef Tanaka Y (1979) Review of the methods of quantification. Environ Health Perspect 32:113–123CrossRef
go back to reference Vu T, Parker DS (2017) Mining community structure with node embeddings. In: Kaya M, Erdoǧan Ö, Rokne J (eds) Social data mining and analysis to prediction and community detection. Lecture notes in social networks. Springer, Berlin, pp 123–140CrossRef Vu T, Parker DS (2017) Mining community structure with node embeddings. In: Kaya M, Erdoǧan Ö, Rokne J (eds) Social data mining and analysis to prediction and community detection. Lecture notes in social networks. Springer, Berlin, pp 123–140CrossRef
go back to reference Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Krishnapuram B, Shah M, Smola AJ, Aggarwal CC, Shen D, Rastogi R (eds) Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, San Francisco, CA, USA, August 13–17, 2016. ACM, pp 1225–1234. https://doi.org/10.1145/2939672.2939753 Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Krishnapuram B, Shah M, Smola AJ, Aggarwal CC, Shen D, Rastogi R (eds) Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, San Francisco, CA, USA, August 13–17, 2016. ACM, pp 1225–1234. https://​doi.​org/​10.​1145/​2939672.​2939753
go back to reference Yelland PM (2010) An introduction to correspondence analysis. Math J 12:1–23 Yelland PM (2010) An introduction to correspondence analysis. Math J 12:1–23
Metadata
Title
Correspondence analysis-based network clustering and importance of degenerate solutions unification of spectral clustering and modularity maximization
Author
Masaomi Kimura
Publication date
01-12-2020
Publisher
Springer Vienna
Published in
Social Network Analysis and Mining / Issue 1/2020
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-020-00686-z

Premium Partner