
218
Complex Networks: An Algorithmic Perspective
MaWIsh attempts to identify conserved multi-protein complexes by searching for
clique-like structures. These structures are expected to contain at least one hub node
with a high degree. Having found a hub in a clique-like structure, it greedily extends
the subgraphs. The time complexity of MaWIsh is O(n
1
n
2
) where n
1
and n
2
are the
sizes of the two graphs being compared. The main disadvantage of MaWIsh is that it
looks for a specific topological property (cliques). MaWIsh was implemented to find
network alignments of the PPI networks of yeast, fly and the worm successfully.
10.5.2.3 IsoRank
IsoRank was introduced ...