Focused SANA: Speeding Up Network Alignment

Network Alignment (NA) is a generalization of the graph isomorphism problem for non-isomorphic graphs, where the goal is to find a node mapping as close as possible to isomorphism. Recent successful NA algorithms follow a search-based approach, such as simulated annealing. We propose to speed up search-based NA algorithms by pruning the search-space based on heuristic rules derived from the topological features of the aligned nodes. We define several desirable properties of such pruning rules, analyze them theoretically, and propose a pruning rule based on nodes

Authors

• Ilia Leybovich
• Rami Puzis
• Roni Stern
• Maor Reuben

Keywords

No keywords are indexed for this paper.