Discovering Latent Influence in Online Social Activities
via Shared Cascade Poisson Processes
Tomoharu Iwata

Amar Shah

Zoubin Ghahramani

University of Cambridge

University of Cambridge

University of Cambridge

iwata.tomoharu@lab.ntt.co.jp as793@cam.ac.uk

ABSTRACT
Many people share their activities with others through online communities. These shared activities have an impact
on other users’ activities. For example, users are likely to
become interested in items that are adopted (e.g. liked,bought and shared) by their friends. In this paper, we propose a probabilistic model for discovering latent influence
from sequences of item adoption events. An inhomogeneous
Poisson process is used for modeling a sequence, in which
adoption by a user triggers the subsequent adoption of thesame item by other users. For modeling adoption of multiple
items, we employ multiple inhomogeneous Poisson processes,
which share parameters, such as influence for each user andrelations between users. The proposed model can be used forfinding influential users, discovering relations between users
and predicting item popularity in the future. We present anefficient Bayesian inference procedure of the proposed model
based on the stochastic EM algorithm. The effectiveness ofthe proposed model is demonstrated by using real data sets
in a social bookmark sharing service.

Categories and Subject Descriptors
H.2.8 [Database Management]: Database Applications—
Data Mining; I.2.6 [Artificial Intelligence]: Learning; I.5.1[Pattern Recognition]: Model—Statistical

General Terms
Algorithms

Keywords
Poisson processes, social community, latent variable models,
Bayesian inference

1.

INTRODUCTION

Many people share their activities with others through online communities, such as social sharing, social networking,Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
KDD ’13
Copyright 20XX ACM 978-1-4503-2174-7/13/08 ...$15.00.

zoubin@eng.cam.ac.uk

and microblogging services. For example, in social sharing services, users share their favorite items, such as web
pages [1], photographs [2], video [3], music [4] and scientificpapers [5]. These shared activities have an impact on otherusers’ activities. Users are likely to become interested in favorite items of their friends. A web page that is praised byan influential user in a social network service is likely to get
popular.
We can obtain activity data from these online services.
However, we cannot generally obtain data that directly describe which activity has had an impact on the following activities. The user interactions in some online communities
have been referred to as “ballot box communication” [34],in which users do not directly interact with each other byexchanging messages, but they implicitly interact with one
another by expressing their preferences on the shared items.
In this paper, we propose a probabilistic model for discovering latent influence between users in social communities.
As activities, we consider adopting items by users over time,such as sharing web pages, voting for music and joining communities. The given data is multiple event sequences, where
each event sequence is associated to an item, and contains
user and timestamp information for each event of adopting
the item. The proposed model can be used for finding influential users, discovering relations between users and predicting trends in item popularity in the future.
With the proposed model, we assume that each user has
some latent degree of influence. Each adoption event can
trigger the subsequent adoption events for the same itemby other users. The possibility of triggering depends on
the influence of the users of the preceding events. The proposed model also assumes that the influence differs among
pairs of users. Friends can have an impact more than people
who have never met. We use a cascade Poisson process [30]for modeling an event sequence of adopting an item. By
using multiple cascade Poisson processes for modeling multiple event sequences and sharing their parameters, we caninfer influence for each user and relations between users. We
call the proposed model shared cascade Poisson processes(SCPP).
We present an efficient probabilistic inference procedure
for the proposed model based on the stochastic EM algorithm. In the E-step, we sample the latent trigger for each
event from the preceding events using collapsed Gibbs sampling while analytically integrating out parameters for influences and relations. By integrating out parameters, we candrastically reduce the memory requirement. In the M-step,
we estimate the other model parameters by maximizing thejoint likelihood. By alternately iterating E- and M-steps, we
infer the proposed model from the given data.
The paper is organized as follows: In Section 2, we outline related work. In Section 3, we propose the shared cascade Poisson processes for discovering latent influence frommultiple sequences of item adoption events. We present its
Bayesian inference procedure in Section 4, and discussion
on scalability of the inference in Section 5. In Section 6,
we describe a sampling procedure for generating data fromthe inferred model. In Section 7, we demonstrate the effectiveness of the proposed framework by using real data sets
in a social bookmark sharing service. Finally, we present
concluding remarks in Section 8.

2.

RELATED WORK

γ
Item1

A

Table 1: Notation.
Description
set of users
set of items
item, i ∈ I
user of the nth event in item i, uin ∈ Uobservation period
time of the nth event in item i, t ∈ [0, T ]number of events for item i in time [0, T ]influence of user u, αu ≥ 0
popularity of item i, αi ≥ 0transitionP
probability from user u to u′ ,
θuu′ ≥ 0, u′ ∈U θuu′ = 1
decay parameter, γ ≥ 0

B

Item2
Item3

