Network similarity

How to measure Similarity (or distance) between networks? What if two networks have different size or density?

In considering Graph isomorphism, we are interested in whether two given networks can be mapped to each other perfectly. Graph matching or Network alignment deals with the problem of aligning two networks as much as possible when these two networks are not necessarily isomorphic. Graph matching is the term mostly used in computer science and Network alignment is used in biological contexts (e.g., aligning two Protein protein interaction networks from two species). Graph kernels are similarity functions used for Kernel method.

There are many ways to think about similarity. We can think about macroscopic properties, such as degree distribution, average path length, etc., or mesoscopic structure¹, or microscopic properties. Recently, there have also been embedding-based approaches.

• https://link.springer.com/chapter/10.1007/978-3-540-69812-8_51
• Bagrow et al., Portraits of Complex Networks, Bagrow & Bollt, An information-theoretic, all-scales approach to comparing networks
• Koutra et al., DELTACON: A Principled Massive-Graph Similarity Function
• Shimada et al., Graph distance for complex networks
• Identifying network structure similarity using spectral graph theory
• Torres et al., Non-backtracking cycles: length spectrum theory and graph mining applications
• SimGNN: A Neural Network Approach to Fast Graph Similarity Computation

Brain network

• Comparing brains by matching connectivity profiles