Revision b56a7ca2 latex/note_w01.tex

View differences:

latex/note_w01.tex
15 15

  
16 16
            Line 116
17 17
            \begin{itemize}
18
            \item S
19
            \item P
20
            \item sigma
18
                \item S: all nodes belonging to some shortest path from \lstinline{s}
19
                \item P: predecessors. \lstinline{P[w]} is the list of predecessors of vertex w, when starting from source \lstinline{s}
20
                \item sigma: the number of shortest paths. \lstinline{sigma[w]} is the number of shortest paths from \lstinline{s} to \lstinline{w}
21 21
            \end{itemize}
22 22

  
23 23
            $c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}$
24 24

  
25
            \textbf{How accumulate_basic works?}
26
            \begin{lstlisting}
27
# accumulate_basic()
28
delta = dict.fromkeys(S, 0)
29
while S:
30
    w = S.pop()
31
    coeff = (1.0 + delta[w]) / sigma[w]
32
    for v in P[w]:
33
        delta[v] += sigma[v] * coeff
34
            \end{lstlisting}
35

  
36
            \begin{table}[h]
37
                \label{paper_networkx_variable_mapping}
38
                \caption{Mapping variables between the paper and the networkx code}
39
                \begin{tabular}{c|c|p{11cm}}
40
                    \toprule
41
                    Paper & Networkx & Meaning \\
42
                    \hline
43
                    $s$ & s & the \texttt{source vertex} \\
44

  
45
                    $t$ & ... & the \texttt{target vertex}. \textbf{???} Maybe it doesn't have the equivalent variable in the code. Since we only need to calculate the dependency of vertex $s$ on a single vertex $v$, rather than the \texttt{pair-dependency} of a pair $s, t$ on an intermediary $v$ \\
46

  
47
                    ... & {\lstinline!S!} & a list of vertex $w$ that satisfies $w$ is any vertex with $v \in P_s(w)$ \\
48

  
49
                    ??? & w & a vertex from a list $S$ \\
50

  
51
                    $P_s(w)$ &  & the predecessor of a \texttt{middle vertex} on the shortest path from \texttt{source vertex} \\
52

  
53
                    $\delta_{s.}(v)$ & {\lstinline!delta[v]!} & the \texttt{dependency} of a source vertex $s$ on a single vertex $v$ \\
54

  
55
                    $\delta_{s.}(w)$ & {\lstinline!delta[w]!} & the \texttt{dependency} of a source vertex $s$ on a single vertex \\
56

  
57
                    $\sigma_{sv}$ & {\lstinline!sigma[v]!} & the number of shortest paths from $s$ to $v$ \\
58

  
59
                    $\sigma_{sw}$ & {\lstinline!sigma[w]!} & the number of shortest paths from $s$ to $w$ \\
60

  
61
                    .. & {\lstinline!betweenness[w]!} & \textbf{???} It's not really match with $\delta_{s.}(v)$ \\
62

  
63
                \end{tabular}
64
            \end{table}
65

  
66
        \subsubsection{Output of Brandes from networkx}
67
            \begin{lstlisting}
