Statistics
| Branch: | Revision:

mobicen / documents / manifest / manifest.tex @ fa4a0a42

History | View | Annotate | Download (4.73 KB)

1
\documentclass[12pt]{report}
2
\usepackage[english]{babel}
3
%\usepackage{natbib}
4
\usepackage{url}
5
\usepackage[utf8x]{inputenc}
6
\usepackage{amsmath}
7
\usepackage{graphicx}
8
\graphicspath{{images/}}
9
\usepackage{parskip}
10
\usepackage{fancyhdr}
11
\usepackage{hyperref}
12
\usepackage{multicol}
13
\usepackage{float}
14
\usepackage[top=1.25in, bottom=1.25in, left=0.8in, right=0.8in]{geometry}
15
%\usepackage{vmargin}
16
%\setmarginsrb{3 cm}{2.5 cm}{3 cm}{2.5 cm}{1 cm}{1.5 cm}{1 cm}{1.5 cm}
17

    
18
\title{Study of Graph Metrics on Evolving Dynamic Graphs}								
19
\author{Lorenzo Ghiro}						
20
\date{\today}
21

    
22
\makeatletter
23
\let\thetitle\@title
24
\let\theauthor\@author
25
\let\thedate\@date
26
\makeatother
27

    
28
\pagestyle{fancy}
29
\fancyhf{}
30
\rhead{\theauthor}
31
\lhead{\thetitle}
32
\cfoot{\thepage}
33

    
34
\usepackage[capitalise]{cleveref}
35
\crefname{lemma}{Lemma}{Lemmas}
36
\crefname{theorem}{Theorem}{Theorems}
37
\crefname{figure}{Fig.}{Figs.}
38
\crefname{table}{Table}{Tables}
39
\crefname{section}{Sec.}{Secs.}
40
\crefname{equation}{Eq.}{Eqs.}
41
\crefname{algocfline}{Algorithm}{Algorithms}
42
\Crefname{algocfline}{Algorithm}{Algorithms}
43
\usepackage[nohyperlinks]{acronym}
44

    
45
\acrodef{AC}{autocorrelation}
46
\acrodef{BC}{Betweenness Centrality}
47
\acrodef{LC}{Load Centrality}
48
\acrodef{DES}{Discrete Event Simulator}
49

    
50
\begin{document}
51

    
52
\begin{titlepage}
53
	\centering
54
    \vspace*{0.5 cm}
55
   % \includegraphics[scale = 0.075]{bsulogo.png}\\[1.0 cm]	% University Logo
56
\begin{center}    \textsc{\Large   Advanced Networking Systems}\\[2.0 cm]	\end{center}% University Name
57
	\textsc{\Large Research Project Description  }\\[0.5 cm]				% Course Code
58
	\rule{\linewidth}{0.2 mm} \\[0.4 cm]
59
	{ \huge \bfseries \thetitle}\\
60
	\rule{\linewidth}{0.2 mm} \\[3.5 cm]
61
	
62
%	\begin{minipage}{0.4\textwidth}
63
%		\begin{flushleft} \large
64
%		%	\emph{Submitted To:}\\
65
%		%	Name\\
66
%          % Affiliation\\
67
%           %contact info\\
68
%			\end{flushleft}
69
%			\end{minipage}~
70
%			\begin{minipage}{0.4\textwidth}
71
%			\begin{flushright} \large
72
%			\emph{Submitted By :} \\
73
%			Student Name  
74
%		\end{flushright}
75
%	\end{minipage}
76
	\includegraphics[scale = 0.8]{logo-ans.pdf}
77
\end{titlepage}
78
%\tableofcontents
79
%\pagebreak
80
\renewcommand{\thesection}{\arabic{section}}
81

    
82
\section{Goal}
83
 Study the evolution of Graph Metrics, above all Centrality metrics, in dynamic graphs.
84
 
85
\section{General Description}
86
 This is a Simulation Study based on a Python \ac{DES}. The core idea is the following: while we simulate the evolution of dynamic graphs, we
87
log the many graph metrics of potential interest, so to allow a later offline analysis.
88

    
89
\begin{figure}[H]
90
\centering
91
  \includegraphics[width=.55\linewidth]{workflow.pdf}
92
  \caption{Workflow of Experiment to allow autocorrelation analysis}
93
  \label{fig:workflow}
94
\end{figure}
95

    
96
To simulate dynamic graphs we will use the Mobility Models implemented \href{https://github.com/panisson/pymobility}{here}.
97

    
98
Supported Mobility models are:
99
\begin{multicols}{3}
100
\footnotesize
101
  \begin{itemize}
102
     \item Random Walk
103
     \item Random Waypoint
104
     \item Random Direction
105
     \item Truncated Levy Walk \cite{rhee2011levy}
106
     \item Gauss-Markov \cite{camp2002survey}
107
     \item Reference Point Group \cite{hong1999group}
108
     \item Time-variant Community \cite{hsu2007modeling}
109
  \end{itemize}
110
\end{multicols}
111

    
112
The control parameters to configure the above mobility models (e.g. area of simulation and the distribution of the nodes' speed) are still to be chosen.
113

    
114
The first analysis to be performed could be a classic \ac{AC} analysis of time series, that could be performed with Python as described \href{https://machinelearningmastery.com/gentle-introduction-autocorrelation-partial-autocorrelation/}{here}. For example, the time series of interest could be the evolving \ac{BC} index of a given node, as shown in \cref{sec:demo}.
115

    
116
\section{Preliminary Demo}\label{sec:demo}
117

    
118
\begin{multicols}{3}
119
\footnotesize
120
  \begin{itemize}
121
  \item duration: 10000,
122
  \item  max\_velocity: 1.0,
123
  \item  max\_wait\_time: 1.0,
124
  \item  max\_x: 100,
125
  \item  max\_y: 100,
126
  \item  min\_velocity: 0.1,
127
  \item  mob\_model: RandomWayPoint,
128
  \item  mobility\_timer: 1.0,
129
  \item  nodes\_number: 50,
130
  \item  radius: 30.0
131
  \end{itemize}
132
\end{multicols}
133

    
134

    
135
\begin{figure}[H]
136
\centering
137
  \includegraphics[width=.8\linewidth]{BCACF.pdf}
138
  \caption{ACF averaged over all Nodes}
139
  \label{fig:BCACF}
140
\end{figure}
141

    
142
\subsection{How is computed the above Mean ACF}
143
For every time-instant we have a graph. For each node in the graph we have its \ac{BC} index.
144
Therefore, for each node we can compute the ACF over the time-series of \ac{BC} for that node. Given that we have 50 nodes, for any time-lag we have
145
50 ACF values. The average ACF is computed over the 50 nodes for time-lags spanning from 0 to 750. 
146
This average ACF is plotted in \cref{fig:BCACF}
147

    
148

    
149

    
150
\bibliographystyle{IEEEtran}
151
\bibliography{references}
152

    
153

    
154
\end{document}