Great interest is being shown in developing methods foranalyzing online social communities. Those methods areused for viral marketing [12, 28, 21, 6], ranking influential
users [31, 18] and personalized recommender systems [32, 11,
19, 7]. Learning degree of influence of users is useful for predicting future item adoption and recommendations [31, 11].
However, in many social communities, users may not necessarily declare explicit social ties among themselves even if
such functionality exists and the degree of influence of eachtie is rarely explicitly declared. Thus, estimating influences
and relations among users from their activities are important.
Influences in social communities are often analyzed by using information diffusion models, such as independent cascade models [13, 35, 15] and linear threshold models [16].
They usually assume discrete time although events occur
in continuous time. Some information diffusion models incontinuous time have been proposed [17, 29]. The proposedmodel is based on Poisson processes, which are widely used
for modeling events in continuous time. Poisson processes
have been extensively studied in statistics, and have elegant
theoretical properties, such as superposition and subsampling properties [22]. We can use these properties for developing a procedure of generating samples as described in Section 6, and for extending the proposed model. We develop
an efficient Bayesian inference procedure, where parameters
are analytically integrated out. With continuous time information diffusion models [29], influences are estimated given
the network structure of users, where each edge represents
the existence of influence. On the other hand, the proposedmodel can efficiently estimate influences without the network structure because influence parameters, which require
memory of the order of the square of user size, integrated
out in the Bayesian inference. In recent years, methods for
estimating influences without the network structure basedon maximum likelihood have been proposed [25, 14, 15].
The proposed model is an extension of the cascade Poissonprocess [30], which models a sequence of cascading events.
We simultaneously model multiple sequences of adoption
events for multiple items by sharing parameters, such as
influences and relations among users. In [30], parameters
are estimated based on maximum likelihood. We take a
Bayesian approach that discourages overfitting during inference. Reciprocating Hawkes Processes [9], which are inhomogeneous Poisson processes, are used for discovering social
structures from direct interaction time-series data, such as
message exchanges. The proposed model does not use interaction data between users, but uses item adoption event

Symbol
U
I
i
uin
T
tin
Ni
αu
αi
θuu′

F

E

C

F

G

E

C

D

E

B

time

Figure 1: Example of the given data with three
items and seven users. Latent triggers are shownby arrows between users.
data to model how users indirectly interact with each otherand influence each other in social communities.

3. MODEL
Suppose that we have a set of |I| event sequences D ={Di }i∈I , where I is a set of items. An event sequence foritem i consists of Ni events, where an event is a pair of timeiand user, Di = {(tin , uin )}N
n=1 , which represents that user
uin adopts item i at time tin . Without loss of generality,
we can assume that events are sorted by their timestamps,
tin ≤ tin′ for n < n′ . Our notation is summarized in Table 1.
An example of the data is shown in Figure 1. Note thattriggers that are shown by arrows between users are notobserved.
In our model, an event can trigger further events in the
future. This property is referred to as cascading, where theoccurrence of an event sprouts the possibility of a chain offurther events. For example, in Figure 1, adoption of Item-1
by User-A causes adoption of Item-1 by User-B and UserF. In particular, we use the following intensity function formodeling the rate that user u adopts item i at time t influenced by the event that user u′ adopts item i at time
t′ ,

