Thesis » QuynhNguyen-MS

\documentclass[12pt]{article}

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

% customizations and command definitions. The preamble is everything

% between \documentclass and \begin{document}.

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

\usepackage{graphicx}              % to include figures

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

\usepackage{epstopdf}              % for the .ps image

\epstopdfsetup{update}

\DeclareGraphicsExtensions{.eps}

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

\usepackage[noabbrev,capitalise]{cleveref}

\usepackage{amsmath}               % great math stuff

\usepackage{amsfonts}              % for blackboard bold, etc

\usepackage{amsthm}                % better theorem environments

\usepackage{listings}              % to add code

\lstset{language=Java}

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

\usepackage[utf8]{inputenc}

\usepackage{color}

\usepackage{cite}

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

\hypersetup{citecolor=green}

\hypersetup{linkcolor=red}

\hypersetup{urlcolor=blue}

\usepackage{cleveref}

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

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

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

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

\lstdefinestyle{mystyle}{

    backgroundcolor=\color{backcolour},

    commentstyle=\color{codegreen},

    keywordstyle=\color{magenta},

    numberstyle=\tiny\color{codegray},

    stringstyle=\color{codepurple},

    basicstyle=\footnotesize,

    breakatwhitespace=false,

    breaklines=true,

    captionpos=b,

    keepspaces=true,

    numbers=left,

    numbersep=5pt,

    showspaces=false,

    showstringspaces=false,

    showtabs=false,

    tabsize=2

}

\lstset{style=mystyle}

\DeclareMathOperator{\id}{id}

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

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

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

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

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

\usepackage[T1]{fontenc}

\AtBeginDocument{%

  \begingroup\lccode`~=`_%

  \lowercase{\endgroup\let~}_%

  \catcode`_=12

}

\usepackage{booktabs} % To thicken table lines

\usepackage{algorithm}

\usepackage[noend]{algpseudocode} % For pseudocode

\begin{document}

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

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

\maketitle

\clearpage

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

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

    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".

    \begin{algorithm}

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

        \begin{algorithmic}[1]

            \Procedure{accumulation}{}

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

                \For{$v \in V$}

                    $\delta[v] \leftarrow 0$

                \EndFor

                \While{$S$ not empty}

                    \State pop $w \leftarrow S$

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

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

                    \EndFor

                    \If{$w \neq s$}

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

                    \EndIf

                \EndWhile

            \EndProcedure

        \end{algorithmic}

    \end{algorithm}

    \begin{algorithm}

    \caption{Including targets}\label{accumulation_targets}

        \begin{algorithmic}[1]

            \Procedure{accumulation}{}

                \For{$v \in V$}

                    $\delta[v] \leftarrow 0$

                \EndFor

                \While{$S$ not empty}

                    \State pop $w \leftarrow S$

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

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

                    \EndFor

                    \If{$w \neq s$}

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

                    \EndIf

                \EndWhile

            \EndProcedure

        \end{algorithmic}

    \end{algorithm}

    \begin{algorithm}

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

        \begin{algorithmic}[1]

            \Procedure{accumulation}{}

                \For{$v \in V$}

                    $\delta[v] \leftarrow 0$

                \EndFor

                \While{$S$ not empty}

                    \State pop $w \leftarrow S$

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

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

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

                    \EndFor

                    \If{$w \neq s$}

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

                    \EndIf

                \EndWhile

            \EndProcedure

        \end{algorithmic}

    \end{algorithm}

    \begin{figure}[h]

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

            \label{fig:comparison_including_either_source_target}

            \includegraphics[]{comparison_including_either_source_target.eps}

    \end{figure}

\section{The BC inter}

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}

    \begin{figure}[h]

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

            \label{fig:not_substracted_by_bc_inter}

            \includegraphics[]{feb10_bc_inter.eps}

    \end{figure}

    \begin{figure}[h]

            \caption{Heuristic BC is subtracted by BC inter}

            \label{fig:substracted_by_bc_inter}

            \includegraphics[]{feb10_subtracted_by_bc_inter.eps}

    \end{figure}

\clearpage

\bibliography{references}{}

\bibliographystyle{plain}

\end{document}