IntroductionRelated workMethodsSmooth changes in parametersStructural changes in parametersMultiple observationsChoosing tuning parametersSimulation studiesApplications to real dataSenate voting records dataGene regulatory networks of Drosophila melanogasterSome properties of the algorithmsDiscussionAcknowledgmentsReferencesAuthor's AddressesThe Annals of Applied Statistics2010, Vol. 4, No. 1, 94–123DOI: 10.1214/09-AOAS308© Institute of Mathematical Statistics, 2010ESTIMATING TIME-VARYING NETWORKSBY MLADEN KOLAR,LE SONG1,AMR AHMED AND ERIC P. XING2Carnegie Mellon UniversityStochastic networks are a plausible representation of the relational infor-mation among entities in dynamic systems such as living cells or social com-munities. While there is a rich literature in estimating a static or temporallyinvariant network from observation data, little has been done toward estimat-ing time-varying networks from time series of entity attributes. In this paperwe present two new machine learning methods for estimating time-varyingnetworks, which both build on a temporally smoothed l1-regularized logis-tic regression formalism that can be cast as a standard convex-optimizationproblem and solved efficiently using generic solvers scalable to large net-works. We report promising results on recovering simulated time-varyingnetworks. For real data sets, we reverse engineer the latent sequence of tem-porally rewiring political networks between Senators from the US Senate vot-ing records and the latent evolving regulatory networks underlying 588 genesacross the life cycle of Drosophila melanogaster from the microarray timecourse.1. Introduction. In many problems arising from natural, social, and infor-mation sciences, it is often necessary to analyze a large quantity of random vari-ables interconnected by a complex dependency network, such as the expressionsof genes in a genome, or the activities of individuals in a community. Real-timeanalysis of such networks is important for understanding and predicting the orga-nizational processes, modeling information diffusion, detecting vulnerability, andassessing the potential impact of interventions in various natural and built systems.It is not unusual for network data to be large, dynamic, heterogeneous, noisy, in-complete, or even unobservable. Each of these characteristics adds a degree ofcomplexity to the interpretation and analysis of networks. In this paper we presenta new methodology and analysis that address a particular aspect of dynamic net-work analysis: how can one reverse engineer networks that are latent, and topolog-ically evolving over time, from time series of nodal attributes.While there is a rich and growing literature on modeling time-invariant net-works, much less has been done toward modeling dynamic networks that areReceived December 2008; revised August 2009.1Supported by a Ray and Stephenie Lane Research Fellowship.2Supported by Grant ONR N000140910758, NSF DBI-0640543, NSF DBI-0546594, NSF IIS-0713379 and an Alfred P. Sloan Research Fellowship. Corresponding author.Key words and phrases. Time-varying networks, semi-parametric estimation, graphical models,Markov random fields, structure learning, high-dimensional statistics, total-variation regularization,kernel smoothing.94ESTIMATING TIME-VARYING NETWORKS 95rewiring over time. We refer to these time or condition specific circuitries as time-varying networks, which are ubiquitous in various complex systems. Consider thefollowing two real world problems:• Inferring gene regulatory networks. Over the course of organismal development,there may exist multiple biological “themes” that dynamically determine thefunctions of each gene and their regulations. As a result, the regulatory networksat each time point are context-dependent and can undergo systematic rewiringrather than being invariant over time [Luscombe et al. (2004)]. An intriguingand unsolved problem facing biologists is as follows: given a set of microarraymeasurements over the expression levels of p genes, obtained at n (n  p)different time points during the developmental stages of an organism, how doyou reverse engineer the time-varying regulatory circuitry among genes?• Understanding stock market. In a finance setting we have values of differentstocks at each time point. Suppose, for simplicity, that we only measure whetherthe value of a particular stock is going up or down. We would like to find theunderlying transient relational patterns between different stocks from these mea-surements and get insight into how these patterns change over time.In both of the above-described problems, the data-generating process and latentrelational structure between a set of entities change over time. A key technicalhurdle preventing us from an in-depth investigation of the mechanisms underlyingthese complex systems is the unavailability of serial snapshots of the time-varyingnetworks underlying these systems. For example, for a realistic biological system,it is impossible to experimentally determine time-specific networks for a series oftime points based on current technologies such as two-hybrid or ChIP-chip sys-tems. Usually, only time series measurements, such as microarray, stock price,etc., of the activity of the nodal entities, but not their linkage status, are available.Our goal is to recover the latent time-varying networks with temporal resolutionup to every single time point based on time series measurements. Most of the ex-isting work on structure estimation assumes that the data generating process istime-invariant and that the relational structure is fixed, which may not be a suit-able assumption for the described problems. The focus of this paper is to estimatedynamic network structure from a time series of entity attributes.The Markov Random Fields (MRF) have been a widely studied model for therelational structure over a fixed set of entities [Wainwright and Jordan (2008);Getoor and Taskar (2007)]. Let G = (V , E) be a graph with the vertex set V andthe edge set E. A node u ∈ V represents an entity (e.g., a stock, a gene, or a per-son) and an edge (u, v) ∈E represents a relationship (e.g., correlation, friendship,or influence). Each node in the vertex set V ={1,...,p} corresponds to an ele-ment of a p-dimensional random vector X = (X1,...,Xp)of nodal states, whoseprobability distribution is indexed by θ ∈ . Under a MRF, the nodal states are as-sumed to be discrete, that is, X