Title: SPECTRE: Seedless Network Alignment via Spectral Centralities,
Abstract: Network alignment consists of finding a correspondence between the nodes of
two networks. From aligning proteins in computational biology, to
de-anonymization of social networks, to recognition tasks in computer vision,
this problem has applications in many diverse areas. The current approaches to
network alignment mostly focus on the case where prior information is
available, either in the form of a seed set of correctly-matched nodes or
attributes on the nodes and/or edges. Moreover, those approaches which assume
no such prior information tend to be computationally expensive and do not scale
to large-scale networks. However, many real-world networks are very large in
size, and prior information can be expensive, if not impossible, to obtain. In
this paper we introduce SPECTRE, a scalable, accurate algorithm able to solve
the network alignment problem with no prior information. SPECTRE makes use of
spectral centrality measures and percolation techniques to robustly align nodes
across networks, even if those networks exhibit only moderate correlation.
Through extensive numerical experiments, we show that SPECTRE is able to
recover high-accuracy alignments on both synthetic and real-world networks, and
outperforms other algorithms in the seedless case.