Credible seed identification for large-scale structural network alignment

Chenxu Wang, Yang Wang, Zhiyuan Zhao, Dong Qin, Xiapu Luo, Tao Qin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Structural network alignment utilizes the topological structure information to find correspondences between nodes of two networks. Researchers have proposed a line of useful algorithms which usually require a prior mapping of seeds acting as landmark points to align the rest nodes. Several seed-free algorithms are developed to solve the cold-start problem. However, existing approaches suffer high computational cost and low reliability, limiting their applications to large-scale network alignment. Moreover, there is a lack of useful metrics to quantify the credibility of seed mappings. To address these issues, we propose a credible seed identification framework and develop a metric to assess the reliability of a mapping. To tackle the cold-start problem, we employ graph embedding techniques to represent nodes by structural feature vectors in a latent space. We then leverage point set registration algorithms to match nodes algebraically and obtain an initial mapping of nodes. Besides, we propose a heuristic algorithm to improve the credibility of the initial mapping by filtering out mismatched node pairs. To tackle the computational problem in large-scale network alignment, we propose a divide-and-conquer scheme to divide large networks into smaller ones and then match them individually. It significantly improves the recall of mapping results. Finally, we conduct extensive experiments to evaluate the effectiveness and efficiency of our new approach. The results illustrate that the proposed method outperforms the state-of-the-art approaches in terms of both effectiveness and efficiency.

Original languageEnglish
Pages (from-to)1744-1776
Number of pages33
JournalData Mining and Knowledge Discovery
Volume34
Issue number6
DOIs
Publication statusPublished - 1 Nov 2020

Keywords

  • Edge consistency
  • Mapping credibility
  • Network alignment
  • Seed identification

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications

Cite this