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

History | View | Annotate | Download (5.61 KB)

1 |
\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 for Weighted Graph} |

80 | |

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

82 | |

83 |
\maketitle |

84 |
\clearpage |

85 | |

86 |
\section{Introduction} |

87 |
\subsection{Notation} |

88 |
\textbf{BBC}: the score obtained by Brandes Betweenness Centrality |

89 | |

90 |
\textbf{BBCT}: the score obtained by Brandes BC with the inclusion of targets |

91 | |

92 |
\textbf{HBCU}: the heuristic way to obtain BC score, for unweighted graph |

93 | |

94 |
\textbf{HBCW}: the heuristic way to obtain BC score, for weighted graph |

95 | |

96 |
\subsection{Dataset} |

97 |
There are 5 datasets in total: |

98 | |

99 |
\begin{itemize} |

100 |
\item Unweighted graphs |

101 |
\begin{itemize} |

102 |
\item \emph{simple}: this is the graph getting from paper \cite{PuzisZEDB12} |

103 |
\item \emph{ninux_unweighted_connected}: all the vertices and edges are the same as \emph{ninux_30_1}, but the costs for all edges are 1. It's |

104 |
\end{itemize} |

105 |
\item Weighted graphs |

106 |
\begin{itemize} |

107 |
\item \emph{ninux_30_1} |

108 |
\item \emph{olsr-netjson} |

109 |
\item \emph{jsoninfo_topo} |

110 |
\end{itemize} |

111 |
\end{itemize} |

112 | |

113 |
\subsection{Comparison between BBC, BBCT, HBCU} |

114 |
We have BBC $\sim$ HBCU, there are constant difference between the scores obtained by these 2 methods. |

115 | |

116 |
And we have BBCT = HBCU. See \ref{fig:feb16_jsoninfo_topo_unweighted} |

117 | |

118 |
\begin{figure}[h] |

119 |
\caption{BBCT \& HBCU for jsoninfo_topo. Their results are the same} |

120 |
\label{fig:feb16_jsoninfo_topo_unweighted} |

121 |
\includegraphics[]{feb16_jsoninfo_topo_unweighted.eps} |

122 |
\end{figure} |

123 | |

124 |
\subsection{Purpose} |

125 |
This report will |

126 |
\begin{itemize} |

127 |
\item Show how HBCW is obtained |

128 |
\item Comparing HBCU and HBCW |

129 |
\end{itemize} |

130 | |

131 |
\section{HBC for weighted graph} |

132 |
\subsection{Method} |

133 |
When calculating the BC for each bi-connected component, \emph{weight_map} is included. As a result, HBCW will take into account the weight of each edge when calculating the number of shortest paths $\sigma$. And the $\sigma$ will affect the final BC score. |

134 | |

135 |
\subsection{Result} |

136 |
For \textbf{unweighted graph}, BBCT = HBCW. |

137 | |

138 |
For \textbf{weighted graph}, BBCT = HBCW with these dataset: |

139 |
\begin{itemize} |

140 |
\item \emph{ninux_30_1}. See \ref{fig:feb16_ninux_30_1_weighted} |

141 |
\item \emph{olsr-netjson} |

142 |
\end{itemize} |

143 | |

144 |
And BBCT != HBCW in the dataset \emph{jsoninfo_topo}. See \ref{fig:feb16_jsoninfo_topo_weighted}. Compare to the result obtained by HBCU in \ref{fig:feb16_jsoninfo_topo_unweighted} |

145 | |

146 |
\begin{figure}[h] |

147 |
\caption{BBCT \& HBCW for ninux_30_1} |

148 |
\label{fig:feb16_ninux_30_1_weighted} |

149 |
\includegraphics[]{feb16_ninux_30_1_weighted.eps} |

150 |
\end{figure} |

151 |
\begin{figure}[h] |

152 |
\caption{BBCT \& HBCW for jsoninfo_topo. Their results are different} |

153 |
\label{fig:feb16_jsoninfo_topo_weighted} |

154 |
\includegraphics[]{feb16_jsoninfo_topo_weighted.eps} |

155 |
\end{figure} |

156 | |

157 |
\clearpage |

158 |
\bibliography{references}{} |

159 |
\bibliographystyle{plain} |

160 | |

161 |
\end{document} |