Inferring Motif-Based Diffusion Models for Social Networks

1 Introduction

How information spreads from one node to another over online social and information networks is well known to be highly related to the influence between the nodes. In the literature, different diffusion models have been proposed and the underlying diffusion networks can be inferred to explain the observed information cascades [Goldenberg et al., 2001; Lee et al., 2012; Goyal et al., 2010; Gomez-Rodriguez et al., 2011]. Most of them share the assumption that the activation of a node is caused independently by its parents. This assumption limits our understanding on how a node is influenced by the interactions of its parent node activations. For instance, sometimes people may not respond to discussions of their so-so friends until an more influencial friend steps in.

The long-standing framework which associates the probability of adopting a behavior with multiple neighbors [Granovetter, 1978; Jackson and Yariv, 2007] has recently been observed also for the user engagement behavior in Facebook [Ugander et al., 2012]. This notion was later on incorporated into diffusion models for social networks [Bao et al., 2013], where a component-based diffusion model was proposed in which the influence on a node by its parents is exerted independently by the connected components of the parents. In [Bao et al., 2015], a set of inferred co-activation patterns of the parents of each node are assumed to be independently exerting their influence on the node, where the co-activation patterns are assumed to be static in nature.

In this paper, we propose a diffusion model with the dynamic interaction patterns of nodes incorporated. Motifs, often defined as over-represented patterns, have widely been applied for characterizing the structural and functional properties of sequential data (e.g., genomic DNA [Kim et al., 2008]) and network data (e.g., [Milo et al., 2002]). We postulate that the information cascades over the whole network are embedded with a common set of latent temporal activation patterns as the underlying interaction mechanisms of the nodes causing the information to diffuse over the social network. We propose a stochastic temporal activation motif model to represent the temporal activation patterns, and thus define a novel diffusion model based on the motifs. Also, we assume that the motifs are attributed with social roles (as in [Scripps et al., 2007]). We formulate the motif detection problem and the diffusion network inference problem under a unified probabilistic framework. A two-level EM algorithm is derived so as to infer the diffusion-specific motifs and the diffusion probabilities simultaneously. For performance evaluation, we apply the proposed model to three real-world social network datasets with significant improvement on modelling accuracy compared with some recent work. We also illustrate how the inferred temporal activation motifs can be interpreted as the underlying interaction mechanisms causing the diffusion to happen in different social networks.

To the best of our knowledge, this is the first work where the identification of temporal activation motifs and the inference of the information diffusion network are solved within a unified framework. Also, the temporal activation motifs discovered are diffusion-specific ones, which also makes this work unique compared to other motif detection work.

2 RelatedWork

Diffusion models have been studied for the past decade to gain theoretical understanding of how information spreads within social networks [Goldenberg et al., 2001; Lee et al.,

2012; Goyal et al., 2010; Gomez-Rodriguez et al., 2011]. Two commonly used models are the Independent Cascade (IC) model [Goldenberg et al., 2001] and the Linear Threshold (LT) model [Kempe et al., 2005], which have also been put under the unified framework of General Threshold and Cascade Models [Kempe et al., 2003]. Point process models such as Hawkes process diffusion models have recently been proposed so as to model the inter-activation time [Yang and Zha, 2013; Zhou et al., 2013; He et al., 2015]. Also, instead of the conventional way to represent information spread as cascade sequences, some recent work assumes that a cascade takes the form of a tree [Sun et al., 2009]. Some also studied how the diffusion processes in social networks are affected by factors like the cascade structure, its size, and the roles of the users involved [Anderson et al., 2015]. In parallel, the basic IC model has also been extended to uncover temporal dynamics [Lee et al., 2012], and to take continuous time [Goyal et al., 2010] and et al.

Most of the extensions of the ICmodel still share the same assumption that a node is influenced independently by any of its parents. By exploring the structural and behavioral properties of neighboring nodes and their relationship with information diffusion, a component-based diffusion model was recently proposed [Bao et al., 2013] where the influence of the parent nodes to a node is not exerted individually but by connected components of nodes. A structural diversity factor was applied to each such component to quantify the information redundancy. In [Zhang et al., 2013], a related notion called social influence locality has been studied for modeling retweeting behaviors. In [Bao et al., 2015], a set of inferred co-activation patterns of the parents of each node are assumed to be independently influencing the node. To contrast, our proposed motif-based diffusion model makes contribution to identifying latent temporal interaction patterns of nodes which cause the information diffusion to happen in social networks.

