Information diffusion in interconnected heterogeneous networks

In this paper, we are interested in modeling the diffusion of information in a multilayer network using thermodynamic diffusion approach. State of each agent is viewed as a topic mixture represented by a distribution over multiple topics. We have observed and learned diffusion-related thermodynamical patterns in the training data set, and we have used the estimated diffusion structure to predict the future states of the agents. A priori knowledge of a fraction of the state of all agents changes the problem to be a Kalman predictor problem that refines the predicted system state using the error in estimation of the agents. A real world Twitter data set is then used to evaluate and validate our information diffusion model.


INTRODUCTION
Different topics are discussed/diffused in social networks and because of the distinct dynamics of these diffusions, agents in the social networks are affected in different extents. The temporal and spatial dynamics of diffusion have been studied through sequences of activation nodes and observed as spreading cascades in a network [1].
The information diffusion process models can be classified into three major groups, probabilistic models, thermodynamic models, and counting models. NETINF [2], NE-TRATE [3] and INFOPATH [4] are the probabilistic models which infer the underlying diffusion network among information sources using consecutive hit times of the nodes by a specific cascade. The main idea behind the thermodynamic models [5,6,7,8] is that heat will propagate from a warmer region to a colder region or gas will move from the region with higher density to the region with lower density. Modeling the information as heat or gas, we can write the rate at which information is changing in agent i as: dft' = D Lj A(i, j)(' I/Jj -' I/Ji )-Where ' 1/J; (t) is the state of the i th agent at time t, D is the diffusion constant which reflects the amount of information passing from an agent to another agent in a small interval of time, and A( i, j) is the i, j element of adjacency matrix. The counting models [9] form counting processes to find the number of nodes in each group of susceptible or infected nodes. SIS [ 10] and SIR [ 11] models are two of the well-known ones in this group.
One central challenge in modeling information diffusion is to understand the structure of the cascades; the existence of unknown external influence factors and unclear graph connections obscures this query. In this paper, we have for the first time modeled the simple diffusion on a general multilayer network and applied the model to publication networks and social media data.
The multilayer network connectivity structure has been proposed and studied in [12,13,14,15,16], in particular, a two-layer network has been studied in [7] under the Laplacian dynamics. However, the information flow following a Laplacian process on a multilayer network in its most general form has yet to be studied. A multilayer network (illustrated in Fig. I) takes into consideration additional connection possibilities when the true connections for the agents are uncertain. For example, social media such as biogs consist of a set of documents generated by bloggers over time; these documents may share some topical similarities in spite of the different sources they are generated from. It is possible to structure the document similarities into the relational property as a network of documents. Then one can further associate this layer of connection with the connection of bloggers ( e.g., according to following-follower connection). This leads to a multilayer network model where information diffuse both within a single layer and across the inter-layers. The additional paths due to the multilayer structure will diffuse the information at a secondary degree, specifically, an absence of a direct connection between two bloggers may be reestablished by counting the topical similarities between the documents they are associated with. We will refer to the resulting network from a multilayer construction as an interconnected network of heterogeneous nodes.
In a community-like network setting with common interest, such as a network of professors with their publications, online forum community, we have observed diffusion related thermodynamical patterns. It turns out that the simple diffusion model on the interconnected network structure is very effective in predicting the future state of the agents.  The paper is organized as follows: We propose our new approach in Section 2, and present substantiating experimental results in Section 3. We finally provide the concluding remarks in Section 4.

THE PROPOSED METHOD
In closed systems, all changes in the states of agents are a result of interaction of the agents in the network. In a single layer network, a diffusion process based on heat equation has been studied in [5 , 6, 7, 8). Independent of the nodes in a multilayer network being agents or documents, we generalize the single layer diffusion process to: dX -= -.C.X. dt (I) Where X is a N x T matrix, N being the number of nodes in the multilayer network, and each row of X is storing a Tdimensional state vector for each node . .C. is a N x N supra-Laplacian matrix defined in proposition(!).

