Analysis of Complex Networks

11.2 Brief Overview of Network Mapping Methods

This section first gives a brief review of network mapping and then introduces previous work on identifying and filling pathway holes.

The first class in network mapping is comprised of graph and subgraph isomorphisms. An intuitive enumeration algorithm to obtain isomorphisms of pattern graph P to text graph T is to generate a state-space representation tree that represents all possible mappings between the nodes of the two graphs and to check whether each generated mapping in the tree is a good alignment. In a tree with a vertex size of , a vertex represents a pair of matched nodes; a path from a root down to a leaf represents a mapping between the two graphs. Any path across k levels in the tree represents a possible subgraph isomorphism between P and T.

For circumventing the hardness, part of the computation is filtered by using more selective feasibility rules to cut the state search space [35]. Another part is performed in an intensive preprocessing step so that the alignment process based on subgraph isomorphisms runs in polynomial time when one ignores the exponential preprocessing time. The first examples of this approach were presented by Shasha, Wang, and Giugno [37], Yan, Yuz, and Hany [40], Yan and Han [36], Giugno and Shasha [38], Messmer [33], and Bunke [32], which convert the database of graphs individually into DFS a ...