Recently, network motifs have been applied to characterize online social networks [Liu et al., 2013]. However, to the best of our knowledge, there does not exist work on inferring application-specific motifs with social roles integrated. In this paper, we adopt the roles defined in [Scripps et al., 2007]. There also exist other definitions proposed in the literature, e.g., Pagerank Scores and Structural Hole Spanner Scores [Fang and Tang, 2015].

3 AMotif-based DiffusionModel

In this section, we first present some key concepts needed for defining the information diffusion modeling problem. In particular, we make use of also social roles in our formulation. Then, we present a stochastic temporal activation motif model, followed by a corresponding diffusion model and a two-level EM algorithms for the model learning.

3.1 Preliminaries

Social Network and Information Cascade

We represent a social network as a directed graph G = (V↪ E) where V is the set of nodes and E is the set of edges. Let e = (v↪w) be an edge from node v to node w, and f(w)

and b(w) be the sets of child nodes and parent nodes of node w respectively, given as: f(w) = ¶u : (w↪ u) 2 E♦ and b(w) = ¶v : (v↪ w) 2 E♦▷

Let Ds = ¶Ds(0)↪Ds(1) · · ·Ds(Ts)♦ be the sth observed information cascade where Ds(t) is the set of nodes activated at time step t and Ts is the final time step for the cascade Ds.

Social Role

In our model, we assume that each node v carries a social role R(v) := ¶r1↪ ▷▷▷rn♦ based on [Scripps et al., 2007]. In particular, there are four different social roles, namely ambassadors, big fish, bridges and loners, defined based on the local structural information of different nodes. Ambassadors have both high degrees and many connections to different communities, representing the ones with high global influence. Big fish (big fish in a small pool) have high degrees but connections to only a limited number of communities, standing for those with high local influence, like leaders in a small research field. Bridges have low degrees but are connected to many communities, playing the roles of bringing knowledge exchange among communities although not influential. Meanwhile, loners have both lower degrees and less connections to different communities, representing the ones being alone. By adopting these roles, we can then try to discover and see if there exist patterns characterizing how discussions are developed via the interactions of the roles. In general, other role definitions can also be used according to the specific need of analysis.

Activation Sequence and Subsequence

Diffusion models for social networks explain how the activations of some user nodes makes influence on their neighbors so that they will activate as well. Given that in the sth cascade, assume that a node w is activated at time t and t - Ls(w↪ t) consecutively where Ls(w↪ t) is defined as the interval between the latest activation of the node w prior to time step t in the sth cascade. To explain the activation of w at t, the set of activations being considered are those found in b(w) (parents of w) and activated in the time interval [t -Ls(w↪ t)↪ t]. The activations are then sorted in ascending order, each tagged with a pre-computed social roles to form a particular temporal activation sequence for node w.

In addition, we make the conjectures that (i) there exist temporal subsequence patterns embedded in the set of temporal activation sequences for all nodes in G and that (ii) the parent activations even though sorted in time may not necessarily mean that they happen in response to each other one by one exactly according to the temporal order. We thus sample subsequences from a temporal activation sequence by grouping adjacent activations happening within a pre-set ∆t in an overlapping manner. We implement a depth-first search with a First-In First-Out stack. We first push all the individual activations in a temporal activation sequence (each as a subsequence candidate) into the stack. Then, we pop a subsequence candidate X from the stack. Suppose xi is the last activation in the candidate X. We search for the activation xj happening later than xi in the original activation sequence. If such xj can be found and happens within a ∆t time window, we will add xj to the end of X and push the new subsequence candidate into the stack again. Otherwise, the candidate will be finalized. The process repeats until there are no more candidates in the stack. We can also set a limit on the maximum number of activations allowed for a subsequence as l. In the sequel, we denote the corresponding set of subsequences for node w observed at time t in the sth cascade as X(s) w (t).

3.2 Formulation

To formulate a motif-based diffusion model under a probabilistic framework, we first define a stochastic temporal activation motif to represent the patterns of the aforementioned activation subsequence.

Temporal Activation Motif

