Credible seed identification for large-scale structural network alignment
- PDF / 2,368,315 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 3 Downloads / 158 Views
Credible seed identification for large-scale structural network alignment Chenxu Wang1,2 Tao Qin2
· Yang Wang1 · Zhiyuan Zhao1 · Dong Qin1 · Xiapu Luo3 ·
Received: 28 June 2019 / Accepted: 18 June 2020 © The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature 2020
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.
Responsible editor: Shuiwang Ji. This work is extended from a conference paper published in ICDCS 2018.
B
Chenxu Wang [email protected]
1
School of Software Engineering, Xi’an Jiaotong University, Xi’an, China
2
MoE Key Lab of INNS, Xi’an Jiaotong University, Xi’an, China
3
Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China
123
C. Wang et al.
Keywords Network alignment · Seed identification · Edge consistency · Mapping credibility
1 Introduction Structural network alignment aims at finding correspondences between nodes of two networks based on the topological structure (Kollias et al. 2012; Bayati et al. 2009). Relevant techniques have a broad range of applications from biological network alignment (Zaslavskiy et al. 2009; Yang and Sze 2007; Kuchaiev et al. 2010; Alada˘g and Erten 2013; Vijayan et al. 2015), computer vision (Gold and Rangarajan 1996; Luo and Hancock 2001; Robles-Kelly and Hancock 2003; Conte et al. 2004; Emms et al. 2007), data management (Melnik et al. 2002; Hu et al. 2008), to social network deanonymization (Backstrom et al. 2007; Narayanan and Shmati
Data Loading...
