Metrics for graph comparison: A practitioner's guide

Area of Science:

• Graph theory and network analysis
• Data science and machine learning
• Computational network science

Background:

• Graph structure comparison is vital in diverse fields like neuroscience, cybersecurity, and bioinformatics.
• Understanding graph topologies (e.g., communities, hubs) reveals network generation and function.
• Existing graph distance measures lack comparative studies on their efficacy across structural scales.

Purpose of the Study:

• To conduct a comparative study of common graph metrics and distance measures.
• To evaluate their ability to discern topological features in random and real-world networks.
• To provide a multi-scale perspective on graph structure analysis and guide the selection of distance measures.

Main Methods:

• Comparison of commonly used graph metrics and distance measures.
• Analysis of topological features in random graph models and empirical networks.
• Investigation of global and local structural effects on distance measures across multiple scales.

Main Results:

• Demonstrated the varying abilities of different distance measures to identify common graph topologies.
• Revealed the impact of global and local structures on distance measure sensitivity.
• Established a multi-scale framework for understanding graph structure comparison.

Conclusions:

• Recommendations are provided for selecting appropriate graph distance measures based on multi-scale analysis.
• The study highlights the importance of considering scale when comparing graph structures.
• Introduced NetComp, a Python library for implementing and applying these graph distance measures.