Graph comparison via the nonbacktracking spectrum

Author: 

Mellor, A
Grusovin, A

Publication Date: 

23 May 2019

Journal: 

Physical Review E

Last Updated: 

2019-06-14T21:45:31.12+01:00

Issue: 

5

Volume: 

99

DOI: 

10.1103/physreve.99.052309

abstract: 

The comparison of graphs is a vitally important, yet difficult task which
arises across a number of diverse research areas including biological and
social networks. There have been a number of approaches to define graph
distance however often these are not metrics (rendering standard data-mining
techniques infeasible), or are computationally infeasible for large graphs. In
this work we define a new metric based on the spectrum of the non-backtracking
graph operator and show that it can not only be used to compare graphs
generated through different mechanisms, but can reliably compare graphs of
varying size. We observe that the family of Watts-Strogatz graphs lie on a
manifold in the non-backtracking spectral embedding and show how this metric
can be used in a standard classification problem of empirical graphs.

Symplectic id: 

954520

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article