Databases Reference
In-Depth Information
ComputeWAndSValues(G:Propagation Graph,X
src
;X
san
;X
snk
: Set of Nodes)
Precondition:
Inputs:
Acyclic propagation graphG, sets of nodesX
src
;X
san
;X
snk
representing potential
sources, potential sanitizers and potential sinks respectively
Returns:
W(n) ands(n) for each potential sanitizerninG
1:
for each potential sourcen2X
src
do
2:
F(n) := initial probability ofnbeing a source node
3:
F
total
(n) := 1
4:
end for
5:
for each potential sanitizern2X
san
in topological order do
6:
F(n) := 0
7:
F
total
(n) := 0
8:
for eachm2Vsuch that (m;n) 2Edo
9:
F(n) :=F(n) +F(m)
10:
F
total
(n) :=F
total
(n) +F
total
(m)
11:
end for
12:
end for
13:
for each potential sinkn2X
snk
do
14:
B(n) := initial probability ofnbeing a sink node
15:
B
total
(n) := 1
16:
end for
17:
for each potential sanitizern2X
san
in reverse topological order do
18:
B(n) := 0
19:
B
total
(n) := 0
20:
for eachm2Vsuch that (n;m) 2Edo
21:
B(n) :=B(n) +B(m)
22:
B
total
(n) :=B
total
(n) +B
total
(m)
23:
end for
24:
end for
25:
for each potential sanitizern2X
san
do
26:
W(n) :=F(n) B(n)
27:
s(n) :=
W(n)
F
total
(n)B
total
(n)
28:
end for
29:
returns
FIGURE 11.6: Computing W(n) and s(n).
11.4.1 Computing s() and W()
Recall values s() and W() defined in Section 11.2.4. Figure 11.6 describes
ComputeWAndSValues, which computes s(n) for each potential sanitizer node,
given input probabilities for each potential source and each potential sink.
The value s(n) for each potential sanitizer n is the ratio of the sum of
weighted source-sink paths that go through n and the total number of paths
that go through n. The algorithm computes W(n) and s(n) by computing
four numbers F(n), F
total
(n), B(n), and B
total
(n).
F(n) denotes the total number of sources that can reach n, and F
total
(n)
denotes the total number of paths that can reach n. B(n) denotes the total
number of sinks that can be reached from n. Finally, B
total
(n) denotes the
total number of paths that can be reached from n.
For each potential source n, we set F(n) to an initial value in line 2 (in
our implementation, we picked an initial value of 0.5), and we set F
total
(n)
to 1 in line 3. For each potential sink, we set B(n) to some initial value in
Search WWH ::
Custom Search