`
´
αu′ θu′ u exp −γ(t − t′ ) if t′ < t′′
λ(i,t ,u ) (t, u) =0
otherwise.
(1)Here, αu′ ≥ 0 represents the influence of user u′ on the otherusers. Note that this user influence remains the same acrossItem1

A

E

F

B

C

Intensity

G

D

time

A BF

C

E

Time

G

Item2

(b) Decay, γIntensity(a) Relation, Θ(c) Influence, {αu }u∈U(d) Popularity, {αi }i∈I

Figure 2: Parameters in the proposed shared cascade Poisson processes.

all items. The second factor θu′ u ≥ 0 represents the strength′of
P the relation from user u to user u, where we assume′u∈U θu u = 1. This relation matrix is shared across items.
The third factor exp(−γ(t−t′)) models decay of the influence
over time with parameter γ ≥ 0. Since an event cannot havean effect on past events, the intensity is zero when t′ ≥ t. A
decaying rate over time is a simple but natural assumption
since, in general, trends evolve or are replaced over time.
There is no influence from other event sequences, and eventsof item i do not trigger events of other items i′ 6= i.
Events can occur without influence from preceding events
according to the following background intensity function,
λ(i,0) (t, u) = αi θ0u .

(2)Here, αi ≥ 0 represents the rate that item i is adopted without being triggered by the preceding events. It represents
the general popularity of item i; if it is high, many users
adopt the item without copying or influence from peers.
θ0u ≥ 0 represents the probability that a userP
who adopts anitem without any trigger is in fact user u, and u∈U θ0u = 1.
In Figure 1, User-A, User-E and User-G adopt Item-1 independently from the preceding events. The first event foreach item always occurs from the background as, by definition, there are no previous users to be influenced by. The
background intensity can be seen as influence from outside
the social community, such as newspapers, TV programs andonline news sites as [26].
Figure 2 shows the parameters in the proposed sharedcascade Poisson processes: (a) relations between users, Θ ={θ}u∈U + , θu = {θuu′ }u′ ∈U , (b) parameter of influence decay
over time, γ, (c) influence for each user {αu }u∈U , and (d)popularity for each item {αi }i∈I . Here, U+ ≡ U ∪ {0}represents a set of users contain a virtual user who is used forthe background intensity as well as actual users U . Noticethat influence can occur in both directions amongst a pairof users e.g. in Figure 2 (a) we see that User-B and User-C
influence each other.
(n)
Let Di be an event sequence of item i, which consists of(0)
events caused by the nth event, Di be an event sequence
(n)
(n′ )
without triggers. They are disjoint, Di ∩ Di
= ∅ forn 6= n′ . We assume that each sequence is generated by a

Intensity

G

Item3

C

Item2

B

Item1

A

F

E

Time

C

D TimeItem3

background

E B

Figure 3: Dynamics of intensity in the shared cascade Poisson processes.
Poisson process as follows,
(0)

Di

`
´
∼ PoissonProcess λ(i,0) (t, u) ,for events from the background intensity, and`´(n)Di ∼ PoissonProcess λ(i,tin ,uin ) (t, u) ,

(3)

(4)

for events triggered by the preceding event n = 1, · · · , Ni .
The whole event sequence of item i is represented by theirS i(n)union, Di = N
n=0 D i . Note that D i is a union of Poissonprocesses. The superposition of Poisson processes is also a
Poisson process (a proof can be found in [20]) and we use
this fact to rewrite the generative process using a Poissonprocess,
Di ∼ PoissonProcess (λi (t, u)) ,where the recursive intensity function is given byX
λi (t, u) = λ(i,0) (t, u) +λ(i,t′ ,u′ ) (t, u),

(5)

(6)

(t′ ,u′ )∈D it

where Dit = {(t′ , u′ )|(t′ , u′ ) ∈ Di and t′ < t} is the setof events before time t.
Figure 3 shows the dynamics of intensity for each item.
The horizontal line in each item represents the background
intensity, which is constant over time, but different depending on the item. At the time of an event occurrence, the intensity increases depending on the influence of its user. For
example, since User-A has high influence, the event by UserA increases the intensity largely. The intensity decreases
over time with parameter γ. The total intensity is the superposition of the background intensity and intensities fromthe preceding events.
The probability of multiple event sequences D given parameters α = {αm }m∈U ∪I , Θ and γ is described as follows,p(D|α, Θ, γ)
=

I
Y

i=1

Ni
“ Z T X”Yλi (tin , uin ),exp −λi (t, u)dt
0

u∈U

n=1

(7)

where we can analytically calculate the integral as follows,
Z T X
λi (t, u)dt
0

and the joint likelihood is given byp(D, Z|γ, β, a, b)
Z Z=p(D, Z|α, Θ, γ)p(α|a, b)p(Θ|β)dαdΘ”“
X X(tin − tizin )= exp −γu∈U= αi T +

Ni
“
“
””
1X
αu 1 − exp −γ(T − tin ) .
γ n=1

(8)

i∈I n:zin 6=0

This value is called the expectation function, which represents the expected number of occurrences in the time period
from 0 to T .

4.

a«|U |+|I |Γ(Mm + a)
M +a(C
m + b) mm∈U ∪I«|U |+1 Y Q„
Γ(β|U |)
u′ ∈U Γ(Muu′ + β)×,Γ(Mu + β|U |)Γ(β)|U |u∈U×INFERENCE

b
Γ(a)

Y

(14)

+

We present a Bayesian inference algorithm for the sharedcascade Poisson processes based on a stochastic EM algorithm. The algorithm alternates collapsed Gibbs samplingof latent triggers and maximum joint likelihood estimationof hyperparameters, while integrating out parameters for influences, popularities and relations.
We introduce latent variables for simplifying the inference
without changing the model. Let zin ∈ {0, 1, · · · , n′ |tin′ <tin } be the latent index of the event which caused the arrival of the nth event in item i, where zin = 0 indicatesthat the event was triggered by background intensity. The
trigger event must occur before the arrival of this nth event,therefore tin′ < tin , since cause precedes effect. By using
latent variable z, the recursive intensity function (6) can be
written asX
λi (t, u) =λi (t, u, z),
(9)
z

P
PNi
′
) is thewhere Muu′ =n=1 δ(uizin = u)δ(uin = uPi∈Inumber of events for user u′ caused by user u, Mu = u′ ∈U Muu′
is the number of total events caused by user u, and Mi =P
Ni
n=1 δ(zin = 0) is the number of events caused by the background intensity in item i. Here, δ(·) represents indicatorfunction; δ(A) = 1 if A is true, and δ(A) = 0 otherwise. For
each item i ∈ I, Ci = T , and for each user u ∈ U ,
„
“
”«
1 X
Cu =
(15)
1 − exp −γ(T − t) ,γ t∈Duwhere Du is a set of timestamps of events of user u.
Based on the joint likelihood (14), we develop a stochastic
EM procedure for the inference. In the E-step, given thecurrent state of all but one latent assignment zin , a newvalue for zin is sampled from the following probability,p(zin = y|D, Z\in , γ, β, a, b)

where
λi (t, u, z) =

λ(i,0) (t, u)λ(i,tiz ,uiz ) (t, u)

if z = 0otherwise.

(10)

In words, (9) states that the intensity is a sum of intensities
for each possible trigger of the event.
Combining (7)–(10), the joint probability of data D andilatent variables Z = {{zin }Nn=1 }i∈I given parameters α, Θand γ is as follows,p(D, Z|α, Θ, γ)
„
«
Ni
I
X
Y
`
´”
1“
αu
exp −αi T −=1 − exp −γ(T − tin )
γ
n=1
i=1
×

