Statistics
| Branch: | Revision:

root / latex / note_w01.tex @ b56a7ca2

 1 %!TEX root = note.tex  %%%%%%%%%%%%%%%%%%  % WEEK 1  %%%%%%%%%%%%%%%%%%  \section{Week 1}   \subsection{Brandes 2001}   \subsubsection{Counting the number of shortest paths}   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}   \textbf{Floyd/Warshall algorithm}   \subsubsection{Code for shortest-path betweenness centrality}   https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality/betweenness.py   Line 116   \begin{itemize}   \item S: all nodes belonging to some shortest path from \lstinline{s}   \item P: predecessors. \lstinline{P[w]} is the list of predecessors of vertex w, when starting from source \lstinline{s}   \item sigma: the number of shortest paths. \lstinline{sigma[w]} is the number of shortest paths from \lstinline{s} to \lstinline{w}   \end{itemize}   $c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}$   \textbf{How accumulate_basic works?}   \begin{lstlisting}  # accumulate_basic()  delta = dict.fromkeys(S, 0)  while S:   w = S.pop()   coeff = (1.0 + delta[w]) / sigma[w]   for v in P[w]:   delta[v] += sigma[v] * coeff   \end{lstlisting}   \begin{table}[h]   \label{paper_networkx_variable_mapping}   \caption{Mapping variables between the paper and the networkx code}   \begin{tabular}{c|c|p{11cm}}   \toprule   Paper & Networkx & Meaning \\   \hline   $s$ & s & the \texttt{source vertex} \\   $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$ \\   ... & {\lstinline!S!} & a list of vertex $w$ that satisfies $w$ is any vertex with $v \in P_s(w)$ \\   ??? & w & a vertex from a list $S$ \\   $P_s(w)$ & & the predecessor of a \texttt{middle vertex} on the shortest path from \texttt{source vertex} \\   $\delta_{s.}(v)$ & {\lstinline!delta[v]!} & the \texttt{dependency} of a source vertex $s$ on a single vertex $v$ \\   $\delta_{s.}(w)$ & {\lstinline!delta[w]!} & the \texttt{dependency} of a source vertex $s$ on a single vertex \\   $\sigma_{sv}$ & {\lstinline!sigma[v]!} & the number of shortest paths from $s$ to $v$ \\   $\sigma_{sw}$ & {\lstinline!sigma[w]!} & the number of shortest paths from $s$ to $w$ \\   .. & {\lstinline!betweenness[w]!} & \textbf{???} It's not really match with $\delta_{s.}(v)$ \\   \end{tabular}   \end{table}   \subsubsection{Output of Brandes from networkx}   \begin{lstlisting}  vertices = [u'5', u'u', u'6']  xxx _single_source_shortest_path  5  [u'5', u'u', u'6']  {u'u': [u'5'], u'5': [], u'6': [u'5']}  {u'u': 1.0, u'5': 1.0, u'6': 1.0}  w = 6  delta = {u'u': 0, u'5': 1.0, u'6': 0}  betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}  w = u  delta = {u'u': 0, u'5': 2.0, u'6': 0}  betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}  w = 5  delta = {u'u': 0, u'5': 2.0, u'6': 0}  xxx _single_source_shortest_path  u  [u'u', u'5', u'6']  {u'u': [], u'5': [u'u'], u'6': [u'u']}  {u'u': 1.0, u'5': 1.0, u'6': 1.0}  w = 6  delta = {u'5': 0, u'u': 1.0, u'6': 0}  betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}  w = 5  delta = {u'5': 0, u'u': 2.0, u'6': 0}  betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}  w = u  delta = {u'5': 0, u'u': 2.0, u'6': 0}  xxx _single_source_shortest_path  6  [u'6', u'u', u'5']  {u'u': [u'6'], u'5': [u'6'], u'6': []}  {u'u': 1.0, u'5': 1.0, u'6': 1.0}  w = 5  delta = {u'5': 0, u'u': 0, u'6': 1.0}  betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}  w = u  delta = {u'5': 0, u'u': 0, u'6': 2.0}  betweenness = {u'u': 0.0, u'5': 0.0, u'6': 0.0}  w = 6  delta = {u'5': 0, u'u': 0, u'6': 2.0}  nodes =  vertices = [u'1', u'3', u'2', u'u', u'4', u'v']  vertices = [u'1', u'3', u'2', u'u', u'4', u'v']  xxx _single_source_shortest_path  1  [u'1', u'3', u'2', u'u', u'4', u'v']  {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']}  {u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 1.0, u'4': 2.0, u'v': 2.0}  w = v  delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}  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}  w = 4  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = u  delta = {u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = 2  delta = {u'1': 3.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = 3  delta = {u'1': 5.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = 1  delta = {u'1': 5.0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  xxx _single_source_shortest_path  3  [u'3', u'1', u'u', u'4', u'v', u'2']  {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']}  {u'1': 1.0, u'3': 1.0, u'2': 4.0, u'u': 1.0, u'4': 1.0, u'v': 1.0}  w = 2  delta = {u'1': 0.25, u'3': 0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = v  delta = {u'1': 0.25, u'3': 1.25, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = 4  delta = {u'1': 0.25, u'3': 2.5, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = u  delta = {u'1': 0.25, u'3': 3.75, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = 1  delta = {u'1': 0.25, u'3': 5.0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = 3  delta = {u'1': 0.25, u'3': 5.0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  xxx _single_source_shortest_path  2  [u'2', u'1', u'u', u'4', u'v', u'3']  {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']}  {u'1': 1.0, u'3': 4.0, u'2': 1.0, u'u': 1.0, u'4': 1.0, u'v': 1.0}  w = 3  delta = {u'1': 0.25, u'3': 0, u'2': 0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = v  delta = {u'1': 0.25, u'3': 0, u'2': 1.25, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = 4  delta = {u'1': 0.25, u'3': 0, u'2': 2.5, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = u  delta = {u'1': 0.25, u'3': 0, u'2': 3.75, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = 1  delta = {u'1': 0.25, u'3': 0, u'2': 5.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  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}  w = 2  delta = {u'1': 0.25, u'3': 0, u'2': 5.0, u'u': 0.25, u'4': 0.25, u'v': 0.25}  xxx _single_source_shortest_path  u  [u'u', u'1', u'3', u'2', u'4', u'v']  {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']}  {u'1': 1.0, u'3': 1.0, u'2': 1.0, u'u': 1.0, u'4': 2.0, u'v': 2.0}  w = v  delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}  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}  w = 4  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = 2  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 0, u'v': 0}  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}  w = 3  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 4.0, u'4': 0, u'v': 0}  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}  w = 1  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 5.0, u'4': 0, u'v': 0}  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}  w = u  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 5.0, u'4': 0, u'v': 0}  xxx _single_source_shortest_path  4  [u'4', u'3', u'2', u'v', u'1', u'u']  {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']}  {u'1': 2.0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 1.0, u'v': 1.0}  w = u  delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}  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}  w = 1  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = v  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 1.0, u'v': 0}  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}  w = 2  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 3.0, u'v': 0}  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}  w = 3  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 5.0, u'v': 0}  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}  w = 4  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 5.0, u'v': 0}  xxx _single_source_shortest_path  v  [u'v', u'3', u'2', u'4', u'1', u'u']  {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': []}  {u'1': 2.0, u'3': 1.0, u'2': 1.0, u'u': 2.0, u'4': 1.0, u'v': 1.0}  w = u  delta = {u'1': 0, u'3': 0.5, u'2': 0.5, u'u': 0, u'4': 0, u'v': 0}  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}  w = 1  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 0}  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}  w = 4  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 1.0}  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}  w = 2  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 3.0}  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}  w = 3  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 5.0}  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}  w = v  delta = {u'1': 0, u'3': 1.0, u'2': 1.0, u'u': 0, u'4': 0, u'v': 5.0}   \end{lstlisting}