Co-evolving patterns in temporal networks of varying evolution

Biological networks describe the interactions among molecules. Unlike static biological networks at a single time point, temporal networks capture how the network topology evolves over time in response to external stimuli or internal variations. We say that two temporal networks have co-evolving subnetworks if the topologies of these subnetworks remain similar to each other as the networks evolve over time. Existing methods for identifying co-evolving patterns make the strong and unrealistic assumption that the two network topologies evolve at the same rate. In this paper, we consider the generalized problem, where each network may evolve at different rates and the rates of evolution may change over time. Moreover, the two networks may have network topologies available for different number of time points. Existing methods fail to solve this problem as they rely on the strong prior assumption. We develop an efficient algorithm, Tempo++, for identifying coevolving subnetworks within two given temporal networks. Unlike existing methods, Tempo++ does not assume that the networks have same and uniform evolutionary rates. We experimentally demonstrate that Tempo++ scales efficiently and accurately on both synthetic and real datasets. Our results on E. coli time resolved response to five different environmental stress conditions demonstrate that Tempo++ identifies genes specific to those conditions that conforms to well-known studies in the literature. Statistical significance of alignments found by Tempo++ outperforms existing strategies. Moreover, Tempo++ correctly identifies co-evolving networks with similar stress response compared to networks with different stress response.