„

Ni
Y

λi (tin , uin , zin ).

(11)

n=1

We assume a Gamma prior for each of user influences anditem popularities αm , m ∈ U ∪ I,
1 a a−1p(αm |a, b) =b αm exp(−bαm ),
Γ(a)

(12)

uiy \inuiy \in

if c = 0otherwise,(16)

where y ∈ {0, 1, · · · , n′ |tin′ < tin }, and subscript \in represents the value or set excluding the nth event in item i.
In the M-step, the decay parameter γ and Dirichlet parameter β are estimated by maximizing the logarithm of thejoint likelihood (14). We estimate γ using Newton’s method.
The objective function to be maximized as a function of γ
is given by
X X(tin − tizin )S(γ) = −γi∈I n:zin 6=0−

X(Mu + a) log(Cu + b).

(17)

u∈U

The update rule is given by

and a Dirichlet prior for relations θu , u ∈ U+ ,Γ(β|U |) Y β−1
θuu′ ,p(θu |β) =Γ(β)|U | ′p(D, Z\in , zin = y|γ, β, a, b)p(D\in , Z\in |γ, β, a, b)
8 Mi\in +a M0uin \in +β< C
M0\in +β|U |i +b“” Mu \in +a Mu u \in +β
=
iy
iy in
: exp −γ(tin − tiy )C+b M+β|U |

∝

(13)

u ∈U

where | · | represents the number of elements in the set.
The choice of a Gamma and Dirichlet prior permit analytic
marginalization over the parameters α and Θ, respectively,γ←γ−∂S(γ)/∂γ,∂ 2 S(γ)/∂γ 2(18)

where the first and second derivatives of the joint likelihood
with respect to γ are described in Appendix A.
We estimate the Dirichlet parameter β by using the fixedpoint iteration method described in [24]. The update rule

is
P

u∈U +

β←β P

P

u∈U +

Ψ(Muu′ + β) − Ψ(β)” ,Ψ(Mu + β|U |) − Ψ(β|U |)
u′ ∈U

“

”

“

(19)

where Ψ(·) is the digamma function defined by Ψ(x) =∂ log Γ(x).
∂x
By alternately iterating the E-step with (16) and M-stepwith (18)–(19), we can estimate latent variables Z, decay
parameter γ and Dirichlet parameter β. Note that because
we are able to analytically integrate at all other parameters(influences αu , item popularities αi , and the relation matrixΘ), there is very little risk of overfitting. The posteriors for
α and Θ are given byp(αm |D, Z, a, b, γ) = Gamma(Mm + a, Cm + b),p(θu |D, Z, β) = Dirichlet(Muu′ + β).

(20)
(21)

Thus, we can obtain point estimates of the integrated out
parameters as follows,α̂m =Mm + a,Cm + b(22)

which can be used for finding influential users, andθ̂uu′ =

Muu′ + β,
Mu + β|U |(23)which can be used for discovering relations between users.
In the experiments, we fixed the hyperparameters as follows:a = b = 1.

5.

SCALABILITY

