what-when-how
In Depth Tutorials and Information
where
I
is the identity matrix. he solution is
∞
∑
0
(
tQ
m
)
!
m
P t
( )
=
e
tQ
=
(3.32)
m
=
If
Q
can be diagonalized by
Q
=
MDM
−1
, then
∞
∑
M tD M
m
(
)
m
−
1
=
=
1
(3.33)
P t
( )
Me M
tD
−
!
=
m
0
For large
Q
, the Taylor approximation can also be used:
m
⎛
⎜
I Q
t
m
⎞
⎟
(3.34)
P t
( )
≈
lim
+
m
→∞
3.3.2.4 Ranking Algorithm
Similarly, we assume that we are given the user adoption data as described in Section
4.3. For the ranking problem, we pose the problem that, if an arbitrary user
j
(
j
≠
i
)
adopts an item at
t
= 0, when will be the average time in which user
i
adopts it? In
CTMC, this question can be answered by the mean first-passage time.
Let
M
be the first-passage time matrix of the CTMC with the (
i
,
j
)-th element as
m
ij
. he mean irst passage time
m
ij
from
i
to
j
is defined as the expected time taken
until first arrival at node
j
, starting at node
i
.
Let
v
be any constant such that v ≥ max
i
(
q
i
). Divide the off-diagonal compo-
nents of
Q
(
q
i
P
ij
(
i
≠
j
) ) by
v
and replace its diagonal components −
q
i
by 1 −
q
i
/
v
. We
then have a uniformized chain (discrete time) whose transition matrix
P
v
can be
related to
.Q
though
v
as follows:
v
= +
1
(3.35)
P
I
v
Q
Let
M
λ
denote the matrix of the first-passage time of the uniformized chain (dis-
crete time). he mean irst-passage time matrix of DTMC is given by
(
)
(3.36)
=
−
+
M
I Z
E Z
(
)
D
v
v
v dg
where
I
is the identity matrix,
E
is a matrix containing all ones, and
D
is the diago-
nal matrix with elements
d
ii
=
1/ ( )
π
where
π
(
i
) is the steady-state distribution of
node
I
in this DTMC, and
Z
v
is its fundamental matrix, with
i
(
∞
−
1
Z
=
I
−
P
+
P
(3.37)
v
v
v
