Molecular interaction networks have emerged as a powerful data source for answering a plethora of biological questions ranging from how cells make decisions to how species evolve. The availability of such data from multiple organisms allows for their analysis from an evolutionary perspective. Indeed, work has emerged recently on network alignment, ancestral network reconstruction, and phylogenetic inference based on networks. In this talk, I will address two central problems in the area of evolutionary analysis of molecular interaction networks. The first concerns correcting genetic distances derived from observed differences between networks. We devise a distance correction method, and show how its estimates are more accurate than those based on observed distances. The second problem concerns the reconstruction of an ancestral network of two extant networks in a probabilistic (rather than parsimonious) framework under the duplication-mutation with complementarity (DMC) model of network evolution. We demonstrate the accuracy of reconstructions achieved by our algorithm on synthetic and biological data.