The proposed model has relation parameters between users
Θ, which require memory of O(|U |2 ). The memory requirement increases quadratically with the number of users if wewere to explicitly sample the relation parameters in our inference procedure. It makes analyzing data with a huge
number of users prohibitively expensive. However, in the
proposed inference procedure, we do not need to store theseparameters as they are integrated out. Instead, we need tostore count Muu′ for u ∈ U+ and u′ ∈ U , which represents
the number of events of user u′ which were caused by user
u. In general, most of the counts are zero since the count isincremented only when the two users adopt an item withina short time of one another. In addition, the Bayesian inference procedure exploits sparsity. When Mu′ u > Mu′′ u , theprobability of selecting the event of user u′ is high, because
the probability is proportional to Mu′ u in (16). The modelhas “the rich gets richer” effect. In the experiment using
the ‘science’ data set with 4,543 users, which is described in
Section 7, 59,590 elements of the influence parameters havenonzero value after the inference, which make up only 13.1
elements per user. Thus, by using the proposed inference,
we can analyze data with a huge number of users efficiently.
The most demanding part of the inference is Gibbs sampling in the E-step. The computational complexity of each
Gibbs sampling (16) is O(R), where R is the average number of events for each item, since we have R options for eachlatent variable on average. In total, the computational complexity becomes O(IR2 ). The computational time for theinference with the ‘science’ data set, which consists of activities in four years, was 12 minutes when using a computerwith 3.20GHz CPU.

Algorithm 1 Generate an event sequence from shared cascade Poisson Processes from time T to T ′ for item i.
Input: Parameters, α, Θ, γ, and data before T , D ={(tn , un )}N
n=1
Output: Data from T to T ′ , D ′ = {(tn , un )}n>N
1: D ′ ← ∅2: n ← N
3: loop4:sn ∼ Exponential(1)
Rt P
P
5:
tn+1 ← inf{t| T u∈U λi (t′ , u)dt′ ≥ nn′ =N sn′ }6:un+1 ∼ Discrete(λ̄i (tn+1 , u))7:
if tn+1 > T ′ then
8:
break
9:
end if10:n← n+111:D ′ ← D ′ ∪ {(tn+1 , un+1 )}12: end loop

6. SIMULATION
By generating sequences, we can simulate when users adopt
items in the future. We can generate event sequences basedon the shared cascade Poisson processes given parameters
and the data up to the present time. Based on Monte Carlo
method, we can predict informative values, such as the number of adoptions for each item, by averaging the simulation
results. The simulation can be also used for targeting users
who are influential and trigger the most events, which isuseful for sociology and viral marketing [21, 6].
Algorithm 1 shows the procedure of generating an event
sequence for item i from time T to T ′ , which is based onÇinlar’s method [10, 27]. The inputs are parameters, α, Θ,γ, and the data before T , D = {(tn , un )}N
n=1 . At line 4, an
exponential random variable is sampled, which corresponds
to a timestamp from a homogeneous Poisson process with
rate one. At line 5, we obtain a timestamp of the shared cascadeby inverting the expectation function
R · PPoisson processes′′u∈U λi (t , u)dt . The solution is given by
T
!
n
X
1
αun exp(γtn ) ,(24)
tn+1 = E + W −E
γ
′
n =1

where W (·) is the Lambert W function, which solves theequation x = W (x) exp(W (x)), and
!
n
n
X
1
1 X
E=
αun exp(−γ(T − tn )) .
sn′ + αi T −
αi
γ ′
′
n =N

n =1

(25)

At line 6, user un+1 is sampled depending on the intensity
at time tn+1 , whereλi (t, u),′u′ λi (t, u )λ̄i (t, u) = P(26)

is the intensity normalized to sum to one. This term represents the probability that the user adopting item i at time
t is u given the previous history of user item adoptions. Algorithm 1 can be used to efficiently forecast future event
sequences and simulate the effect of various social interventions.

Table 2: Data statistics
tag#items #users#events
ajax
35,231
9,554
563,605
javascript
47,256 11,258
779,845
java
60,386
6,645
474,325
linux
101,367 13,879
920,352
news
67,1885,434
324,406
opensource
44,483
6,925
432,379
photography
71,962 11,872
614,143
science
45,986
4,543
268,231webdesign
79,315 18,037 1,271,192

7.

EXPERIMENTS

We evaluated the proposed shared cascade Poisson processes using large data sets collected from a social bookmark
sharing service, Delicious [1]. Here, adopting an item corresponds to bookmarking a web page. The original data,
described in [33], is distributed by the authors for research
purpose. We used nine data sets obtained from the original data, where each data set consist of events of adopting
items that are tagged with one of nine frequently used tags.
The tags and their statistics are shown in Table 2. The
sets of users and items are different depending on each data
set. We omit users who appear less than 30 times in eachdata set. The data was collected between September 2003
to December 2007. Since the data only contain the date on
which a certain item was adopted, the timestamp in all our
experiments is measured in days.
We evaluated the predictive performance using the logarithm of the likelihood for timestamps at the test period
from T to T ′ , which is given by” X
X“ Z T ′ X
XL=λi (t, u),λi (t, u)dt
log
−
i∈I

