P1: Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-08 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:22
8.2 Influence 231Algorithm 8.1Linear Threshold Model (LTM)
Require:GraphG(V,E), set of initial activated nodesA 0
1: return Final set of activated nodesA∞
2: i=0;
3: Uniformly assign random thresholdsθvfrom the interval [0, 1];
4: whilei=0or(Ai− 1 =Ai,i≥1)do
5: Ai+ 1 =Ai
6: inactive=V−Ai;
7: for allv∈inactivedo
8: if∑
jconnected tov,j∈Aiwj,v≥θv.then
9: activatev;
10: Ai+ 1 =Ai+ 1 ∪{v};
11: end if
12: end for
13: i=i+1;
14: end while
15: A∞=Ai;
16: ReturnA∞;are fixed, the process is deterministic and will always converge to the same
state.Example 8.3.Consider the graph in Figure8.5. Values attached to nodes
represent the LTM thresholds, and edge values represent the weights. At time
0, nodev 1 is activated. At time 2, both nodesv 2 andv 3 receive influence
from nodev 1. Nodev 2 is not activated since 0.5<0.8 and nodev 3 is
activated since 0.8>0.7. Similarly, the process continues and then stops
with five activated nodes.Modeling Influence in Implicit Networks
An implicit network is one where the influence spreads over edges in
the network; however, unlike the explicit model, we cannot observe the
individuals (the influentials) who are responsible for influencing others, but
only those who get influenced. In other words, the information available
is the set of influenced populationP(t) at any time and the timetu, when
each individualugets initially influenced (activated). We assume that any
influenced individualucan influenceI(u,t) number of non-influenced
(inactive) individuals afterttime steps. We callI(., .) the influence function.