Distance metric learning for complex networks: towards size-independent comparison of network structures

Area of Science:

• Network Science
• Graph Theory
• Computational Intelligence

Background:

• Real-world complex networks exhibit intricate topological properties like community structures and heavy-tailed degree distributions.
• Network analysis heavily relies on comparing network topologies for tasks such as classification, clustering, model selection, and anomaly detection.
• Existing graph comparison methods, particularly isomorphism-based ones, are computationally expensive and unsuitable for networks of different sizes.

Purpose of the Study:

• To develop an effective similarity metric for comparing complex networks of potentially different sizes.
• To address the limitations of traditional graph comparison methods in terms of speed and applicability to networks of varying scales.
• To leverage intelligent algorithms for feature integration, selection, and weighting in network similarity assessment.

Main Methods:

• A novel approach utilizing genetic algorithms (GAs) for feature engineering in network comparison.
• Integration, selection, and weighting of diverse network topological features using GAs.
• Development of a similarity measure based on the optimized feature set derived from GAs.

Main Results:

• The proposed genetic algorithm-based similarity metric demonstrates superior performance compared to state-of-the-art methods.
• The metric effectively captures structural similarities between complex networks, even those of different sizes.
• Evaluation criteria confirm the enhanced accuracy and efficiency of the developed network similarity measure.

Conclusions:

• Genetic algorithms provide a powerful framework for developing advanced network similarity metrics.
• The proposed method offers a robust and efficient solution for comparing complex network structures.
• This work advances the field of network analysis by providing a more effective tool for topological comparison.