Proposition 1
We can generally write the supra-Laplacian matrix of an M layer multiplex network with N nodes in each layer as Eqn. (2). Where .C.L is the supra-Laplacian matrix of the intra-layer connectivity and .C. 1 is the supra-Laplacian matrix of the inter-layer connectivity. .C.L may be in turn, written as direct sum of the Laplacian matrices of the independent intra-layer connectivities: Proof of proposition (1) can be found in the extended version of the paper [17].
Much of the existing work in information diffusion models have a limited scope (of agents, documents, parameters) when predicting the future state of the nodes. More specifically, agent states may be varied by external sources which are not captured in the network, or by some agent actions which may even to some extent, conflict with the model prediction.
Considering an interconnected network with supra-Laplacian matrix .C., to address this additional auxiliary input, we are further generalizing Eqn. (I) to an open system model as follows: vectors with components as independent standard Brownian motions of variances u i and :E is N x T matrix, and each row shows the u i vector for agent i. Inspired by the Ornstein-Uhlenbeck (0.U.) process [18], Eqn. (6) describes the velocity of the topical-state of the nodes as a Brownian motion in presence of friction. In other words, to describe the uncertainty due to external effects, we proceed to view the whole system as a massive Brownian particle. The drift term (first term in right-hand side of Eqn. (6)), however, moves the velocity from a martingale state of u idB( t) towards a consensus (captured by the drift term). Solution of the differential equation in Eqn. (6), can be expressed as: given the states of nodes at time t 0 we can predict the states at time t 1 , t 1 > t 0 as follows: Where e.C(s-t, +to) is a matrix exponential and itself is a N x N matrix.
Our proposed learning procedure will evaluate the diffusion constants in the supra-Laplacian matrix C as well as the :E matrix. To that end, we proceed to minimize the Frobenius norm of the difference between X and it's predict X, resulting from, Solving this optimization problem helps us decompose the predicted matrix into two main components on the right-hand side of Eqn. (7), the first term representing the interactions in the network, while the second quantifying the uncertainty which results from auxiliary inputs into the system.

