Statistics
| Branch: | Revision:

root / latex / note_w01.tex @ b56a7ca2

History | View | Annotate | Download (10.9 KB)

1
%!TEX root = note.tex
2

    
3
%%%%%%%%%%%%%%%%%%
4
% WEEK 1
5
%%%%%%%%%%%%%%%%%%
6
\section{Week 1}
7
    \subsection{Brandes 2001}
8
        \subsubsection{Counting the number of shortest paths}
9
            Explanation on k-th power of the adjacency matrix equals the number of paths from vertex \texttt{u} to vertex \texttt{v} \footnote{https://www.quora.com/What-is-an-intuitive-explanation-for-why-raising-an-adjacency-matrix-to-the-power-of-n-gives-a-new-matrix-with-the-number-of-n-paths}
10

    
11
            \textbf{Floyd/Warshall algorithm}
12

    
13
        \subsubsection{Code for shortest-path betweenness centrality}
14
            https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality/betweenness.py
15

    
16
            Line 116
17
            \begin{itemize}
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
            \end{itemize}
22

    
23
            $c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}$
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