IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0099966.html
   My bibliography  Save this article

Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks

Author

Listed:
  • Raghvendra Mall
  • Rocco Langone
  • Johan A K Suykens

Abstract

Kernel spectral clustering corresponds to a weighted kernel principal component analysis problem in a constrained optimization framework. The primal formulation leads to an eigen-decomposition of a centered Laplacian matrix at the dual level. The dual formulation allows to build a model on a representative subgraph of the large scale network in the training phase and the model parameters are estimated in the validation stage. The KSC model has a powerful out-of-sample extension property which allows cluster affiliation for the unseen nodes of the big data network. In this paper we exploit the structure of the projections in the eigenspace during the validation stage to automatically determine a set of increasing distance thresholds. We use these distance thresholds in the test phase to obtain multiple levels of hierarchy for the large scale network. The hierarchical structure in the network is determined in a bottom-up fashion. We empirically showcase that real-world networks have multilevel hierarchical organization which cannot be detected efficiently by several state-of-the-art large scale hierarchical community detection techniques like the Louvain, OSLOM and Infomap methods. We show that a major advantage of our proposed approach is the ability to locate good quality clusters at both the finer and coarser levels of hierarchy using internal cluster quality metrics on 7 real-life networks.

Suggested Citation

  • Raghvendra Mall & Rocco Langone & Johan A K Suykens, 2014. "Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks," PLOS ONE, Public Library of Science, vol. 9(6), pages 1-18, June.
  • Handle: RePEc:plo:pone00:0099966
    DOI: 10.1371/journal.pone.0099966
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0099966
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0099966&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0099966?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Andrea Lancichinetti & Filippo Radicchi & José J Ramasco & Santo Fortunato, 2011. "Finding Statistically Significant Communities in Networks," PLOS ONE, Public Library of Science, vol. 6(4), pages 1-18, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wu, Jianshe & Zhang, Long & Li, Yong & Jiao, Yang, 2016. "Partition signed social networks via clustering dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 568-582.
    2. Gregory, Steve, 2012. "Ordered community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2752-2763.
    3. Wu, Zhihao & Lin, Youfang & Wan, Huaiyu & Tian, Shengfeng & Hu, Keyun, 2012. "Efficient overlapping community detection in huge real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(7), pages 2475-2490.
    4. Greg Morrison & L Mahadevan, 2012. "Discovering Communities through Friendship," PLOS ONE, Public Library of Science, vol. 7(7), pages 1-9, July.
    5. Jiang, Yawen & Jia, Caiyan & Yu, Jian, 2013. "An efficient community detection method based on rank centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2182-2194.
    6. Dugué, Nicolas & Perez, Anthony, 2022. "Direction matters in complex networks: A theoretical and applied study for greedy modularity optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 603(C).
    7. Badie, Reza & Aleahmad, Abolfazl & Asadpour, Masoud & Rahgozar, Maseud, 2013. "An efficient agent-based algorithm for overlapping community detection using nodes’ closeness," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(20), pages 5231-5247.
    8. Wang, Yuyao & Bu, Zhan & Yang, Huan & Li, Hui-Jia & Cao, Jie, 2021. "An effective and scalable overlapping community detection approach: Integrating social identity model and game theory," Applied Mathematics and Computation, Elsevier, vol. 390(C).
    9. Fu, Xianghua & Liu, Liandong & Wang, Chao, 2013. "Detection of community overlap according to belief propagation and conflict," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(4), pages 941-952.
    10. Dafne E. van Kuppevelt & Rena Bakhshi & Eelke M. Heemskerk & Frank W. Takes, 2022. "Community membership consistency applied to corporate board interlock networks," Journal of Computational Social Science, Springer, vol. 5(1), pages 841-860, May.
    11. Jiang, Zhongzhou & Liu, Jing & Wang, Shuai, 2016. "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 293-302.
    12. Kyle F Davis & Paolo D'Odorico & Francesco Laio & Luca Ridolfi, 2013. "Global Spatio-Temporal Patterns in Human Migration: A Complex Network Perspective," PLOS ONE, Public Library of Science, vol. 8(1), pages 1-8, January.
    13. Rodica Ioana Lung & Camelia Chira & Anca Andreica, 2014. "Game Theory and Extremal Optimization for Community Detection in Complex Dynamic Networks," PLOS ONE, Public Library of Science, vol. 9(2), pages 1-11, February.
    14. Fu, Jingcheng & Wu, Jianliang & Liu, Chuanjian & Xu, Jin, 2016. "Leaders in communities of real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 428-441.
    15. Lan Huang & Guishen Wang & Yan Wang & Enrico Blanzieri & Chao Su, 2013. "Link Clustering with Extended Link Similarity and EQ Evaluation Division," PLOS ONE, Public Library of Science, vol. 8(6), pages 1-18, June.
    16. Zhang, Hongli & Gao, Yang & Zhang, Yue, 2018. "Overlapping communities from dense disjoint and high total degree clusters," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 286-298.
    17. Li Wang & Jiang Wang & Yuanjun Bi & Weili Wu & Wen Xu & Biao Lian, 2014. "Noise-tolerance community detection and evolution in dynamic social networks," Journal of Combinatorial Optimization, Springer, vol. 28(3), pages 600-612, October.
    18. Stefano Bianchini & Moritz Muller & Pierre Pelletier & Kevin Wirtz, 2021. "Global health science leverages established collaboration network to fight COVID-19," Papers 2102.00298, arXiv.org.
    19. Navakas, Robertas & Džiugys, Algis & Peters, Bernhard, 2014. "A community-detection based approach to identification of inhomogeneities in granular matter," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 407(C), pages 312-331.
    20. Frank Havemann & Jochen Gläser & Michael Heinz & Alexander Struck, 2012. "Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches," PLOS ONE, Public Library of Science, vol. 7(3), pages 1-12, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0099966. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.