Diffusion Network Estimation (Leaming the Supra-Laplacian Matrix)
The supra-Laplacian matrix C which we use in Eqn. (6) for state prediction, is a result of the network connectivity (refer to Eqn. (2)). In practice, hidden connections are pervasive, introducing uncertainty in the prediction, which are causing the information diffusion to require more than the predefined, explicit connections from the network. To that end, consider observations ofX(t) overt E [O, t 1 J, denote x(t) := vec(X(t)), the vectorization of X(t) to obtain a vector differential system in order to learn the supra-Laplacian matrix C of Eqn. We consider the simple cost function J = !t:r E, where E = x -i, and hence for the estimation A we have A = ' Y (x -i)xr (derivative of J with respect to x) , where the estimation i(t + 1) = cAx(t) , and~/ > 0 is chosen appropriately as the scaling gain. In optimization iterations, the estimated value of A at ith iteration is as follows: We use A. 0 =Ir @ (-C), the graph Laplacian of the explicit following-follower network (as initialization). The learned A may, however, not be exactly structured as Ir @ (-C), due to dependence of topics in the state space, as well as the nonlinearity and non-homogeneity of the diffusion. The resulting error E shall be considered for the estimation of the noise in the Kalman-Bucy filter as discussed next.

A Refined Prediction: Kalman-Bucy Filtering
In prediction applications, the actual states of some of the nodes are sometimes known, and we want to predict those of all remaining nodes. An example of this may be seen in social networks, where state of the hub nodes, such as famous people or users with less restrictive privacy policies are known to the public, and one is interested in predicting the state of other less accessible users. Having partial knowledge of the states of a fraction of the nodes in the network, changes the state prediction problem to a Kalman predictor problem, and helps to refine the predicted states using a Kalman filter. We propose a Kalman-Bucy filter as the optimal linear predictor for our system, and we write the observation equation as y(t) = (Ir @H)x(t) +v(t), with Has a diagonal indicator matrix with 1 in all the observed entries, and O in all other entries. A having been learned (see above Section), Kalamn-Bucy equations may be written as: (10) where 1l = Ir @ Hand the noises w(t) and v(t) are zeromean white (temporally) processes, i.e, E(w(t)w(sf) = By considering small time intervals on discretization of the linear continues time system ( c5t = 1 ), one can write the state equation as x(t + 1) = Fx(t) + w(t), where F =I+ A.
Having Eqn. (10) and x(t + 1) = Fx(t) + w(t) as the state and observation equations respectively, we can predict and refine the predicted states of the nodes using Algorithm ( 1 ). The "learning phase" of the Algorithm (1) is estimating the supra-Laplacian matrix A (see above Section). The second phase of the algorithm, is refining the estimated state of the nodes. Note that Rt is the covariance of the observational error, and Xt 2 1t, denotes the linear prediction of x at time t 2 given observations up to and including time t 1 • The state covariance Ilt satisfies the Riccati equation: • A
The designed algorithm shows the discrete time, state update of the Kalman predictor. The estimated states of the available nodes, 1li(t), are compared with the state of the available nodes, y(t) , as measurements observed over time, to evaluate the extent of statistical noise and other inaccuracies in predicting phase. Fig. (2a) shows the prediction based on a network of 79 professors. A three-layer network is formed with the first layer showing if the two professors have ever published in the same venue or not. The second layer being the research group membership of these professors and the third layer showing the similarity network between the papers published by these professors (extracted by LDA [19] topic modeling of the abstract of the papers with dimension I 0). State of the agents are the I 0-dimensional topical vectors which are the mean of the topical representation of the documents produced by the agents . Over time more documents are getting added and the topical state of the agent are changing. The error measure used in all the experiments is the Frobenius norm of the difference of the estimated state of the nodes and ground truth state of the nodes normalized by the Frobenius norm of the ground truth matrix. As may be seen in Fig. (2a), the prediction method based on a three-layer network achieves a lower error than the prediction based on a single-layer network. Note, the single-layer network does not help in predicting the topical states of the agents. The reason is that there are only 79 agents in this experiment and the co-authorship network between the agents is not particularly suited to predict the future state of the agents. Fig. (2b) is an experiment based on 5000 Twitter users. The first layer is a network among users and the second layer is a network between eight Hashtags used in June 2009. The Hashtags are as follows: #jobs, #spymaster, #neda, #l40mafia, #tcot, #musicmonday, #lranelection, #iremember showing how much these Hashtags are similar to each other by counting and normalizing the number of times they have appeared in the same tweet. The average prediction improvement achieved by the two-layer network is about 13 percent. The prediction by first estimating the Laplacian matrix, has about 15 percent improvement over the single layer prediction method. agents in the network respectively. As may be seen in the figures , the prediction error based on the estimated Laplacian matrix yields a lower error than fully trusting the connectivity structure in the network. This as expected, is due to static connectivity network (usually demonstrates the physical or online relation among the agents), falling short on affecting the actual underlying diffusion structure on the network. Having a prior partial knowledge of the agents enabled us to use a Kalman predictor to further refine our prediction.

CONCLUSIONS
In this paper, we proposed a signal processing technique to model and predict states in a multilayer network. The actual diffusion network has been learned by looking at previous diffusion data and has been applied to predicting the future states of agents in the network. Having partial observation of the state of the agents changes the state-space dynamics model to a Kalman filter problem. The Kalman filter allows us to fur-ther refine our state prediction by learning over the prediction error of the observed subset. In future work, we will explore the information diffusion problem with a goal to develop necessary tools to analyze diffusion in more complex network structures.