Let M = ¶M1↪ ▷ ▷ ▷ ↪Mk♦ be a set of k stochastic temporal activation motifs, which are parameterized as a set of probability matrices ⇥ = ¶⇥1↪ ▷ ▷ ▷ ↪⇥k♦. In particular, ⇥m = (✓m ij )n⇥n is defined so that ✓m ij is the probability of transiting from role ri to role rj as represented in the mth motif where n is the number of social roles. The probability that a particular subsequence h 2 X(s) w (t) is generated by the mth motif is given as:

where 0  ✓ij  1, 1  m  k, uh1 denotes the initial probability of observing the first element of the subsequence h. ehi (t) is an indicator which will be 1 if ht = ri where ht is the tth element in h. Also, a background model M0 is used to account for subsequences of activations which may happen at random. For simplicity, we compute the probability of generating h by M0 as Qt p(ht), where p(ht) is estimated as Nr◁Ntotal if ht = r, where Nr and Ntotal denote the total number of activations with role r and the total number of all activations respectively.

Motif-based Information Diffusion

For a node to be influenced by a set of parent nodes causing information diffusion, we postulate that it is the interaction patterns of the parent node activations (i.e., the temporal activation motifs) which form the underlying mechanisms. Therefore, we assume that each subsequence of parent node activations will contribute to the probability that one of the motifs is in effect. And given a particular motif and a particular node, we define the corresponding motif-based diffusion probability.

We denote ⌧m↪w = p(w = 1♣⇥m) as the motif-based diffusion probabilities between Mm and a node w, and the prior probabilities of the Mm as ↵m = p(⇥m). The diffusion process of a particular cascade proceeds as follows. Given the initial set of activated nodes in the sth cascade (Ds(0)), we assume that each of them tries to activate its child nodes. For each such child node w, the probability that it will be activated by a subsequence h 2 X(s) w (t) is then given as:

With the independency assumption that node w will be activated if at least one of those subsequences succeeds, the probability for w to activate at time step t + 1 in the sth cascade is given as:

The diffusion process proceeds until there are no more nodes being activated and the cascade stops.

The likelihood function of the set of observed cascades ¶Ds♦ is then given as:

3.3 Learning Algorithms

To infer the latent temporal activation motifs and the diffusion probabilities simultaneously, we propose a two-level EM algorithm to maximize the likelihood function L(⇥) with respect to the parameters ⇥ = ¶¶⌧m↪w = p(w♣⇥m)♦↪ ¶↵m = p(⇥m)♦↪ ¶⇥m♦♦. The inferred temporal motifs will be those making the information diffusion mostly likely to happen.

First level EM

Let Ih↪m be a latent variable that takes the value of 1 when a parent subsequence h belongs to the latent pattern m, and 0 otherwise, given the constraint Pkm=0 Ih↪m = 1. Let I = ¶Ih↪m♦ denote the whole set of the latent variables. If we assume that I is known, the complete likelihood function can be written as:

where

where

As I is missing in most of the cases, we can do the E-step by first computing the posterior probabilities of I with the current parameter estimates ˆ ⌧m↪w = p(w♣ ˆ⇥m), ˆ↵m = p( ˆ⇥m) and ˆ⇥m, given as

Note that for the case when w is not activated, we substitute ˆ ⌧m↪w with (1-ˆ ⌧m↪w) for ⌘h↪m. Then, the expected likelihood function can be defined as:

For the M-step, we maximize Q(⇥♣ ˆ⇥) by taking the derivative of Q with respect to ⇥ to obtain the updating rule of the model parameters.

To update ¶↵m♦, according to the Lagrange multiplier method, maximizing Q(⇥♣ ˆ⇥) with constraint Pkm=0 ↵m = 1 yields

Thus, 8↵m PSs=1 PTs-1 t=0 Pw Ph2X(s) w (t) ⌘h↪m ↵m - λ = 0▷ Then it can be easily shown that

To update ¶⇥m♦, we consider p(h♣⇥m), and

where m 6= 0. Since p(h♣⇥0) is estimated as constant, there is no corresponding parameters for m = 0.

To update ¶p(w♣⇥m)♦, setting to zero the derivative for the first term EI [log p(w(s↪ t + 1)↪ I ♣X(s) w (t))] in Eq.(1) does not have a simple solution. So, within this M-step, we introduce another level of the EM algorithm.