68
vertices = [u'5', u'u', u'6']
69

  
70
xxx _single_source_shortest_path
71
5
72
[u'5', u'u', u'6']
73
{u'u': [u'5'], u'5': [], u'6': [u'5']}
74
{u'u': 1.0, u'5': 1.0, u'6': 1.0}
75
w = 6
76
delta = {u'u': 0, u'5': 1.0, u'6': 0}
77
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
78
w = u
79
delta = {u'u': 0, u'5': 2.0, u'6': 0}
80
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
81
w = 5
82
delta = {u'u': 0, u'5': 2.0, u'6': 0}
83

  
84
xxx _single_source_shortest_path
85
u
86
[u'u', u'5', u'6']
87
{u'u': [], u'5': [u'u'], u'6': [u'u']}
88
{u'u': 1.0, u'5': 1.0, u'6': 1.0}
89
w = 6
90
delta = {u'5': 0, u'u': 1.0, u'6': 0}
91
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
92
w = 5
93
delta = {u'5': 0, u'u': 2.0, u'6': 0}
94
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
95
w = u
96
delta = {u'5': 0, u'u': 2.0, u'6': 0}
97

  
98
xxx _single_source_shortest_path
99
6
100
[u'6', u'u', u'5']
101
{u'u': [u'6'], u'5': [u'6'], u'6': []}
102
{u'u': 1.0, u'5': 1.0, u'6': 1.0}
103
w = 5
104
delta = {u'5': 0, u'u': 0, u'6': 1.0}
105
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
106
w = u
107
delta = {u'5': 0, u'u': 0, u'6': 2.0}
108
betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}
109
w = 6
110
delta = {u'5': 0, u'u': 0, u'6': 2.0}
111
nodes =
112
vertices = [u'1', u'3', u'2', u'u', u'4', u'v']
113

  
114

  
115
vertices = [u'1', u'3', u'2', u'u', u'4', u'v']
116

  
117
xxx _single_source_shortest_path
118
1
119
[u'1', u'3', u'2', u'u', u'4', u'v']
120
{u'1': [], u'3': [u'1'], u'2': [u'1'], u'u': [u'1'], u'4': [u'3', u'2'], u'v': [u'3', u'2']}
121
{u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 1.0, u'4': 2.0, u'v': 2.0}
122
w = v
123
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
124
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 0.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
125
w = 4
126
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
127
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 0.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
128
w = u
129
delta = {u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
130
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 0.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
131
w = 2
132
delta = {u'1': 3.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
133
betweenness = {u'1': 0.0, u'3': 0.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
134
w = 3
135
delta = {u'1': 5.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
136
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
137
w = 1
138
delta = {u'1': 5.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
139

  
140
xxx _single_source_shortest_path
141
3
142
[u'3', u'1', u'u', u'4', u'v', u'2']
143
{u'1': [u'3'], u'3': [], u'2': [u'1', u'u', u'4', u'v'], u'u': [u'3'], u'4': [u'3'], u'v': [u'3']}
144
{u'1': 1.0, u'3': 1.0, u'2': 4.0, u'u': 1.0, u'4': 1.0, u'v': 1.0}
145
w = 2
146
delta = {u'1': 0.25, u'3': 0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
147
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.0}
148
w = v
149
delta = {u'1': 0.25, u'3': 1.25, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
150
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.0, u'v': 0.25}
151
w = 4
152
delta = {u'1': 0.25, u'3': 2.5, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
153
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.0, u'4': 0.25, u'v': 0.25}
154
w = u
155
delta = {u'1': 0.25, u'3': 3.75, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
156
betweenness = {u'1': 0.0, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
157
w = 1
158
delta = {u'1': 0.25, u'3': 5.0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
159
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
160
w = 3
161
delta = {u'1': 0.25, u'3': 5.0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
162

  
163
xxx _single_source_shortest_path
164
2
165
[u'2', u'1', u'u', u'4', u'v', u'3']
166
{u'1': [u'2'], u'3': [u'1', u'u', u'4', u'v'], u'2': [], u'u': [u'2'], u'4': [u'2'], u'v': [u'2']}
167
{u'1': 1.0, u'3': 4.0, u'2': 1.0, u'u': 1.0, u'4': 1.0, u'v': 1.0}
168
w = 3
169
delta = {u'1': 0.25, u'3': 0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
170
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
171
w = v
172
delta = {u'1': 0.25, u'3': 0, u'2': 1.25, u'u': 0.25, u'4': 0.25, u'v': 0.25}
173
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.25, u'v': 0.5}
174
w = 4
175
delta = {u'1': 0.25, u'3': 0, u'2': 2.5, u'u': 0.25, u'4': 0.25, u'v': 0.25}
176
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.25, u'4': 0.5, u'v': 0.5}
177
w = u
178
delta = {u'1': 0.25, u'3': 0, u'2': 3.75, u'u': 0.25, u'4': 0.25, u'v': 0.25}
179
betweenness = {u'1': 0.25, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
180
w = 1
181
delta = {u'1': 0.25, u'3': 0, u'2': 5.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
182
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
183
w = 2
184
delta = {u'1': 0.25, u'3': 0, u'2': 5.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}
185

  
186
xxx _single_source_shortest_path
187
u
188
[u'u', u'1', u'3', u'2', u'4', u'v']
189
{u'1': [u'u'], u'3': [u'u'], u'2': [u'u'], u'u': [], u'4': [u'3', u'2'], u'v': [u'3', u'2']}
190
{u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 1.0, u'4': 2.0, u'v': 2.0}
191
w = v
192
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
193
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
194
w = 4
195
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
196
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 1.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
197
w = 2
198
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 0, u'v': 0}
199
betweenness = {u'1': 0.5, u'3': 1.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
200
w = 3
201
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 4.0, u'4': 0, u'v': 0}
202
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
203
w = 1
204
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 5.0, u'4': 0, u'v': 0}
205
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
206
w = u
207
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 5.0, u'4': 0, u'v': 0}
208

  
209
xxx _single_source_shortest_path
210
4
211
[u'4', u'3', u'2', u'v', u'1', u'u']
212
{u'1': [u'3', u'2'], u'3': [u'4'], u'2': [u'4'], u'u': [u'3', u'2'], u'4': [], u'v': [u'4']}
213
{u'1': 2.0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 1.0, u'v': 1.0}
214
w = u
215
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
216
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
217
w = 1
218
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
219
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
220
w = v
221
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 1.0, u'v': 0}
222
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 2.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
223
w = 2
224
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 3.0, u'v': 0}
225
betweenness = {u'1': 0.5, u'3': 2.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
226
w = 3
227
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 5.0, u'v': 0}
228
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
229
w = 4
230
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 5.0, u'v': 0}
231

  
232
xxx _single_source_shortest_path
233
v
234
[u'v', u'3', u'2', u'4', u'1', u'u']
235
{u'1': [u'3', u'2'], u'3': [u'v'], u'2': [u'v'], u'u': [u'3', u'2'], u'4': [u'v'], u'v': []}
236
{u'1': 2.0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 1.0, u'v': 1.0}
237
w = u
238
delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}
239
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
240
w = 1
241
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}
242
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
243
w = 4
244
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 1.0}
245
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 3.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
246
w = 2
247
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 3.0}
248
betweenness = {u'1': 0.5, u'3': 3.0, u'2': 4.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
249
w = 3
250
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 5.0}
251
betweenness = {u'1': 0.5, u'3': 4.0, u'2': 4.0, u'u': 0.5, u'4': 0.5, u'v': 0.5}
252
w = v
253
delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 5.0}
254

  
255
            \end{lstlisting}
256

  
257

  
258

  
259

  

Also available in: Unified diff