## root / latex / report_dec_20.tex @ 50aa86a1

History | View | Annotate | Download (9.44 KB)

1 |
% http://www.ams.jhu.edu/~ers/learn-latex/ |
---|---|

2 | |

3 |
\documentclass[12pt]{article} |

4 |
% This first part of the file is called the PREAMBLE. It includes |

5 |
% customizations and command definitions. The preamble is everything |

6 |
% between \documentclass and \begin{document}. |

7 | |

8 |
\usepackage[margin=1in]{geometry} % set the margins to 1in on all sides |

9 |
\usepackage{graphicx} % to include figures |

10 |
\graphicspath{ {report_images/} } % '/' is needed |

11 |
\usepackage[noabbrev,capitalise]{cleveref} |

12 |
\usepackage{amsmath} % great math stuff |

13 |
\usepackage{amsfonts} % for blackboard bold, etc |

14 |
\usepackage{amsthm} % better theorem environments |

15 |
\usepackage{listings} % to add code |

16 |
\lstset{language=Java} |

17 |
\renewcommand{\lstlistingname}{Code} % change "Listing 1.1" to "Code 1.1" |

18 | |

19 |
\usepackage[utf8]{inputenc} |

20 |
\usepackage{color} |

21 | |

22 |
\usepackage{cite} |

23 | |

24 |
\usepackage[colorlinks]{hyperref} % from http://tex.stackexchange.com/questions/3568/how-does-one-typeset-a-url |

25 |
\hypersetup{citecolor=green} |

26 |
\hypersetup{linkcolor=red} |

27 |
\hypersetup{urlcolor=blue} |

28 |
\usepackage{cleveref} |

29 | |

30 |
\definecolor{codegreen}{rgb}{0,0.6,0} |

31 |
\definecolor{codegray}{rgb}{0.5,0.5,0.5} |

32 |
\definecolor{codepurple}{rgb}{0.58,0,0.82} |

33 |
\definecolor{backcolour}{rgb}{0.95,0.95,0.92} |

34 | |

35 |
\lstdefinestyle{mystyle}{ |

36 |
backgroundcolor=\color{backcolour}, |

37 |
commentstyle=\color{codegreen}, |

38 |
keywordstyle=\color{magenta}, |

39 |
numberstyle=\tiny\color{codegray}, |

40 |
stringstyle=\color{codepurple}, |

41 |
basicstyle=\footnotesize, |

42 |
breakatwhitespace=false, |

43 |
breaklines=true, |

44 |
captionpos=b, |

45 |
keepspaces=true, |

46 |
numbers=left, |

47 |
numbersep=5pt, |

48 |
showspaces=false, |

49 |
showstringspaces=false, |

50 |
showtabs=false, |

51 |
tabsize=2 |

52 |
} |

53 | |

54 |
\lstset{style=mystyle} |

55 |
\DeclareMathOperator{\id}{id} |

56 | |

