Many applications involve evolving networked data, e.g. in social networks, biological networks and evolutionary networks. Often, one can only observe the current state of the network, and has only very limited or no access to earlier states of the network, e.g. in evolutionary biology we can sequence the genomes of the individuals living today but the amount of well-preserved fossils is rather limited. Still, an interesting task is to learn a model of evolution. In a number of domains, specific approach exist, often making a lot of simplifying assumptions. In this presentation, I will review the challenges for addressing this problem and some existing approaches, and then discuss some preliminary ongoing work towards addressing this problem relying on assymptotic properties of random networks.