T

t∈D itest

u∈U

u∈U

(27)

where Ditest represents the test data for item i. For eachdata set, we prepared 10 different training and test data
splits by changing the test time period from 10 to 100 days.
Figure 4 shows the test likelihoods, which are averaged by
the test period, T ′ − T . We compared the proposed sharedcascade Poisson processes (SCPP) with the homogeneous
Poisson processes (PP). The proposed model achieved higher
predictive performance than the Poisson processes with allof the data sets except for the ‘news’ data set. In general,
the test likelihood decreases as the test period increases,
because long term prediction is more difficult than shortterm prediction. Many web pages in the ‘news’ data set
are adopted by influence from portal or news sites, not by
influence of other users, which may explain why the Poissonprocesses achieved better performance.
We also evaluated the predictive performance of users byusing the logarithm of the likelihood for users at the test
period as follows,XX
log λ̄i (t, u).
(28)
L′ =
i∈I (t,u)∈D testi

We compared the proposed model with latent Dirichlet allocation (LDA) [8], and multinomial distribution as the baseline. LDA is a widely used probabilistic model for discrete
data, such as text documents, where each document consists

Figure 7: Relations between users estimated by the
proposed model in the ‘science’ data set. Each node
represents a user, and users who are influenced areconnected. We omit isolated users who are not connected with others.
of a set of words. In our data sets, a word corresponds toa user, and a document corresponds to an event sequenceof an item. Figure 5 shows the result. The proposed model
achieved higher user predictive performance than the othermethods with all of the data sets except for the ‘news’ data
set. These results indicate that modeling influences and relations is important for analyzing social activity data sets.
Figure 6 shows the event sequences in the ‘science’ data
set with the estimated results of influence between events.
Some events occur in a short time interval, and they werelearned to have been triggered by the precedent events in thesequence. Events which occurred in isolation were estimatedas being generated from the background intensity.
Figure 7 shows relations between users estimated by the
proposed model in the ‘science’ data set. The relation graphis visualized using the method in [23] so that connected
nodes are located closely. Most users have a small numberof edges, but a few users have a lot of edges; these would be
the main influencers or most influenced depending on the
direction. Some users form clusters, where users in eachcluster are connected to each other, representing communities of influence. Overall the influence graph for this data
set is quite sparse.
Figure 8 shows the values of influences and popularities
estimated by the proposed model in the ‘science’ data set,
where user and item indices were sorted by their values.
Only a small number of users and items have high influence
or popularity, whilst most have very small values.

8. CONCLUSION
In this paper, we have proposed a probabilistic model for
discovering latent influence in social activities. Our modelis based on multiple inhomogeneous Poisson processes, inwhich events are triggered by preceding events, and parameters are shared among the Poisson processes. We also presented its efficient Bayesian inference procedure based on
the stochastic EM algorithm. We have confirmed experimentally that the proposed model can appropriately model
sequences of item adoption events in social bookmark sharing data sets.

-1600

-2000
SCPP
PP

-1800

-3000
SCPP
PP

-2200

-2000

SCPP
PP

-3500

-2400

-4000

-2600

-4500

-2800

-5000

-2800

-3000

-5500

-3000

-3200

-2200
-2400
-2600

10

20

30

40

50

60

70

80

90

100

-6000
10

20

30

(a) ajax

40

50

60

70

80

90

100

-4000

-5500
-6000
-6500
-7000
30

40

50

60

70

80

90

-3500

-2200

-4000

-2300

-4500

-2400

-5000

-2500

-5500

-2600

-6000

-2700

-6500

-2800

100

60

70

80

90

100

90

100

SCPP
PP

20

30

40

50

60

70

80

90

100

10

20

(e) news

30

40

50

60

70

80

(f) opensource

-1600
SCPP
PP

-3800

50

-2900
10

(d) linux
-3600

40

-2100

-7000
20

30

-2000
SCPP
PP

-3000

-5000

10

20

(c) javascript

-2500
SCPP
PP

-4500

10

(b) java

-5000
SCPP
PP

-1800

SCPP
PP

-5500
-6000

-4000

-6500
-2000

-4200
-4400

-7000
-7500

-2200

-4600

-8000
-8500

-2400

-9000

-4800

-9500

-2600

-5000

-10000

-5200

-2800
10

20

30

40

50

60

70

(g) photography

80

90

100

-10500
10

20

30

40

50

60

(h) science

70

80

90

100

10

20

30

40

50

60

70

80

90 100(i) webdesign

Figure 4: Average test likelihood for timestamps with different test periods in nine social bookmark data
sets. The vertical axis is the test likelihood, and the horizontal is the test time period.

