## 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