what-when-how
In Depth Tutorials and Information
Independent Cascade Model
: Whenever a social contact
ν ∈ Γ
(
u
) (
Γ
(
u
) is the
set of the neighbors of node
u
) of a node
u
adopts an innovation, it does so with a
probability
P
v
,u
. he process of the independent cascade model can be described as
follows. Starting with an initial set of active nodes
A
0
, the process unfolds in dis-
crete steps according to the following randomized rule. When node
v
first becomes
active in step
t
, it is given a single chance to activate each currently inactive neigh-
bor
u
; it succeeds with a probability
P
v
,u
(a parameter of the system) independently
of the history thus far. (If
u
has multiple newly activated neighbors, their attempts
are sequenced in an arbitrary order.) If
v
succeeds, then
u
will become active in
step
t
+ 1; but whether or not
v
succeeds, it cannot make any further attempts to
activate
u
in subsequent rounds. Again, the process runs until no more activation
is possible.
Linear hreshold Model:
Each node
u
in the network chooses a threshold
θ
u
∈ [0,1]
, typically drawn from a probability distribution. Every neighbor
v
of
u
has a nonnegative connection weight
w
u,v
so that
Σ
Γ
≤
w
1
and
u
adopts a
∈
v
(
u
)
u v
,
threshold if and only if
Σ
( ) ,
θ
. Given a random choice of thresholds
and an initial set of active nodes
A
0
(with all other nodes inactive), the diffusion
process unfolds deterministically in discrete steps: in step
t
, all nodes that were
active in step
t
− 1 remain active, and we activate any node
u
for which the total
weight of its active neighbors is at least
θ
u
.
Based on the independent cascade model, Gruhl et al. [44] proposed a model
to predict the tendency of users' posting behaviors in a blogosphere, on an
assumption that users do not write multiple postings on the topic. Given a set of
N
nodes, at the initial state of each episode a possibly empty set of nodes has writ-
ten about the topic. At each successive state, a possibly empty set of authors write
about the topic. he process will end when no new articles appear for a number
of time steps.
Under the independent cascade model, users are connected by a directed graph
where each edge (
v
,
w
) is labeled with a copy probability
k
v,w
. When author
v
writes
an article at time
t
, each node
w
that has an arc from
v
to
w
writes an article about
the topic at time
t
+ 1 with probability
k
v,w
. his inluence is independent of the
history of whether any other neighbors of
w
have written on the topic.
Note that a user may visit certain blogs frequently and other blogs infrequently.
herefore, an additional edge parameter
r
u,v
is added to denote the probability that
u
reads
v
's blog on any given day. Formally, propagation in the model occurs as fol-
lows. If a topic exists at vertex
v
on a given day, then the model computes the prob-
ability that the topic will propagate from
v
to a neighboring vertex
u
, which occurs
as follows. Node
u
reads the topic from node
v
on any given day with reading prob-
ability
r
u,v
, so a delay is chosen from an exponential distribution with parameter
r
u,v
. hen, with probability
k
u,v
, the author of
u
will choose to write about it. If
u
reads the topic and chooses not to copy it, then
u
will never copy that topic from
v
; there is only a single opportunity for a topic to propagate along any given edge.
Alternatively, one may imagine that once
v
is infected, node
u
will become infected
w
≥
adopters v
∈
Γ
u
u v
u
