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

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

\maketitle

\clearpage

\section{Introduction}

    \subsection{Notation}

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

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

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

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

    \subsection{Dataset}

        There are 5 datasets in total:

        \begin{itemize}

            \item Unweighted graphs

            \begin{itemize}

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

                \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

            \end{itemize}

            \item Weighted graphs

            \begin{itemize}

                \item \emph{ninux_30_1}

                \item \emph{olsr-netjson}

                \item \emph{jsoninfo_topo}

            \end{itemize}

        \end{itemize}

    \subsection{Comparison between BBC, BBCT, HBCU}

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

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

        \begin{figure}[h]

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

            \label{fig:feb16_jsoninfo_topo_unweighted}

            \includegraphics[]{feb16_jsoninfo_topo_unweighted.eps}

        \end{figure}

    \subsection{Purpose}

        This report will

        \begin{itemize}

             \item Show how HBCW is obtained

             \item Comparing HBCU and HBCW

         \end{itemize}

\section{HBC for weighted graph}

    \subsection{Method}

        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.

    \subsection{Result}

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

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

        \begin{itemize}

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

            \item \emph{olsr-netjson}

        \end{itemize}

        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}

        \begin{figure}[h]

                \caption{BBCT \& HBCW for ninux_30_1}

                \label{fig:feb16_ninux_30_1_weighted}

                \includegraphics[]{feb16_ninux_30_1_weighted.eps}

        \end{figure}

        \begin{figure}[h]

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

                \label{fig:feb16_jsoninfo_topo_weighted}

                \includegraphics[]{feb16_jsoninfo_topo_weighted.eps}

        \end{figure}

\clearpage

\bibliography{references}{}

\bibliographystyle{plain}

\end{document}