Title: GoT-WAVE: Temporal network alignment using graphlet-orbit transitions,
Abstract: Global pairwise network alignment (GPNA) aims to find a one-to-one node
mapping between two networks that identifies conserved network regions. GPNA
algorithms optimize node conservation (NC) and edge conservation (EC). NC
quantifies topological similarity between nodes. Graphlet-based degree vectors
(GDVs) are a state-of-the-art topological NC measure. Dynamic GDVs (DGDVs) were
used as a dynamic NC measure within the first-ever algorithms for GPNA of
temporal networks: DynaMAGNA++ and DynaWAVE. The latter is superior for larger
networks. We recently developed a different graphlet-based measure of temporal
node similarity, graphlet-orbit transitions (GoTs). Here, we use GoTs instead
of DGDVs as a new dynamic NC measure within DynaWAVE, resulting in a new
approach, GoT-WAVE.
On synthetic networks, GoT-WAVE improves DynaWAVE's accuracy by 25% and speed
by 64%. On real networks, when optimizing only dynamic NC, each method is
superior ~50% of the time. While DynaWAVE benefits more from also optimizing
dynamic EC, only GoT-WAVE can support directed edges. Hence, GoT-WAVE is a
promising new temporal GPNA algorithm, which efficiently optimizes dynamic NC.
Future work on better incorporating dynamic EC may yield further improvements.