Second level EM

Let Y (s) h↪w (t) denote a latent variable that indicates whether the activation of a node w at time step t in the sth cascade is due to w's parent subsequence h or not. We further define Ys = ¶Ys(0)↪ Ys(1) · · · Ys(Ts)♦ where Ys(t) := ¶Y (s) h↪w (t)♦ represents the set of latent variables corresponding to the activations at time step t in the sth cascade. Then, we compute the posterior probability of Y (s) h↪w (t), given as

where ˆ ⌧m↪w stands for the current estimate of ⌧m↪w, and

The corresponding Q0 function can then be defined as Q0 (⇥♣ ˆ⇥)

We define T + w↪s as the set of time steps ¶t♦ with reference to the sth cascade satisfying the condition that node w is activated at time step t + 1 and at least one of its parents have been activated since t - Ls(w↪ t). Meanwhile, T - w↪s is the set of time steps ¶t♦ where node w is not activated at t + 1, but at least one of its parents have been activated since t - Ls(w↪ t). Moreover, we define a set of cascades where T + w↪s is not empty as S+ w = ¶Ds : 9t(X(s) w (t) 6= ; ^ w 2 Ds(t +1))♦, and a set of cascades where T - w↪s is not empty as Sw = ¶Ds : 9t(X(s) w (t) 6= ; ^w 62 Ds(t +1))♦. Then @Q◁@⌧m↪w = 0 yields:

4 Experiments

We compare our model with some recently proposed diffusion models using three real-world social and information network datasets.

4.1 Experimental Settings

We compare our model (abbreviated as Motif-IC) with the basic IC model, a component-based IC model (abbreviated as COMP-IC [Bao et al., 2013]) and a co-activation pattern based IC model (abbreviated as LCM-IC [Bao et al., 2015]). The two variants of the IC models are chosen for comparison as both considered structural and behavioral dependency of the parent nodes. For all three models, we allow a node to be activated multiple times in a single cascade for fair performance comparison.

For all the experiments performed, the initial values of ¶ˆ ⌧m↪w♦ are within [0↪ 0▷1] as the diffusion probabilities in real data are known to be very small (e.g., with a mean value of 0▷04 and standard deviation of 0▷07 [Gruhl et al., 2004]). The initial values of ¶ˆ ✓m ij ♦ are generated within [0↪ 1]. And the initial values of ↵m are generated within [0↪ 1] satisfying Pm ˆ↵m = 1. Also, for COMP-IC, LCM-IC and Motif-IC, we obtain the optimal number of model components using the cross-validation method.

As the ground-truth is unknown for real data, we use perplexity as the metric for performance evaluation. The perplexity over a set of observed cascades is defined as

where P(Ds) is the probability for the sth cascade to be generated, and W is the number of activations due to the influence of the corresponding nodes' parents. A smaller perplexity value indicates the inferred model to be more accurate, and thus better performance. Also, five-fold cross-validation is adopted to avoid experimental bias.

4.2 Performance Evaluation

Three real datasets are used for the evaluation, namely MemeTracker [Leskovec et al., ], Digg [Lerman and Ghosh, 2010] and Flixster [Jamali and Ester, 2010] where both the network structure and the information cascades are available. (i) The MemeTracker dataset records the posts of mass media and weblogs from August 1 2008 to April 30 2009. Websites with news articles and blog posts are modeled as nodes which are further connected by directed edges (hyperlinks). It contains 4 million nodes, 13 million edges, and 71↪ 568 cascades. Each cascade is defined based on a set of posts reporting the same event. (ii) The Digg dataset records the story voting process under a directed friendship network over one month in 2009. Users are modeled as nodes and following relations are modeled as edges. It contains 280k nodes, 2▷6 million edges and 3↪ 553 cascades. Each cascade is defined based on a particular frequently voted story. (iii) The Flixster dataset records the movie rating process under an undirected friendship network of users over a period from November 2005 to November 2009. Users are modeled as nodes and friend relations are modeled as edges. It contains 787k nodes and 5▷9 million edges. We select 5↪ 318 cascades for the frequently rated movies in the dataset.