9.

REFERENCES[1] http://www.delicious.com/.
[2] http://http://www.flickr.com/.
[3] http://www.youtube.com/.
[4] http://www.last.fm/.
[5] http://www.citeulike.org/.
[6] N. Agarwal and H. Liu. Blogosphere: research issues,
tools, and applications. ACM SIGKDD Explorations
Newsletter, 10(1):18–31, 2008.
[7] C. Au Yeung and T. Iwata. Capturing implicit user
influence in online social sharing. In Proceedings of the
21st ACM Conference on Hypertext and Hypermedia,
pages 245–254. ACM, 2010.
[8] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent
Dirichlet allocation. Journal of Machine Learning
Research, 3:993–1022, 2003.
[9] C. Blundell, K. Heller, and J. Beck. Modellingreciprocating relationships with Hawkes processes. In
Advances in Neural Information Processing Systems
25, pages 2609–2617, 2012.
[10] E. Çinlar. Introduction to stochastic processes,
volume 3. Prentice-Hall Englewood Cliffs, NJ, 1975.
[11] D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg,
and S. Suri. Feedback effects between similarity andsocial influence in online communities. In KDD ’08,
pages 160–168, 2008.
[12] P. Domingos and M. Richardson. Mining the network
value of customers. In KDD ’01, pages 57–66, 2001.
[13] J. Goldenberg, B. Libai, and E. Muller. Talk of the
network: A complex systems look at the underlying
process of word-of-mouth. Marketing letters,
12(3):211–223, 2001.
[14] M. Gomez-Rodriguez, D. Balduzzi, and B. Schölkopf.
Uncovering the temporal dynamics of diffusion
networks. In Proceedings of the 29th International
Conference on Machine Learning, 2011.
[15] M. Gomez-Rodriguez, J. Leskovec, and B. Schölkopf.
Structure and dynamics of information pathways inonline media. In Sixth ACM International Conferenceon Web Search and Data Mining (WSDM), pages
23–32, 2013.
[16] M. Granovetter. Threshold models of collective
behavior. American journal of sociology, pages
1420–1443, 1978.
[17] D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins.
Information diffusion through blogspace. In
Proceedings of the 13th international conference on
World Wide Web, WWW ’04, pages 491–501, 2004.

-1000

-1000
SCPP
LDA
Multinomial

-1500

-3000
SCPP
LDA
Multinomial

-1500
-2000

-2000

SCPP
LDA
Multinomial

-4000
-5000

-2500
-2500

-6000
-3000

-3000

-7000

-3500

-3500

-4000

-4000

-4500
10

20

30

40

50

60

70

80

90

100

-8000
-9000
10

20

30

(a) ajax

40

50

60

70

80

90

100

-4500
-5500

20

30

40

50

60

70

80

90

100

90

100

(c) javascript

-1000
SCPP
LDA
Multinomial

-5000

10

(b) java
-2400
SCPP
LDA
Multinomial

-2000

SCPP
LDA
Multinomial

-2600
-2800
-3000

-6000

-3000

-3200

-6500
-7000

-3400

-4000

-3600

-7500

-3800

-5000

-8000

-4000

-8500

-4200

-6000

-9000

-4400

-9500

-7000
10

20

30

40

50

60

70

80

90

100

-4600
10

20

30

(d) linux

40

50

60

70

80

90

100

-4000

-1600

-5500

-1800

-6000

-2000

-6500

-2200

-7000

-2400

-7500

-2600

-8000

-2800
20

30

40

50

60

70

80

90

100

30

40

50

60

70

80

-4000
SCPP
LDA
Multinomial

-1400

-5000

10

20

(f) opensource

-1200
SCPP
LDA
Multinomial

-4500

10

(e) news

SCPP
LDA
Multinomial

-6000
-8000
-10000-12000-14000-16000-1800010(g) photography

20

30

40

50

60

70

80

90

100

10

(h) science

20

30

40

50

60

70

80

90 100(i) webdesign

Figure 5: Average test likelihood for users with different test periods in nine social bookmark data sets. The
vertical axis is the test likelihood, and the horizontal is the test time period.
1000
900
800
700
Item

600
500
400
300
200
100
200

400

600

800
Time

1000

1200

1400

200

180

Item

160

140

120

100
1300

1350

1400

1450

1500

1550

Time

Figure 6: Event sequences in the ‘science’ data set with the estimated results of influence between events.
(a) item indices 1 to 1000 and time 100 to 1559, and (b) its zoom of item indices 100 to 200 and time 1300
to 1559. Here, ‘x’ represents an event that is caused by the background intensity, ‘o’ represents an eventthat is triggered by the preceding event, and in that case the triggered event is indicated by a curved line
connected between them.

