ELRUNA: Elimination Rule-based Network Alignment

摘要: Networks model a variety of complex phenomena across different domains. In many applications, one the most essential tasks is to align two or more networks infer similarities between cross-network vertices and discover potential node-level correspondence. this paper, we propose ELRUNA (Elimination rule-based network alignment), novel alignment algorithm that relies exclusively on underlying graph structure. Under guidance elimination rules defined, computes similarity pair iteratively by accumulating their selected neighbors. The resulting matrix then used permutation encodes final vertices. addition algorithm, also improve performance local search, commonly post-processing step for solving problem, introducing selection method RAWSEM (Randomwalk based method) propagation levels mismatching (defined in paper) networks. key idea pass initial throughout entire random-walk fashion. Through extensive numerical experiments real networks, demonstrate significantly outperforms state-of-the-art methods terms accuracy under lower comparable running time. Moreover, robust perturbations such it can maintain close optimal objective value high level noise added original Finally, proposed further quality with less number iterations compared naive search method.