57 |
\newcommand{\bd}[1]{\mathbf{#1}} % for bolding symbols |

58 |
\newcommand{\RR}{\mathbb{R}} % for Real numbers |

59 |
\newcommand{\ZZ}{\mathbb{Z}} % for Integers |

60 |
\newcommand{\col}[1]{\left[\begin{matrix} #1 \end{matrix} \right]} |

61 |
\newcommand{\comb}[2]{\binom{#1^2 + #2^2}{#1+#2}} |

62 | |

63 |
\usepackage[T1]{fontenc} |

64 |
\AtBeginDocument{% |

65 |
\begingroup\lccode`~=`_% |

66 |
\lowercase{\endgroup\let~}_% |

67 |
\catcode`_=12 |

68 |
} |

69 | |

70 |
\usepackage{booktabs} % To thicken table lines |

71 | |

72 |
\begin{document} |

73 | |

74 |
\title{Thesis - Report Dec 20 - Heuristic Betweenness by using biconnected components} |

75 | |

76 |
\author{Quynh Nguyen - DISI - University of Trento} |

77 | |

78 |
\maketitle |

79 |
\clearpage |

80 | |

81 |
\section{Bugs in calculating the Component Tree Weight (or Link Weight)} |

82 | |

83 |
As Leonardo, I checked again how I calculate the Link Weight for the Component Tree. |

84 | |

85 |
\textbf{Version 1:} the exactl Algorithm 1 as in \cite{PuzisZEDB12}. But the result is wrong when I test with the graph in the paper. |

86 | |

87 |
Line 6-12 execute the case of Eq. 15 in \cite{PuzisZEDB12}. This is the case when the component has only 1 unknown link weight. |

88 | |

89 |
Line 14-19 performs the equation. 14 in \cite{PuzisZEDB12}, for when the cutpoint has exactly 1 unknown link weight. |

90 | |

91 | |

92 |
\textbf{Version 2:} modifying the Algorithm 1 in 2 places: |

93 |
\begin{itemize} |

94 |
\item line 9: It will be $size \leftarrow size + |V| - D^{n(}_{B} - 1$ |

95 |
\item line 15: \(size \leftarrow 0\). The $size$ is the sum part in Eq. 14 in \cite{PuzisZEDB12}. According to the equation, the initial value of the sum must be 0, not 1. |

96 |
\end{itemize} |

97 | |

98 |
Below is the result for the size of \textbf{cut with B}, or the $D^{u()}_{B}$. From left to right, it denotes the \lstinline{cut with B} for component $A, B, C, D, E$, respectively. |

99 | |

100 |
\begin{lstlisting} |

101 |
# Wrong result - from Version 1 |

102 |
[{u'u': 2}, {u'u': 7, u'v': 9}, {u'v': 1}, {u'v': 1}, {u'v': 1}] |

103 | |

104 |
# Correct result for the size of [cut with B] - Version 2 - I obtained the result by manually work with the graph, and then check the output from the algorithm |

105 |
[{u'u': 2}, {u'u': 8, u'v': 7}, {u'v': 1}, {u'v': 1}, {u'v': 1}] |

106 |
\end{lstlisting} |

107 | |

108 |
\begin{lstlisting} |

109 |
Component A : {u'u': 2} |

110 |
Component B: {u'u': 7, u'v': 9} |

111 |
Component C: {u'v': 1} |

112 |
Component D: {u'v': 1} |

113 |
Component E: {u'v': 1} |

114 |
\end{lstlisting} |

115 | |

116 |
\textbf{Disclaimer:} I'm not sure whether my modifications are correct. But I've tested with: |

117 |
\begin{itemize} |

118 |
\item Example from the paper |

119 |
\item More complex examples, modified from the paper example. |

120 |
\item Ninux graph. I do not manually perform the check, but I use the Verification process. |

121 |
\end{itemize} |

122 | |

123 |
\subsection{Verification for the changes} |

124 |
There will be the time when a pair $(B, v)$ or $(v, B)$ value as been calculated before. And those 2 values should be equal $(B, v) = (v, B)$ since they are only 2 ways to calculate the size of the \emph{cut with B} |

125 | |

126 |
Therefore, before line 10, and line 17 in Algorithm 1 in \cite{PuzisZEDB12}, I call another function, to make sure that the old value (if it's existed) match with the new value. |

127 | |

128 |
\section{Accumation of delta} |

129 |
\subsection{Basic accumulation - \lstinline{accummulate_weight_basic()}} |

130 |
Figure \ref{fig:algorithm_puzis_2008} shows the pseudocode for calculating the Group Betweenness Centrality from \cite{Puzis:2008:ONP:1485445.1485471}. This paper was referred to in \cite{PuzisZEDB12}, as a way to compute the BC using combinatorial path counting when we take into account the \lstinline{communication intensity}. Line $15-22$ gradually accummulate the BC value. |

131 | |

132 |
For now, the result shown in Figure. \ref{fig:bc_comparison_networkx_weightbasic} seems promising, because the value of BC gathered from 3 different ways changes proportionally (XXX not sure if it's a right word) with each other. In details, I mean they increases/decreases with each other. |

133 | |

134 |
\begin{figure}[h] |

135 |
\caption{This algorithm is taken from \cite{Puzis:2008:ONP:1485445.1485471}} |

136 |
\label{fig:algorithm_puzis_2008} |

137 |
\includegraphics[scale=0.4]{algorithm_puzis_2008} |

138 |
\end{figure} |

139 | |

140 |
\begin{figure}[h] |

141 |
\caption{Comparison between 3 different ways to accumulate BC} |

142 |
\label{fig:bc_comparison_networkx_weightbasic} |

143 |
\includegraphics[scale=0.4]{bc_comparison_networkx_weightbasic} |

144 |
\end{figure} |

145 | |

146 |
\subsection{Accumulation with the \emph{Traffic Matrix} - Heuristic version - \lstinline{accumulate_weight()}} |

147 |
In this one, I also follow the algorithm in Figure \ref{fig:algorithm_puzis_2008}. But this time, instead of naive way to set the value for $h(v1, v2)$, I use the value from the \lstinline{Traffic Matrix}. Check \cite{PuzisZEDB12} for how to obtain it. |

148 | |

149 |
\subsection{Experiments} |

150 |
\subsubsection{Dataset} |

151 |
I tested the BC with: |

152 |
\begin{itemize} |

153 |
\item the graph from the paper. The result resemblences the simplifed \emph{Ninux} graph. See \ref{fig:bc_comparison_simple} |

154 |
\item full \emph{Ninux Graph}. The graph is shown in \ref{fig:ninux_graph} |

155 |
\item \textbf{simplified connected} graph from \emph{Ninux Graph}, with fewer edges and vertices. However, I make sure that the simplifed graph is still \emph{connected}. I choose the first 50 edges out of over 100 edges, and then add few edges to make the graph connected. See \ref{fig:ninux_simplified_graph} and \ref{fig:ninux_simplified_connected_graph} for the graph. |

156 |
\end{itemize} |

157 | |

158 |
\begin{figure}[h] |

159 |
\caption{BC for the simplified Ninux Graph} |

160 |
\label{fig:ninux_graph} |

161 |
\includegraphics[scale=0.4]{ninux.png} |

162 |
\end{figure} |

163 | |

164 |
\begin{figure}[h] |

165 |
\caption{Simplified Ninux Graph} |

166 |
\label{fig:ninux_simplified_graph} |

167 |
\includegraphics[scale=0.4]{ninux_simplified.png} |

168 |
\end{figure} |

169 | |

170 |
\begin{figure}[h] |

171 |
\caption{Simplified Connected Ninux Graph} |

172 |
\label{fig:ninux_simplified_connected_graph} |

173 |
\includegraphics[scale=0.4]{ninux_simplified_connected.png} |

174 |
\end{figure} |

175 | |

176 |
\subsubsection{Algorithms to test} |

177 |
3 different ways to calculate the BC are tested: |

178 |
\begin{itemize} |

179 |
\item BC calculated with \lstinline{accummulate_weight_basic()} |

180 |
\item BC calculated with \lstinline{accummulate_weight()} |

181 |
\item BC calculated with the standard \lstinline{networkx.betweenness_centrality()} |

182 |
\end{itemize} |

183 | |

184 |
\textbf{NOTE:} For the \emph{cutpoint} vertices, I do not subtract the $BC^{inter}(v)$ from their sum of locally computed BC in each biconnected component. In another |

185 | |

186 |
\subsubsection{Results} |

187 |
For the first 2 simple graph, the results resemblence the Figure. \ref{bc_comparison_simple}, where each BC from \lstinline{accummulate_weight()} and \lstinline{accummulate_weight_basic()} overlap each other. |

188 | |

189 |
But for the full \emph{Ninux} graph, as shown in Figure \ref{fig:bc_comparison_ninux}, the BC results from \lstinline{accummulate_weight()} are still way off from their expected range. [I still could not figure out why] |

190 | |

191 |
\begin{figure}[h] |

192 |
\caption{BC for the simplified Ninux Graph} |

193 |
\label{fig:bc_comparison_simple} |

194 |
\includegraphics[scale=0.4]{bc_comparison_simple.png} |

195 |
\end{figure} |

196 | |

197 |
\begin{figure}[h] |

198 |
\caption{BC for the full Ninux graph} |

199 |
\label{fig:bc_comparison_ninux} |

200 |
\includegraphics[scale=0.4]{bc_comparison_ninux.png} |

201 |
\end{figure} |

202 | |

203 | |

204 |
\clearpage |

205 |
\bibliography{references}{} |

206 |
\bibliographystyle{plain} |

207 | |

208 |
\end{document} |