Figure 1 shows the experimental results. For all the three datasets, the proposed Motif-IC model achieves the best performance consistently. Compared with COMP-IC and LCMIC, Motif-IC results in decreases in perplexity by 0▷69 and 0▷09 respectively for MemeTracker, by 2▷06 and 0▷40 for Digg, and by 0▷19 and 0▷04 for Flixster. The optimal number of motifs, k, is found to be 5 for MemeTracker, 5 for Flixster, and 15 for Digg. The basic IC Model has much worse performance and thus the result is not shown in the figure.

4.3 Discussion on the InferredMotifs

The temporal activation motifs of parent nodes ⇥m inferred from the three datasets are reported in Figures 2, 3 and 4. The roles of Ambassador, Big Fish, Bridge, and Loner are indicated as "A", "BF", "B" and "L" respectively. We show only two motifs with the highest value for their mixing portions due to the page limit.

For the Digg and Flixter datasets, the interpretation of the social roles is straight-forward based on the role definitions. For the MemeTracker dataset, Ambassadors are referring to the websites covering various topics (e.g., news.bbc.co.uk a major news media). Big Fish are referring to the websites featuring specific domains (e.g., climateark.org that publishes news about climate). Bridges are referring to the websites covering news of several domains (e.g., merchantlaw.com containing business laws in several practice areas like agriculture law and so on). The weblog sites often turn out to be Loners (e.g., humppazoid.blogspot.com). Some examples can be found in Table 1.

In the following, we provide interpretations on the inferred motifs as diffusion mechanisms:

MemeTracker-Motifs: Referring to Figure 2, we can interpret MemeTracker-Motif 1 as the pattern of first starting with a posting at some famous websites (e.g., major news media) and then following up again by famous websites, with occasional starts at some domain specific websites and then picked up by famous websites afterwards. MemeTrackerMotif 2 is another pattern with some posting interactions among weblogs before it is being picked up by some famous websites. There is the possibility that MemeTrackerMotif 1 accounts for the diffusion of major news, while MemeTracker-Motif 2 accounts for the diffusion of news of some more specific topics which gain momentum of diffusion within the weblogs at the earlier stage.

Digg-Motifs: According to Figure 3, Digg-Motif 1 reveals a pattern that the globally reputable users starting the voting and then followed by also other reputable users, again with occasional starting votes from users of other types and then being followed by reputable users. Digg-Motif 2 refers to a pattern with occasional starts by big fish users and the voting process is retained among the big fish before the reputable users react. So, the first motif may refer to story votings among the circle of reputable users, while the second one may refer to story votings first among big fish users and got spread also to reputable users. A user in principle can respond differently to these different mechanisms.

Flixster-Motifs: According to Figure 4, Flixster-Motifs 1 and 2 are more different from those inferred from the other two datasets. In particular, there is a much higher chance of transiting from globally reputable movie lovers to other types of users, and that there is a much higher chance that the movies are kept being evaluated within big fish, bridge, or loner circles. This could be because views on movies are more personal, resulting in more diverse parent activation patterns (instead of globally dominated by some users).

Note that in order to further validate the insights gained from the inferred motifs as discussed, more in-depth analysis and evaluation efforts will be needed. However, we believe that the inferred patterns form new hypotheses which are data-driven and worth further investigation for deepening our understanding on user behaviors and information diffusion in large-scale social networks.

5 Conclusion

In this paper, we proposed a novel motif-based diffusion model for social networks and a corresponding learning algorithm to infer both the latent temporal activation motifs as well as the diffusion model under a unified framework. The empirical results carried out on a number of real-world datasets consistently show that the proposed model achieves a higher modeling accuracy compared with a number of recently proposed models. Also, we have shown how the inferred temporal activation motifs can be interpreted as the underlying interaction mechanisms for the diffusion to happen in different social and information networks.

Possible extensions of this work may include fusing multimodal information in the cascades to infer more informative "colored" motifs. Also, the stochastic motif models can be further extended to increase its representation power. In general, we believe that this work provides a bridge between work of diffusion modeling and motif-based network characterization. Both have been used to support different social science related studies. Bridging them implies that it opens up a number of new opportunities. For instance, it will be interesting to perform careful studies to evaluate how the inferred diffusion specific motifs are related to the different types of events happening in social networks under different topics of concern. In addition, how each user responds to different activation motifs can also be studied to achieve better user characterization and influence maximization.

Acknowledgments

This work was partially supported by Hong Kong Baptist University Strategic Development Fund.