## root / latex / report_feb_10.tex @ 4ca27bae

History | View | Annotate | Download (6.7 KB)

1 | 46d9d2ec | Quynh PX Nguyen | \documentclass[12pt]{article} |
---|---|---|---|

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

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

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

5 | |||

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

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

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

9 | \usepackage{epstopdf} % for the .ps image |
||

10 | \epstopdfsetup{update} |
||

11 | \DeclareGraphicsExtensions{.eps} |
||

12 | \epstopdfDeclareGraphicsRule{.eps}{pdf}{.pdf}{ps2pdf -dEPSCrop -dNOSAFER #1 \OutputFile} |
||

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

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

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

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

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

18 | \lstset{language=Java} |
||

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

20 | |||

21 | \usepackage[utf8]{inputenc} |
||

22 | \usepackage{color} |
||

23 | |||

24 | \usepackage{cite} |
||

25 | |||

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

27 | \hypersetup{citecolor=green} |
||

28 | \hypersetup{linkcolor=red} |
||

29 | \hypersetup{urlcolor=blue} |
||

30 | \usepackage{cleveref} |
||

31 | |||

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

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

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

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

36 | |||

37 | \lstdefinestyle{mystyle}{ |
||

38 | backgroundcolor=\color{backcolour}, |
||

39 | commentstyle=\color{codegreen}, |
||

40 | keywordstyle=\color{magenta}, |
||

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

42 | stringstyle=\color{codepurple}, |
||

43 | basicstyle=\footnotesize, |
||

44 | breakatwhitespace=false, |
||

45 | breaklines=true, |
||

46 | captionpos=b, |
||

47 | keepspaces=true, |
||

48 | numbers=left, |
||

49 | numbersep=5pt, |
||

50 | showspaces=false, |
||

51 | showstringspaces=false, |
||

52 | showtabs=false, |
||

53 | tabsize=2 |
||

54 | } |
||

55 | |||

56 | \lstset{style=mystyle} |
||

57 | \DeclareMathOperator{\id}{id} |
||

58 | |||

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

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

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

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

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

64 | |||

65 | \usepackage[T1]{fontenc} |
||

66 | \AtBeginDocument{% |
||

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

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

69 | \catcode`_=12 |
||

70 | } |
||

71 | |||

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

73 | |||

74 | \usepackage{algorithm} |
||

75 | \usepackage[noend]{algpseudocode} % For pseudocode |
||

76 | |||

77 | \begin{document} |
||

78 | |||

79 | \title{Thesis - Report Feb 10 - Heuristic Betweenness Centrality vs Brandes Betweenness Centrality} |
||

80 | |||

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

82 | |||

83 | \maketitle |
||

84 | \clearpage |
||

85 | |||

86 | \section{The discrepency between Heuristic Betweenness Centrality (HBC) and Brandes Betweenness Centrality (BBC)} |
||

87 | \textbf{Summary:} the gap between the default version (of both networkx and BGL) to calculate BC is due to the inclusion of the source. |
||

88 | |||

89 | Algorithm 2 in \cite{Brandes2008136} show the variant of calculating betweenness centrality with endpoints included. The paper also mentions that we can "restrict the inclusion of endpoints to either sources or targets". |
||

90 | |||

91 | \begin{algorithm} |
||

92 | \caption{Including endpoints (both sources + targets)}\label{accumulation_endpoints} |
||

93 | \begin{algorithmic}[1] |
||

94 | \Procedure{accumulation}{} |
||

95 | \State $c_B[s] \leftarrow c_B[s] + (|S| - 1)$ |
||

96 | \For{$v \in V$} |
||

97 | $\delta[v] \leftarrow 0$ |
||

98 | \EndFor |
||

99 | |||

100 | \While{$S$ not empty} |
||

101 | \State pop $w \leftarrow S$ |
||

102 | \For{$v \in Pred[w]$} |
||

103 | $\delta[v] \leftarrow \delta[v] + \frac{\sigma[v]}{\sigma[w]} (1 + \delta[w])$ |
||

104 | \EndFor |
||

105 | \If{$w \neq s$} |
||

106 | $c_B[w] \leftarrow c_B[w] + \delta[w] + 1$ \Comment{$w$ is target of $s$ once} |
||

107 | \EndIf |
||

108 | \EndWhile |
||

109 | \EndProcedure |
||

110 | \end{algorithmic} |
||

111 | \end{algorithm} |
||

112 | |||

113 | \begin{algorithm} |
||

114 | \caption{Including targets}\label{accumulation_targets} |
||

115 | \begin{algorithmic}[1] |
||

116 | \Procedure{accumulation}{} |
||

117 | \For{$v \in V$} |
||

118 | $\delta[v] \leftarrow 0$ |
||

119 | \EndFor |
||

120 | |||

121 | \While{$S$ not empty} |
||

122 | \State pop $w \leftarrow S$ |
||

123 | \For{$v \in Pred[w]$} |
||

124 | $\delta[v] \leftarrow \delta[v] + \frac{\sigma[v]}{\sigma[w]} (1 + \delta[w])$ |
||

125 | \EndFor |
||

126 | \If{$w \neq s$} |
||

127 | $c_B[w] \leftarrow c_B[w] + \delta[w] + 1$ \Comment{$w$ is target of $s$ once} |
||

128 | \EndIf |
||

129 | \EndWhile |
||

130 | \EndProcedure |
||

131 | \end{algorithmic} |
||

132 | \end{algorithm} |
||

133 | |||

134 | \begin{algorithm} |
||

135 | \caption{Heuristic Betweenness Centrality}\label{accumulation_heuristic} |
||

136 | \begin{algorithmic}[1] |
||

137 | \Procedure{accumulation}{} |
||

138 | \For{$v \in V$} |
||

139 | $\delta[v] \leftarrow 0$ |
||

140 | \EndFor |
||

141 | \While{$S$ not empty} |
||

142 | \State pop $w \leftarrow S$ |
||

143 | \State $h \leftarrow $ get_the_communication_intensity_between $(w, s)$ |
||

144 | \For{$v \in Pred[w]$} |
||

145 | $\delta[v] \leftarrow \delta[v] + \frac{\sigma[v]}{\sigma[w]} (h + \delta[w])$ |
||

146 | \EndFor |
||

147 | \If{$w \neq s$} |
||

148 | $c_B[w] \leftarrow c_B[w] + \delta[w] + h$ |
||

149 | \EndIf |
||

150 | \EndWhile |
||

151 | \EndProcedure |
||

152 | \end{algorithmic} |
||

153 | \end{algorithm} |
||

154 | |||

155 | \begin{figure}[h] |
||

156 | \caption{Comparison between 3 different accumulation functions \ref{accumulation_endpoints}, \ref{accumulation_targets}, \ref{accumulation_heuristic}} |
||

157 | \label{fig:comparison_including_either_source_target} |
||

158 | \includegraphics[]{comparison_including_either_source_target.eps} |
||

159 | \end{figure} |
||

160 | |||

161 | \section{The BC inter} |
||

162 | Lemma 4.2 in \cite{PuzisZEDB12} shows that the BC for articulation points are the sum of BC in each bi-connected components, subtracted by the \texttt{BC inter}. However, when I subtract the \texttt{BC inter} from the \texttt{BC sum}, the results are not meaningful as shown in figure \ref{fig:substracted_by_bc_inter} and \ref{fig:not_substracted_by_bc_inter} |
||

163 | |||

164 | \begin{figure}[h] |
||

165 | \caption{Heuristic BC is NOT subtracted by BC inter} |
||

166 | \label{fig:not_substracted_by_bc_inter} |
||

167 | \includegraphics[]{feb10_bc_inter.eps} |
||

168 | \end{figure} |
||

169 | |||

170 | \begin{figure}[h] |
||

171 | \caption{Heuristic BC is subtracted by BC inter} |
||

172 | \label{fig:substracted_by_bc_inter} |
||

173 | \includegraphics[]{feb10_subtracted_by_bc_inter.eps} |
||

174 | \end{figure} |
||

175 | |||

176 | \clearpage |
||

177 | |||

178 | \bibliography{references}{} |
||

179 | \bibliographystyle{plain} |
||

180 | |||

181 | \end{document} |