Statistics
| Branch: | Revision:

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}