root / latex / report_feb_16.tex @ 4ca27bae
History | View | Annotate | Download (5.61 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 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} |