## 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