Multilevel hierarchical kernel spectral clustering for real-life large scale complex networks.

Area of Science:

• Network analysis
• Machine learning
• Data mining

Background:

• Kernel spectral clustering (KSC) is framed as a constrained optimization problem related to weighted kernel principal component analysis.
• The dual formulation of KSC enables model building on subgraphs and parameter estimation during validation, offering an out-of-sample extension for large networks.

Purpose of the Study:

• To exploit KSC's eigenspace projections for automatic determination of distance thresholds.
• To develop a novel hierarchical community detection method for large-scale networks.
• To demonstrate the capability of detecting multilevel hierarchical structures in real-world networks.

Main Methods:

• Utilizing the dual formulation of kernel spectral clustering for model training on representative subgraphs.
• Exploiting eigenspace projection structures to derive distance thresholds for hierarchical analysis.
• Employing a bottom-up approach to construct hierarchical network structures.

Main Results:

• Successfully determined multilevel hierarchical organization in real-world networks.
• Demonstrated superior performance compared to Louvain, OSLOM, and Infomap methods in detecting complex hierarchies.
• Achieved high-quality cluster detection at both fine and coarse hierarchical levels using internal metrics.

Conclusions:

• The proposed KSC-based approach effectively reveals multilevel network hierarchies, offering an advantage over existing methods.
• This technique provides a robust framework for analyzing complex network structures at multiple scales.
• The method's ability to identify good quality clusters across different hierarchical levels highlights its practical utility.