2
1.8
1.6

alpha

1.4
1.2
1
0.8
0.6
0.4
0.2
500

1000

1500

2000

2500

3000

3500

4000

4500

user

(a) Influence {αu }u∈U
8
7
6

alpha

5
4
3
2
1

0.5

1

1.5

2

2.5

3

3.5

item

4

4.5
4

x 10

(b) Popularity {αi }i∈I
Figure 8: Estimated user influence (a), and item
popularity (b) in the ‘science’ data set. User anditem indices are sorted by their values.

[18] M. Katagiri and M. Etoh. Social influence modelingon smartphone usage. Advanced Data Mining andApplications, pages 292–303, 2011.
[19] N. Kawamae, H. Sakano, and T. Yamada. Personalizedrecommendation based on the personal innovator
degree. In Proceedings of the 3rd ACM Conference on
Recommender systems, pages 329–332. ACM, 2009.
[20] J. F. C. Kingman. Poisson processes, volume 3.
Oxford University Press, USA, 1993.
[21] J. Leskovec, L. A. Adamic, and B. A. Huberman. The
dynamics of viral marketing. ACM Transactions on
the Web (TWEB), 1(1):5, 2007.
[22] D. Lin, E. Grimson, and J. Fisher. Construction of
dependent Dirichlet processes based on Poissonprocesses. In Advances in Neural Information
Processing Systems, 2010.
[23] T. Matsubayashi and T. Yamada. A force-directed
graph drawing based on the hierarchical individual
timestep method. International Journal of Electronics,
Circuits and Systems, 1(2):116–121, 2007.
[24] T. Minka. Estimating a Dirichlet distribution, 2000.
[25] S. A. Myers and J. Leskovec. On the convexity oflatent social network inference. In Advances in Neural
Information Processing Systems, 2010.
[26] S. A. Myers, C. Zhu, and J. Leskovec. Information
diffusion and external influence in networks. In KDD’12, pages 33–41, 2012.

[27] R. Pasupathy. Generating Poisson arrival streams.
Wiley Encyclopedia of Operations Research andManagement Science, 2009.
[28] M. Richardson and P. Domingos. Mining
knowledge-sharing sites for viral marketing. In KDD’02, pages 61–70, 2002.
[29] K. Saito, M. Kimura, K. Ohara, and H. Motoda.
Learning continuous-time information diffusion model
for social behavioral data analysis. Advances in
Machine Learning, pages 322–337, 2009.
[30] A. Simma and M. I. Jordan. Modeling events withcascades of Poisson processes. In UAI: Proceedings ofthe 26th Conference on Uncertainty in Artificial
Intelligence, pages 546–555, 2010.
[31] X. Song, Y. Chi, K. Hino, and B. L. Tseng.
Information flow modeling based on diffusion rate forprediction and ranking. In Proceedings of the 16th
international conference on World Wide Web, WWW’07, pages 191–200, 2007.
[32] X. Song, B. L. Tseng, C.-Y. Lin, and M.-T. Sun.
Personalized recommendation driven by information
flow. In Proceedings of the 29th Annual International
ACM SIGIR Conference on Research andDevelopment in Information Retrieval, SIGIR ’06,
pages 509–516, New York, NY, USA, 2006. ACM.
[33] R. Wetzker, C. Zimmermann, and C. Bauckhage.
Analyzing social bookmarking systems: A del. icio. us
cookbook. In Proceedings of the ECAI 2008 Mining
Social Data Workshop, pages 26–30, 2008.
[34] M. Xia, Y. Huang, W. Duan, and A. B. Whinston.
Ballot box communication in online communities.
Commun. ACM, 52(9):138–142, Sept. 2009.
[35] J. Yang and J. Leskovec. Modeling information
diffusion in implicit networks. In IEEE 10th
International Conference on Data Mining (ICDM),
pages 599–608. IEEE, 2010.

APPENDIXA.

ESTIMATING DECAY PARAMETER

This appendix describes the first and second derivativesof the joint likelihood (14) with regard to decay parameterγ, which are required for estimating the decay parameterbased on Newton’s method. The first derivative of S(γ) is
given byX X
∂S(γ)(tin − tizin )=−∂γi∈I n:zin 6=0«
X Mu + a „ Au
(29)−
+ A′u ,−
Au + γbγu∈Uand the second derivative of S is given by«
X Mu + a „ ′′ „ Au
∂ 2 S(γ)
′
=
−
+
A
A
+
−
u
u
∂γ 2
Au + γb
γ
u∈U
„ ′
««
Au + b1
×+,(30)
Au + γbγ`´
P
where Au = γCu , A′u = − t∈D u exp −γ(T − t) (T − t),`´Pand A′′u = t∈D u exp −γ(T − t) (T − t)2 .