Networks represent a fundamental medium for spreading and diffusion of various types of behavior, information, rumors and diseases [27] . A contagion appears at some node of a network and then spreads like an epidemic from node to node over the edges of Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. the underlying network. For example, in case of information diffusion, the contagion represents a piece of information [16, 18] and infection events correspond to times when nodes mention or copy the information from one of their neighbors in the network. Similarly, we can think about the spread of a new type of behavior or an action, e.g., purchasing a new cellphone [15] , or the propagation of a contagious disease over the edges of the underlying social network [6] .
In the context of network diffusion, we often observe the temporal traces of diffusion while the pathways over which contagion spreads remain hidden. In other words, we observe the times when each node gets infected by the contagion, but the edges of the network that gave rise to the diffusion remain unobservable. For example, we can often measure and observe the time when people decide to adopt a new behavior while we do not explicitly observe which neighbor in the social network influenced them to do so. In case of information diffusion, we often observe people (or media sites) talking about a new piece of information without explicitly observing the path it took in the information diffusion network to reach the particular node of interest. And, epidemiologists often observe when a person gets sick but usually cannot tell who infected her. In all these examples, one can observe the infection events themselves while not knowing over which edges of the network the contagions spread. Therefore, one of the fundamental research problems in the context of network diffusion is inferring the structure of networks over which various types of contagions spread [10] . Moreover, many times networks over which contagions diffuse are not static but change over time. Depending on the type of contagion, the time of the day, or death of the existing and birth of new nodes, the underlying network may dynamically change and shift over time.
In recent years, several network inference algorithms have been developed [9, 10, 12, 20, 24, 30] . Some approaches infer only the network structure [10, 30] , while others infer not only the network structure but also the strength or the average latency of every edge in the network [9, 20] . However, to the best of our knowledge, previous work has always assumed networks to be static and contagion pathways to be constant over time. However, in most cases, networks are dynamic, and contagion pathways change over time, depending upon the contagions that propagate through them [22, 28] . For example, a blog can increase its popularity abruptly after one of its posts turns viral, this may create new edges in the information transmission network and so the content the blog produces in the future will likely spread to larger parts of the network. Similarly, at any given time a particular unexpected event may occur and a topic or piece of news may become very popular for a limited period of time. This again will lead to different emerging and vanishing information pathways, and thus to a time-varying underlying Model Edge (j, i) transmission likelihood f(t i |t j ; α j,i ) network. In order to better understand these temporal changes, one needs to reconstruct the time-varying structure and underlying temporal dynamics of these networks and then study the information pathways of real-world events, topics or content.
Our approach to time-varying network inference. In this paper we investigate the problem of inferring dynamic networks based on information diffusion data. We assume there is an unobserved dynamic network that changes over time, while we observe the node infection times of many different contagions spreading over the edges of the network. The task then is to infer the edges and the dynamics of the underlying network. We develop an efficient on-line dynamic network inference algorithm, INFOPATH, that allows us to infer daily networks of information diffusion between online media sites over a one year period using more than 179 million different contagions diffusing over the underlying media network. We model diffusion processes as discrete networks of fully continuous temporal processes occurring at different rates building on our previous work [9, 11] . Our model allows information to propagate at different rates across different edges by adopting a datadriven approach, where only the recorded temporal diffusion events are used. The model considers the information which propagates through the network due only to diffusion, while ignoring any external sources [22] . However, our original diffusion model considered only static networks [9] . Here, we generalize the model and develop a new inference method to support dynamic networks. Our time-varying network inference algorithm, INFOPATH, uses stochastic gradient [26] to provide estimates of the time-varying structure and temporal dynamics of the inferred network. The framework enables us to study the temporal evolution of information pathways in the online media space.
We apply the INFOPATH algorithm to synthetic as well as real Web information propagation data. We study 179 million different information cascades spreading among 3.3 million blog and news media sites over a one year period, from March 2011 till February 2012. 1 Results on synthetic data show INFOPATH is able to track changes in the topology of dynamic networks and provides accurate on-line estimates of the time-varying transmission rates of the edges of the network. INFOPATH is also robust across network topologies, and temporal trends of edge transmission dynamics.
Experiments on large-scale real news and social media data lead to interesting insights and findings. For example, we find that the information pathways over which general recurrent topics propagate remain more stable over time, while unexpected events lead to dramatically changing information pathways. Clusters of mainstream news and blogs often emerge and vanish in a matter of days, and our on-line algorithm is able to uncover such structures. News events that involve large-scale social movements, as the Libyan civil war, Egypt's revolution or Syria's uprise, result in a greater increase in information transfer among blogs than among main-stream media. Perhaps surprisingly, the amount of mainstream media and blogs among the most influential nodes for most topics or news events are comparable. However, we find that growing numbers of influential blogs on some topics or news events are often temporally correlated with large-scale social movements (e.g., the Occupy Wall Street movement in Sept-Nov 2011).
Further related work. Previous methods for inferring diffusion networks [9, 10, 12, 20] also use a generative probabilistic model for modeling cascading processes over networks. NETINF [10] and MULTITREE [12] infer the network connectivity using submodular optimization. NETRATE [9] and CONNIE [20] infer not only the network connectivity but also transmission rates of infection or prior probabilities of infection using convex optimization. Moreover, there have been also attempts to model information diffusion without assuming the existence of an underlying network [33, 32] .
However, to the best of our knowledge, all previous approaches to network inference assume the network and the underlying dynamics of the edges to be constant, i.e., the network structure and the transmission rates of each edge do not change over time. Therefore, they consider the pathways over which information propagates to be time-invariant. The main contribution of this paper is to combine stochastic gradient and the diffusion model introduced in [9] to develop an efficient on-line network inference algorithm that provides time-varying estimates of the edges of a network and the transmission rates of each edge. This allows us to detect how information pathways emerge and vanish over time, and identify when nodes produce highly viral content.
The remainder of the paper is organized as follows: in Sec. 2, we revisit the model of diffusion and state the dynamic network inference problem. Section 3 describes the proposed time-varying network inference method, called INFOPATH. Section 4 evaluates INFOPATH quantitatively and qualitatively using synthetic and real diffusion data. We conclude with a discussion of results in Section 5.
In this section, we build on our fully continuous time model of diffusion [9, 11] . We start by briefly describing the generative model for the observed data. We then revisit how to compute the likelihood of a cascade using the model and state the continuous time network inference problem for both static and dynamic networks. Across the section, we explicitly point out which assumptions of the original model need to be extended in order to support dynamic networks.
Observed data. For now let's consider a single static directed network. Over the edges of the network multiple contagions propagate. As the contagion spreads from infected to non-infected nodes over the edges of the network the contagion creates a cascade. For each contagion c, we observe a cascade t c , which is simply a record of observed node infection times during a time window of length T c . In an information propagation setting, each cascade corresponds to a different piece of information and the infection time of a node is simply the time when the node first mentioned the piece of information c.
Cascade is a N-dimensional vector t c := (t c 1 , . . . ,t c N ) recording the times when each of N nodes got infected by the contagion c: t c k ∈ [t 0 ,t 0 + T c ] ∪ {∞}, where t 0 is the infection time of the first node. Generally contagions do not infect all the nodes of the network, symbol ∞ is used for nodes that were not infected by the contagion c during the observation window [t 0 ,t 0 + T c ]. Contagions often propagate simultaneously [21, 25] Table 2 : Contagion transmission models for the three edge transmission likelihoods: Exponential, Power-law and Rayleigh.
work but we assume each contagion to propagate independently of each other. Given a set of node infection times of many different contagions, our goal is to infer the underlying dynamic network over which contagions propagated. We apply the Maximum Likelihood principle in order to infer the network that most likely generated the observed data. We proceed by assuming a static network and describe the generative model of information diffusion. We then generalize the model to dynamic networks.
Pairwise transmission likelihood. The first step in modeling diffusion dynamics is to consider pairwise node interaction. For every pair of nodes ( j, i), we define a pairwise transmission rate α j,i which models how frequently information spreads from node j to node i; the strength of an edge ( j, i). We pay attention to the rather general case of heterogeneous pairwise transmission rates, i.e., infections can occur at different transmission rates over different edges of the network. As α j,i → 0 the expected transmission time from node j to node i becomes arbitrarily long. In contrast with the original model [9] , we will later allow transmission rates α j,i to change over time. In particular, we will allow the transmission rates α j,i to change across cascades but not within a cascade. Allowing edge transmission rates to dynamically increase and decay over time will enable us to infer time-varying diffusion networks.
Next, we define f (t i |t j ; α j,i ) to be the conditional likelihood of transmission between node j and node i and assume it depends on the infection times (t j ,t i ) and the edge transmission rate α j,i . We allow information to only propagate forward in time, i.e., node j that has been infected at time t j may infect node i at time t i only if t j < t i , otherwise f (t i |t j , α j,i ) = 0. The shape of the conditional likelihood of transmission may depend on the particular setting (information, influence, diseases, etc.) in which propagation takes place. In some scenarios, it may be possible to estimate a non-parametric likelihood while in others, expert knowledge may be used to decide upon a parametric model. For simplicity, we consider three well-known parametric models of edge transmission rates: exponential, power-law, and Rayleigh, defined in Table 1 . Exponential and power-law likelihoods have been used in modeling information propagation in social and information networks [9, 10, 11, 12, 20] , while Rayleigh has been used in previous work in disease spread in epidemiology [31] . In all three models, as α j,i → 0, the likelihood of infection tends to zero.
We recall some additional standard notation [14] that we will use in the remainder of the section. Given some node j, infected at time t j , we define the survival function of edge j → i as
dt is the cumulative transmission density function, computed from the transmission likelihood. Finally, the hazard function, or instantaneous infection rate, of edge j → i is the ratio H(t i |t j ; α j,i ) = f (t i |t j ; α j,i )/ S(t i |t j ; α j,i ). We derive the log survival and hazard functions for the three edge transmission models in Table 2 .
Likelihood of a cascade. Consider some node i in a directed network. Node i can get infected by any of its parents (i.e., nodes pointing to i). Once infected, node i can then also spread the contagion to its children (i.e., nodes i points to). As in the independent cascade model [13] , we assume that node gets infected once the first parent infects it (i.e., a node can get infected only once). Then, the likelihood of infection of node i at time t i given a collection of previously infected nodes (t 1 , . . . ,t N |t k ≤ t i ) results from summing over the likelihoods of the mutually disjoint events that each node is the first parent that generated the infection event of our node i:
If we assume that infections are conditionally independent given the parents of the infected nodes, the likelihood of the infections in a cascade is:
where t ≤T c denotes the vector of infected nodes in the cascade up to T c . Removing the condition k = j makes the product independent of j,
.
The fact that some nodes are not infected during the observation window is also informative. We therefore add multiplicative survival terms to Eq. 3 and rearrange with hazard functions:
Perhaps surprisingly, our continuous time model of diffusion is a particular case of Aalen's additive regression model, frequently used in survival theory analysis [3] . In Aalen's model, the hazard function, or instantaneous infection rate, of node i is parametrized
is a vector that accounts for the effect of a collection of observable covariates s(t) and α i,0 (t) is a baseline. It is easy to show that the hazard function of node i at time t i for the three pairwise transmission models: exponential, power-law and Rayleigh, has the following form:
Algorithm 1 INFOPATH: the dynamic network inference algorithm Require:
where α i = (α 1,i , . . . , α N,i ) accounts for the effect of a collection of observable covariates s i (t i ;t 1 , . . . ,t N \ t i ), the covariates depend on the pairwise transmission model (exponential, power-law or Rayleigh) and the previously infected nodes, and the baseline is zero.
Dynamic network inference problem. Given a static network with constant edge transmission rates α j,i , the network inference problem reduces to solving a maximum likelihood problem over set of recorded cascades C [9] :
where A := {α j,i | i, j = 1, . . . , n, i = j} are the edge transmission rates we aim to infer. The edges of the network are those pairs of nodes with transmission rates α j,i > 0. Now we generalize the network inference problem to dynamic networks with edge transmission rates α j,i (t) that may change over time. To this aim, at any given time t, we solve a maximum weighted likelihood problem over the set of recorded cascades by time t, C t = {t 1 , . . . , t |C t | }:
where w c (t) ≥ 0 is a weight that penalizes the importance of cascade c based on how old it is at time t and A(t) := {α j,i (t) | i, j = 1, . . . , n, i = j} are the variables. The intuition here is that diffusion network smoothly changes over time and that recent cascades have higher importance in determining current network structure than old cascades. Thus, at any point in time, we can solve the above optimization problem to obtain the structure of the diffusion network at that particular time. Next, we show how to efficiently solve the above optimization problem for all time points t.
The problem defined by equation Eq. 8 is convex for the three transmission models we consider. Therefore we can aim to find the unique optimal solution at any given time point t:
). Given log-concave survival functions and concave hazard functions in the parameter(s) of the pairwise transmission likelihoods, the network inference problem defined by equation Eq. 8 is convex in A.
Stochastic gradient (SG) methods have been shown to be extremely successful for taking advantage of the structure exhibited by the optimization problem stated in Eq. 8. They have received increasing attention in the machine learning literature [4, 5, 7, 8, 29] . Although many optimization methods based on stochastic gradient descent have been proposed, we have found that in practice the basic projected stochastic gradient method [26] works well for our problem. Other more sophisticated methods, like the stochastic average gradient [29] or incremental average gradient [7] do not offer a significant advantage. Therefore, we proceed with the basic stochastic gradient method in the remainder of the paper.
Projected Stochastic Gradient. The projected stochastic gradient method [26] uses iterations of the form:
where ∇ α j,i L c k (·) is the gradient of the log-likelihood L c (·) with respect to the edge transmission rate α j,i , γ k is a step-size, (z) + = max(0, z), and cascade c k is sampled (with replacement) from C t . The gradients for all three edge transmission models are given in Table 2 .
Note that instead of using all historic data and then explicitly penalizing each cascade by a different weighting factor w c (t), we use a different, more scalable approach. We sample cascades with replacement, where the probability of a cascade being sampled decays with the age of the cascade. This way recent cascades get sampled more often and thus implicitly hold higher importance when inferring the network. In practice, we achieve a significant speed up by using this approach. Moreover, in our dynamic network inference problem, the edge transmission rates usually vary smoothly. This means that stochastic gradient descent is a perfect method as we can use the inferred network from the previous time step as initialization for the inference procedure in the current time step. We find that setting the starting point α 0 j,i of each edge transmission rate α j,i to the last outputted estimate of the transmission rate allows us to further speed up the algorithm.
Importantly, in each iteration k of the projected stochastic gradient method, we only need to compute the gradients ∇ α j,i L c k (A k ) for edges ( j, i) such that node j has been infected in cascade c k , and the iteration cost and convergence rate are independent of |C| [5, 23] . Rigorous theoretical analysis of convergence turns out to be a challenging problem which we leave for future work. However, we point out that standard analyses [26] typically assume the gradients ∇ A L c (A k ) to be either bounded above by a constant M, where ||∇ A L c (A)|| ≤ M, or Lipschitz-continuous with constant L,
In our case, these conditions are violated if at any iteration k, there is a node i infected in cascade c k such that H(t c k i |t c k j ; α k−1 j,i ) = 0 ∀ j : t c k j < t c k i , i.e., node i has no parents that explain the infection at t c k i , and the objective function is positively unbounded. In practice, we obtain a good performance and avoid such scenario by bounding below each feasible transmission rate, α j,i ≥ ε. An edge transmission rate α j,i is feasible if there is at least one cascade in which both node j and i get infected. When outputting the final solution, we simply omit edges with transmission rates ε.
Aging edges. Suppose we solve the dynamic network inference problem for a given time t using the projected SG method. In each iteration k, we only update edge transmission rate α k j,i if node j has been infected in cascade c k . Now, suppose a few edge transmission rates α 0 j,i are greater than zero for a given node j, i.e., their last outputted estimates before t have been positive. Then, if node j turns to be infected in many sampled cascades at time t but it never transmits information to any of its neighbors i in the future, the edge transmission rates α k j,i will eventually converge to zero for large k. However, if node j is never infected for any of the future cascades, then none of edge transmission rates α j,i will be updated, and they will remain positive. So, if node j is never infected in subsequent future cascades, the transmission rates α j,i will remain positive for- ever. However, we would like these unused edges ( j, i) to decay and eventually vanish, or equivalently the transmission rates α j,i to converge to zero. To achieve this, we multiply transmission rates of unused edges by aging factor ρ every time we solve the dynamic network inference problem. We use ρ = 0.95 in all experiments.
Cascade sampling. In Eq. 9, instead of sampling cascades uniformly at random and explicitly penalizing each cascade by a different weighting factor w c (t), we achieve a significant speed up by sampling cascades using a sampling procedure that penalizes old cascades and considers w c (t) = 1 for all cascades. There are many possible sampling schemes. In practice, and for simplicity, we use windowed uniform sampling or windowed exponential sampling. Windowed means that when solving the network inference problem for time t, we only sample (uniformly or exponentially) cascades that have started in a sampling time window (t − T, T ). Here, we find an an important tradeoff. The shorter is the sampling time window T in the stochastic gradient descend, the quicker our algorithm is tracking changes in the edge transmission rates. However, short sampling time window results in less reliable estimates because of sampling from a smaller universe of distinct cascades. Therefore, in order to be able to track changes quickly, we would need to observe many cascades over time.
We evaluate the performance of INFOPATH on time-varying synthetic networks that mimic the structure of real networks as well as on a dataset of more than 179 million information cascades extracted from 300 million blogs and news articles from 3.3 million media sites over a period of one year, from March 2011 till February 2012. All the data, code and additional results are available at the supporting website [1] .
The goal of the experiments with synthetic data is to understand how temporal changes in a network affect the performance of our algorithm. We aim to detect not only when an edge appears (i.e., its transmission rate becomes > 0) or disappears (i.e., its transmission rate becomes 0) but also provide instantaneous transmission rate estimates that track the true edge transmission rates over time.
Experimental setup. First, we generate synthetic networks using Kronecker graph models of directed real-world networks [17] . For all our experiments, we consider two different Kronecker networks, both with 1,024 nodes and 2,048 edges: A core-periphery Kronecker network with parameter matrix [0.9, 0.5; 0.5, 0.3]) and a hierarchical Kronecker network with parameters [0.9, 0.1; 0.1, 0.9]. The next step is to make each edge to follow a particular edge transmission rate evolution pattern. Our goal later will be to recover the network as well as the evolution of the transmission rate of each individual edge.
We consider five edge evolution patterns: Slab, Square, Chainsaw, Hump and constant (see Figure 1 ). Slab and Hump patterns model outgoing connections of sites that become popular for a short period of time. Square and Chainsaw patterns model incoming connections to sites that perform updates periodically at specific times of the day or days of the week. Constant pattern represents connections between sites that interact at any time and during a long period of time, usually large media sites. We consider Chainsaw, Hump and Continuous to be examples of Type I pattern, without discontinuities, and Slab and Square to be examples of Type II pattern, with discontinuities.
We assign to each edge in the network an evolution pattern chosen uniformly at random from the set of the above 5 patterns. Then, we generate transmission rate values α * j,i (t) for each edge according to its chosen evolution pattern. The evolving edge transmission rate α * j,i (t) models how quickly information spreads from one node to another. Finally, we generate 1,000 information cascades per time step. For each cascade we randomly pick the cascade initiator node.
Given the node infection times from the recorded cascades, our goal then is to find the true edges of the network and for each edge discover its transmission rate evolution pattern. In other words, inferring how each edge transmission rate α(t) evolves over time. Figure 1 shows the true and inferred edge transmission rates for four different edges, each with a different evolution pattern: Slab, Square, Chainsaw and Hump. Observe that INFOPATH is able to track the evolving edge transmission rates over time for all evolution patterns. INFOPATH gives near perfect performance when edge transmission rate evolves continuously (Chainsaw, Hump). Interestingly, even when the edge transmission rate evolves discontinuously (Slab, Square), INFOPATH manages to track it.
We evaluate the INFOPATH method quantitatively by computing four different measures for every time step: Precision, Recall and Accuracy of inferred edges as well as the Mean Squared Error (MSE) in the edge transmission rate. Precision at time t is the fraction of edges in the inferred networkĜ(t) present in the true network G * (t). Recall at time t is the fraction of edges of the true network G * (t) present in the inferred network G(t). And accuracy at time t is defined as
, where α * (t) is the true transmission rate at time t,α(t) is the estimated transmission rate at time t, and I(α(t)) = 1 if α(t) > 0 and I(α(t)) = 0 otherwise. Inferred networks with no edges or only false edges would have zero accuracy. Last, Mean Squared Error (MSE) at time t is defined as E ||α * (t) −α(t)|| 2 , where α * (t) is the true edge transmission rate at time t andα(t) is the estimated transmission rate. Figure 2 shows Precision, Recall, Accuracy, and MSE over time for the time-varying core-periphery Kronecker network with exponential edge transmission model, and hierarchical Kronecker network with Rayleigh edge transmission model. Observe that the performance of our method is stable across time, and as mentioned before, continuous evolution patterns are easier to track and estimate than discontinuous ones.
Accuracy vs. running time in static networks. Our stochastic gradient descend based method, INFOPATH, can be also used to speed-up inference of static networks. In such scenario, stochastic gradient descend processes cascades in a random round-robin fashion. Here, we compare INFOPATH to the state of the art methods for inference of static networks: NETINF [10] and NETRATE [9] . First, we compare the methods by computing the accuracy against running time. Second, we compare INFOPATH to NETRATE in terms of mean squared error of the estimated transmission rates against the running time. We omit NETINF from this last comparison since it only infers the network structure (and no edge transmission rates). For the sake of fairness in the running time comparison we implemented all methods in C++. Our C++ implementation of NETRATE is much faster than the public Matlab implementation. 
The emergence of specific information pathways often depends on the information content of the news that is propagating [22, 28] . For example, a real world event may occur for a limited period of time and thus news related to the event spread quicker and to larger parts of the network around such time period. At any given time, there are many different real world events, topics, and content that propagates through the Web, leading to different emerging and vanishing information pathways, and thus an underlying time-varying network. In order to better understand these temporal changes, we aim to reconstruct time-varying networks and the information pathways for particular real world events and topics.
Dataset description. We experiment with more than 300 million blog posts and news articles collected from 3.3 million websites over a period of one year, from March 2011 till February 2012. We trace the flow of information using memes [16] . Memes are a short textual phrases (like, "lipstick on a pig") that travel through the Web. We consider each meme m as a separate information cascade c m . Since all documents which contain memes are time-stamped, a cascade c m is simply a record of times when sites first mentioned meme m. We extracted more than 179 million memes, longer than four words. Out of these, 34 million distinct memes appeared at least twice, resulting in 34 million different information cascades.
Experimental setup. Our aim is to consider sites that actively spread memes over the Web. We achieve this by selecting top 5,000 sites in terms of the number of memes they mentioned. Moreover, we are interested in inferring dynamic networks related to particular topics or events. So, we assume we are also given a keyword query Q related to the event/topic of interest. When inferring a network for a given query Q, we only consider documents (and the memes they mention) that include keywords Q. Then, we build information cascades using only those memes and apply the IN-FOPATH algorithm to infer the edges and evolving edge transmission rates. The edge transmission rates explain the propagation of information related to a given topic or real world event Q. For each query Q we infer one network per day. Table 3 summarizes Implementation and scalability. We developed an efficient distributed implementation of our INFOPATH algorithm in C++ based on the network analysis library SNAP [2] . We deployed the implementation in a cluster with 1,000 CPU cores and 6 TB of RAM.
With this setup, we considered 38 different topics/events Q. For each topic, we inferred a time-varying network with a daily temporal resolution for a period of one year, from March 2011 to February 2012. Each network has thousands of nodes and is based on hundreds of thousands of cascades. Inferring 38 different time-varying networks took less than 4 hours on our cluster. Note that this is equivalent to solving Eq. 8 more than 13,000 times (38 x 365) for millions of pairwise transmission rates. We also tested our algorithm on larger datasets. For example, for "Occupy Wall Street movement", we were able to infer a 43,415-node time-varying network over a period of 18 months, from January 2011 to June 2012, using 1,381,793 information cascades.
Visualizing the information pathways. Figure 4 plots diffusion networks for three different 2011 world events: Fukushima nuclear disaster, UK royal wedding, and civil uprise in Syria. Each network is shown at three different time points. Red nodes represent mainstream media sites, and blue nodes represent blogs [16] . Based on the figure, we draw several interesting observations. Most often, information propagates through a core-periphery network structure. Such structure emerges by few central media sites and blogs driving the adoption of memes across the Web [10] . However, the network structure often changes dramatically over time, and we find clusters that emerge and vanish in short periods of time. For example, the information networks for Syria's uprise illustrated in Figures 4(g-h) , do not have any clear clustering structure. However, on December 2, 2011 (Figure 4 (i)) a cluster suddenly emerges in the network. Further investigation reveals that the cluster is composed of UK news sites and blogs that discuss recently implemented EU sanctions against Syria. Generally, it is common to observe sudden formation of clusters of sites from specific geographical areas. This is specially noticeable in the information network for Fukushima's disaster, in Figures 4(a-c) . Such clusters often form due to language boundaries, since such boundaries prevent memes to flow across countries or continents. Moreover, we often observe that such clusters are caused by a common external event [22] , like in the case of UK discussion on EU sanctions against Syria. Inferred dynamic networks can thus be used to investigate the flow of information as well as to detect external events that cause sudden perturbations to the diffusion network structure.
Evolution of edge transmission rates. Next, we aim to study the evolution of links among different types of sites. We label the nodes in our network as mainstream media and blog, and compute the number of links between different types of sites over time. Figure 5 gives the results for several inferred diffusion networks for different topics and world events. We note several interesting patterns.
The connectivity changes tend to reflect the amount of attention that a news event or a topic triggers over time. Unexpected news events, like the sex scandal of the director of the International Monetary Fund Strauss-Kahn on May 14, 2011 in Fig. 5(g) or the death of British singer Amy Winehouse on July 23, 2011 in Fig. 5(a) , result in a dramatic increase in the number of edges over a short period of time. More general topics, like the NBA in Fig. 5(e) , result in a network with more stable connectivity over time. Certain types of news are sometimes spreading earlier among blogs than mainstream media. This is especially the case for population wide events like the Fukushima nuclear disaster, civil war in Libya and civil uprise in Syria ( Fig. 5(b, c, h) . However, it happens more frequently that the largest amount of links are mainstream media-to-mainstream media and the fewest links point from blogs to mainstream media. These results are intuitive and consistent with previous work [10, 16] that observed most often information flows from mainstream media to blogs (and rarely the other way around). However, as we see here for population level events and social movements (like, in case of the civil unrest in the Middle East) social media plays crucial role in information dissemination and organization of civil movements.
Evolution of node centrality. Having studied the dynamics of edges in the network we now move towards investigating the network centrality of blogs and mainstream media sites over time for different topics and world events. To measure network centrality of node S in the network at time t, we first compute shortest path length from S to any other node R in the network. Then centrality of node S is defined as ∑ R 1/d(S, R), where d(S, R) is the shortest path length from S to R (if R is not reachable from S then d(S, R) = ∞). For networks with core-periphery structure, nodes with high centrality are typically located in the "central" core of the network. Figure 6 plots the percentage of blogs among the top 100 most central sites over time for eight different topics/events of 2011. Perhaps surprisingly, we observe there is a about the same number of mainstream media and blogs in the top-100 most central nodes for most networks -the number of blogs in the top-100 does not typically decreases below 30% or increases over 70%. For some topics, mainstream media are always more central (e.g., baseball and NBA in Figures 6(a, b) ). In contrast, for other topics, blogs dominate mainstream media over a significant amounts of time (e.g., Gaddafi in Fig. 6(c) ). Centrality of mainstream media and blogs can be relatively constant ( Fig. 6(a,b) ) or more time-varying ( Fig. 6(c,h) ). We find that a significant rise in the number of central blogs is often temporally correlated with an increasing social unrest (e.g., the Occupy Wall Street movement in Sept-Nov 2011 in Fig. 6(f) ).
Accuracy on real data. So far, we have used memes to trace the flow of information over the Web and have made several qualitative observations about the structure and dynamics of information pathways in online media. We now proceed and attempt to also quantitatively evaluate INFOPATH on real data. In case of real data the ground-truth information diffusion network is impossible to obtain. However, we can use the temporal dynamics of hyperlinks created between news sites as a proxy for real information flow. Thus, by observing the times when sites create hyperlinks, our goal is to infer the 'targets' of the links (i.e., infer the hyperlink network from the hyperlinks times). We proceed as follows. First, we discretize the time in days, we generate one network G * (t) per day t, in which we add an edge (u, v) if a document on a site u linked to a document on a site v within the last day. Then, we build a set of hyperlink cascades. A hyperlink cascade c h starts when a site publishes a piece of information and then other sites use hyper-links to refer to it. Since all our documents/posts are time stamped, we can trace the hyperlinks in the reverse direction and obtain information cascades. We extracted almost 0.5 million hyperlink cascades from 3.3 million websites from July 2011 till December 2012. Our aim is to use the hyperlink cascades to infer the time-varying network G * (t). We then evaluate how many edges INFOPATH estimates correctly by computing Accuracy, Precision and Recall for each day. Figure 7 shows Precision, Recall, and Accuracy over time for a time-varying hyperlink network with 11,461 nodes and 19,915 edges created over time, using 495,655 hyperlink cascades from July 2011 to December 2011. We assume an exponential edge transmission model. We observe weekly periodicity and the overall encouraging performance of around 0.4 to 0.5 for all three performance metrics.
All previous network inference algorithms have assumed diffusion networks to be static. Therefore, they have considered the pathways over which information propagates to be static over time. In contrast, we developed an algorithm for time-varying network inference, INFOPATH. Our algorithm provides on-line time-varying estimates of the edges of the network as well as the dynamic edge transmission rates, which allows us to detect how information pathways emerge and vanish over time.
We evaluated our algorithm on synthetic data and demonstrated that INFOPATH successfully tracks changes in the topology of dynamic networks, provides accurate on-line estimates of the timevarying edge transmission rates and is also robust across network topologies, edge transmission models and patterns of evolution of edge transmission rates.
We also run INFOPATH on real data and investigated how real networks and information pathways evolve over time. We found that information pathways over which general recurrent topics propagate remain relatively stable across time. In contrast, major realworld events lead to dramatic changes and shifts in the information pathways. We observed that clusters of mainstream news and We split the sites into mainstream media and blogs and count the links among these two node types. blogs often emergence and vanish in matter of days. We discovered that there is an early greater increase in information transfer among blogs than among mainstream media for news involving general population and social unrest, such as the Libyan civil war, Egyptian revolution, Syria's uprise and the Occupy Wall Street movement. Our work also opens various venues for future work. For example, rigorous theoretical analysis of the convergence of our stochastic gradient descent method would provide further insights for its performance. Moreover, we notice that many times the changes in the inferred network structure could be attributed to sudden external real-world events. This opens two interesting questions. How can diffusion network inference be combined with methods for detecting external influence in networks [22] ? And also, how can dynamic network inference be extended for detecting unexpected real-world events based on a stream of documents? Last, many times not only information but also sentiment attached to a piece of information spreads through the network [19] . It would be interesting to think about inference of signed networks, where a positive/negative valence of an edge models sentiment relationship between a pair of nodes. Overall, such methods would allow us to improve our understanding of the current landscape of news coverage, the role that news media plays in framing the discussion of important topics, and the evolving ecosystem that news media occupies. 