Date Added: Jan 2011
As graph-structured datasets become commonplace, there is increasing need for efficient ways of analyzing such datasets. These analyses include conservation, alignment, differentiation, and discrimination, among others. When defined on general graphs, these problems are considerably harder than their well-studied counterparts on sets and sequences. This is a direct consequence of the underlying isomorphism associated with many of these problems. In this paper, the authors study the problem of global alignment of large sparse graphs. Specifically, they investigate efficient methods for computing pairwise topological similarity between nodes in two networks (or within the same network).