  Network alignment consists of finding a structure-preserving correspondence
between the nodes of two correlated, but not necessarily identical, networks.
This problem finds applications in a wide variety of fields, from the alignment
of proteins in computational biology, to the de-anonymization of social
networks, as well as recognition tasks in computer vision.
  In this work we introduce SPECTRE, a scalable algorithm that uses spectral
centrality measures and percolation techniques. Unlike most network alignment
algorithms, SPECTRE requires no seeds (i.e., pairs of nodes identified
beforehand), which in many cases are expensive, or impossible, to obtain.
Instead, SPECTRE generates an initial noisy seed set via spectral centrality
measures which is then used to robustly grow a network alignment via bootstrap
percolation techniques. We show that, while this seed set may contain a
majority of incorrect pairs, SPECTRE is still able to obtain a high-quality
alignment. Through extensive numerical simulations, we show that SPECTRE allows
for fast run times and high accuracy on large synthetic and real-world
networks, even those which do not exhibit a high correlation.
