## root / latex / report_dec_20.tex @ 4f432e4a

History | View | Annotate | Download (9.44 KB)

1 | 50aa86a1 | Quynh PX Nguyen | % 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} |