Revision 50aa86a1

View differences:

latex/references.bib
1
@book {richard1995,
2
    author    = {Scheaffer, Richard},
3
    title     = {Probability and Statistics for Engineers},
4
    publisher = "ITP",
5
    year      = {1995},
6
    edition   = {First}
7
}
8

  
9
@book {gut2005,
10
    author    = {Gut, Allan},
11
    title     = {Probability: A Graduate Course},
12
    publisher = "Springer",
13
    year      = {2005},
14
    edition   = {First}
15
}
16

  
17
@inproceedings{PuzisZEDB12,
18
  author    = {Rami Puzis and
19
               Polina Zilberman and
20
               Yuval Elovici and
21
               Shlomi Dolev and
22
               Ulrik Brandes},
23
  title     = {Heuristics for Speeding Up Betweenness Centrality Computation},
24
  booktitle = {2012 International Conference on Privacy, Security, Risk and Trust,
25
               {PASSAT} 2012, and 2012 International Confernece on Social Computing,
26
               SocialCom 2012, Amsterdam, Netherlands, September 3-5, 2012},
27
  pages     = {302--311},
28
  year      = {2012},
29
  crossref  = {DBLP:conf/socialcom/2012},
30
  url       = {http://dx.doi.org/10.1109/SocialCom-PASSAT.2012.66},
31
  doi       = {10.1109/SocialCom-PASSAT.2012.66},
32
  timestamp = {Mon, 14 Jan 2013 18:11:28 +0100},
33
  biburl    = {http://dblp2.uni-trier.de/rec/bib/conf/socialcom/PuzisZEDB12},
34
  bibsource = {dblp computer science bibliography, http://dblp.org}
35
}
36

  
37
@inproceedings{Puzis:2008:ONP:1485445.1485471,
38
 author = {Puzis, Rami and Klippel, Marius David and Elovici, Yuval and Dolev, Shlomi},
39
 title = {Optimization of NIDS Placement for Protection of Intercommunicating Critical Infrastructures},
40
 booktitle = {Proceedings of the 1st European Conference on Intelligence and Security Informatics},
41
 series = {EuroISI '08},
42
 year = {2008},
43
 isbn = {978-3-540-89899-3},
44
 location = {Esbjerg, Denmark},
45
 pages = {191--203},
46
 numpages = {13},
47
 url = {http://dx.doi.org/10.1007/978-3-540-89900-6_20},
48
 doi = {10.1007/978-3-540-89900-6_20},
49
 acmid = {1485471},
50
 publisher = {Springer-Verlag},
51
 address = {Berlin, Heidelberg},
52
 keywords = {NIDS placement, communication infrastructure protection, epidemic models},
53
}
54

  
latex/report_dec_20.tex
1
% http://www.ams.jhu.edu/~ers/learn-latex/
2

  
3
\documentclass[12pt]{article}
4
% This first part of the file is called the PREAMBLE. It includes
5
% customizations and command definitions. The preamble is everything
6
% between \documentclass and \begin{document}.
7

  
8
\usepackage[margin=1in]{geometry}  % set the margins to 1in on all sides
9
\usepackage{graphicx}              % to include figures
10
\graphicspath{ {report_images/} }       % '/' is needed
11
\usepackage[noabbrev,capitalise]{cleveref}
12
\usepackage{amsmath}               % great math stuff
13
\usepackage{amsfonts}              % for blackboard bold, etc
14
\usepackage{amsthm}                % better theorem environments
15
\usepackage{listings}              % to add code
16
\lstset{language=Java}
17
\renewcommand{\lstlistingname}{Code} % change "Listing 1.1" to "Code 1.1"
18

  
19
\usepackage[utf8]{inputenc}
20
\usepackage{color}
21

  
22
\usepackage{cite}
23

  
24
\usepackage[colorlinks]{hyperref}       % from http://tex.stackexchange.com/questions/3568/how-does-one-typeset-a-url
25
\hypersetup{citecolor=green}
26
\hypersetup{linkcolor=red}
27
\hypersetup{urlcolor=blue}
28
\usepackage{cleveref}
29

  
30
\definecolor{codegreen}{rgb}{0,0.6,0}
31
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
32
\definecolor{codepurple}{rgb}{0.58,0,0.82}
33
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
34

  
35
\lstdefinestyle{mystyle}{
36
    backgroundcolor=\color{backcolour},
37
    commentstyle=\color{codegreen},
38
    keywordstyle=\color{magenta},
39
    numberstyle=\tiny\color{codegray},
40
    stringstyle=\color{codepurple},
41
    basicstyle=\footnotesize,
42
    breakatwhitespace=false,
43
    breaklines=true,
44
    captionpos=b,
45
    keepspaces=true,
46
    numbers=left,
47
    numbersep=5pt,
48
    showspaces=false,
49
    showstringspaces=false,
50
    showtabs=false,
51
    tabsize=2
52
}
53

  
54
\lstset{style=mystyle}
55
\DeclareMathOperator{\id}{id}
56

  
57
\newcommand{\bd}[1]{\mathbf{#1}}  % for bolding symbols
58
\newcommand{\RR}{\mathbb{R}}      % for Real numbers
59
\newcommand{\ZZ}{\mathbb{Z}}      % for Integers
60
\newcommand{\col}[1]{\left[\begin{matrix} #1 \end{matrix} \right]}
61
\newcommand{\comb}[2]{\binom{#1^2 + #2^2}{#1+#2}}
62

  
63
\usepackage[T1]{fontenc}
64
\AtBeginDocument{%
65
  \begingroup\lccode`~=`_%
66
  \lowercase{\endgroup\let~}_%
67
  \catcode`_=12
68
}
69

  
70
\usepackage{booktabs} % To thicken table lines
71

  
72
\begin{document}
73

  
74
\title{Thesis - Report Dec 20 - Heuristic Betweenness by using biconnected components}
75

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

  
78
\maketitle
79
\clearpage
80

  
81
\section{Bugs in calculating the Component Tree Weight (or Link Weight)}
82

  
83
    As Leonardo, I checked again how I calculate the Link Weight for the Component Tree.
84

  
85
    \textbf{Version 1:} the exactl Algorithm 1 as in \cite{PuzisZEDB12}. But the result is wrong when I test with the graph in the paper.
86

  
87
    Line 6-12 execute the case of Eq. 15 in \cite{PuzisZEDB12}. This is the case when the component has only 1 unknown link weight.
88

  
89
    Line 14-19 performs the equation. 14 in \cite{PuzisZEDB12}, for when the cutpoint has exactly 1 unknown link weight.
90

  
91

  
92
    \textbf{Version 2:} modifying the Algorithm 1 in 2 places:
93
    \begin{itemize}
94
        \item line 9: It will be $size \leftarrow size + |V| - D^{n(}_{B} - 1$
95
        \item line 15: \(size \leftarrow 0\). The $size$ is the sum part in Eq. 14 in \cite{PuzisZEDB12}. According to the equation, the initial value of the sum must be 0, not 1.
96
    \end{itemize}
97

  
98
    Below is the result for the size of \textbf{cut with B}, or the $D^{u()}_{B}$. From left to right, it denotes the \lstinline{cut with B} for component $A, B, C, D, E$, respectively.
99

  
100
    \begin{lstlisting}
101
# Wrong result - from Version 1
102
[{u'u': 2}, {u'u': 7, u'v': 9}, {u'v': 1}, {u'v': 1}, {u'v': 1}]
103

  
104
# Correct result for the size of [cut with B] - Version 2 - I obtained the result by manually work with the graph, and then check the output from the algorithm
105
[{u'u': 2}, {u'u': 8, u'v': 7}, {u'v': 1}, {u'v': 1}, {u'v': 1}]
106
    \end{lstlisting}
107

  
108
    \begin{lstlisting}
109
    Component A : {u'u': 2}
110
    Component B: {u'u': 7, u'v': 9}
111
    Component C: {u'v': 1}
112
    Component D: {u'v': 1}
113
    Component E: {u'v': 1}
114
    \end{lstlisting}
115

  
116
    \textbf{Disclaimer:} I'm not sure whether my modifications are correct. But I've tested with:
117
        \begin{itemize}
118
            \item Example from the paper
119
            \item More complex examples, modified from the paper example.
120
            \item Ninux graph. I do not manually perform the check, but I use the Verification process.
121
        \end{itemize}
122

  
123
    \subsection{Verification for the changes}
124
        There will be the time when a pair $(B, v)$ or $(v, B)$ value as been calculated before. And those 2 values should be equal $(B, v) = (v, B)$ since they are only 2 ways to calculate the size of the \emph{cut with B}
125

  
126
        Therefore, before line 10, and line 17 in Algorithm 1 in \cite{PuzisZEDB12}, I call another function, to make sure that the old value (if it's existed) match with the new value.
127

  
128
\section{Accumation of delta}
129
    \subsection{Basic accumulation - \lstinline{accummulate_weight_basic()}}
130
        Figure \ref{fig:algorithm_puzis_2008} shows the pseudocode for calculating the Group Betweenness Centrality from \cite{Puzis:2008:ONP:1485445.1485471}. This paper was referred to in \cite{PuzisZEDB12}, as a way to compute the BC using combinatorial path counting when we take into account the \lstinline{communication intensity}. Line $15-22$ gradually accummulate the BC value.
131

  
132
        For now, the result shown in Figure. \ref{fig:bc_comparison_networkx_weightbasic} seems promising, because the value of BC gathered from 3 different ways changes proportionally (XXX not sure if it's a right word) with each other. In details, I mean they increases/decreases with each other.
133

  
134
        \begin{figure}[h]
135
            \caption{This algorithm is taken from \cite{Puzis:2008:ONP:1485445.1485471}}
136
            \label{fig:algorithm_puzis_2008}
137
            \includegraphics[scale=0.4]{algorithm_puzis_2008}
138
        \end{figure}
139

  
140
        \begin{figure}[h]
141
            \caption{Comparison between 3 different ways to accumulate BC}
142
            \label{fig:bc_comparison_networkx_weightbasic}
143
            \includegraphics[scale=0.4]{bc_comparison_networkx_weightbasic}
144
        \end{figure}
145

  
146
    \subsection{Accumulation with the \emph{Traffic Matrix} - Heuristic version - \lstinline{accumulate_weight()}}
147
        In this one, I also follow the algorithm in Figure \ref{fig:algorithm_puzis_2008}. But this time, instead of naive way to set the value for $h(v1, v2)$, I use the value from the \lstinline{Traffic Matrix}. Check \cite{PuzisZEDB12} for how to obtain it.
148

  
149
    \subsection{Experiments}
150
        \subsubsection{Dataset}
151
            I tested the BC with:
152
                \begin{itemize}
153
                    \item the graph from the paper. The result resemblences the simplifed \emph{Ninux} graph. See \ref{fig:bc_comparison_simple}
154
                    \item full \emph{Ninux Graph}. The graph is shown in \ref{fig:ninux_graph}
155
                    \item \textbf{simplified connected} graph from \emph{Ninux Graph}, with fewer edges and vertices. However, I make sure that the simplifed graph is still \emph{connected}. I choose the first 50 edges out of over 100 edges, and then add few edges to make the graph connected. See \ref{fig:ninux_simplified_graph} and \ref{fig:ninux_simplified_connected_graph} for the graph.
156
                \end{itemize}
157

  
158
            \begin{figure}[h]
159
                \caption{BC for the simplified Ninux Graph}
160
                \label{fig:ninux_graph}
161
                \includegraphics[scale=0.4]{ninux.png}
162
            \end{figure}
163

  
164
            \begin{figure}[h]
165
                \caption{Simplified Ninux Graph}
166
                \label{fig:ninux_simplified_graph}
167
                \includegraphics[scale=0.4]{ninux_simplified.png}
168
            \end{figure}
169

  
170
            \begin{figure}[h]
171
                \caption{Simplified Connected Ninux Graph}
172
                \label{fig:ninux_simplified_connected_graph}
173
                \includegraphics[scale=0.4]{ninux_simplified_connected.png}
174
            \end{figure}
175

  
176
        \subsubsection{Algorithms to test}
177
            3 different ways to calculate the BC are tested:
178
            \begin{itemize}
179
                \item BC calculated with \lstinline{accummulate_weight_basic()}
180
                \item BC calculated with \lstinline{accummulate_weight()}
181
                \item BC calculated with the standard \lstinline{networkx.betweenness_centrality()}
182
            \end{itemize}
183

  
184
            \textbf{NOTE:} For the \emph{cutpoint} vertices, I do not subtract the $BC^{inter}(v)$ from their sum of locally computed BC in each biconnected component. In another
185

  
186
        \subsubsection{Results}
187
            For the first 2 simple graph, the results resemblence the Figure. \ref{bc_comparison_simple}, where each BC from \lstinline{accummulate_weight()} and \lstinline{accummulate_weight_basic()} overlap each other.
188

  
189
            But for the full \emph{Ninux} graph, as shown in Figure \ref{fig:bc_comparison_ninux}, the BC results from \lstinline{accummulate_weight()} are still way off from their expected range. [I still could not figure out why]
190

  
191
            \begin{figure}[h]
192
                \caption{BC for the simplified Ninux Graph}
193
                \label{fig:bc_comparison_simple}
194
                \includegraphics[scale=0.4]{bc_comparison_simple.png}
195
            \end{figure}
196

  
197
            \begin{figure}[h]
198
                \caption{BC for the full Ninux graph}
199
                \label{fig:bc_comparison_ninux}
200
                \includegraphics[scale=0.4]{bc_comparison_ninux.png}
201
            \end{figure}
202

  
203

  
204
\clearpage
205
\bibliography{references}{}
206
\bibliographystyle{plain}
207

  
208
\end{document}

Also available in: Unified diff