Network Archaeology: Uncovering Ancient Networks from Present-day Interactions

Abstract

Often questions arise about old or extinct networks. What proteins interacted in a long-extinct ancestor species of yeast? Who were the central players in the Last.fm social network 3 years ago? Our ability to answer such questions has been limited by the unavailability of past versions of networks. To overcome these limitations, we propose several algorithms for reconstructing a network's history of growth given only the network as it exists today and a generative model by which the network is believed to have evolved. Our likelihood-based method finds a probable previous state of the network by reversing the forward growth model. This approach retains node identities so that the history of individual nodes can be tracked. We apply these algorithms to uncover older, non-extant biological and social networks believed to have grown via several models, including duplication-mutation with complementarity, forest fire, and preferential attachment. Through experiments on both synthetic and real-world data, we find that our algorithms can estimate node arrival times, identify anchor nodes from which new nodes copy links, and can reveal significant features of networks that have long since disappeared.

16 pages, 10 figures

References in corpus (2)

• Quantifying social group evolution
• Kronecker Graphs: An Approach to Modeling Networks

Cited by in corpus (14)

• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• The evolutionary dynamics of protein-protein interaction networks inferred from the reconstruction of ancient networks
• Phase transition in the recoverability of network history
• Choosing among alternative histories of a tree
• A New Computationally Efficient Measure of Topological Redundancy of Biological and Social Networks
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Inference for growing trees
• Network interpolation
• Belief propagation for permutations, rankings, and partial orders
• Prediction Of Arrival Of Nodes In A Scale Free Network
• Reconstruction of Network Evolutionary History from Extant Network Topology and Duplication History
• Influence of homology and node-age on the growth of protein-protein interaction networks
• Degree centrality and root finding in growing random networks
• Maximum likelihood estimation for mechanistic network models