GoT-WAVE is a new method for temporal global pairwise network alignment (GPNA). GPNA aims to find a one-to-one node mapping between two networks that identifies conserved network regions. An example of an application domain where GoT-WAVE is useful is computational biology, where GoT-WAVE can be used for alignment of molecular networks that evolve over time. Other domains include social networks, computer vision, ontology matching, etc.
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. We recently developed a different graphlet-based measure of temporal node similarity, graphlet-orbit transitions (GoTs).
GoT-WAVE, like DynaWAVE, is an extension of WAVE. While WAVE, DynaWAVE and GoT-WAVE optimize EC as well as NC across the aligned networks, WAVE conserves static edges and similarity between static node neighborhoods while DynaWAVE and GoT-WAVE conserve dynamic edges (events) and temporal node features. GoT-WAVE optimizes NC in terms of their GoTs, while DynaWAVE optimizes NC in terms of their DGDVS. Compared against DynaWAVE, GoT-WAVE works better (in terms of accuracy) on networks with high snapshot overlap and is faster on sparser networks (we use g-tries to boost speed).
David Aparício may be contacted via email at daparicio [at] dcc [dot] fc [dot] up [dot] pt.