SoCS Conference 2018 Conference Paper
Focused SANA: Speeding Up Network Alignment
- Ilia Leybovich
- Rami Puzis
- Roni Stern
- Maor Reuben
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