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]{logoans.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 GaussMarkov \cite{camp2002survey} 
107 
\item Reference Point Group \cite{hong1999group} 
108 
\item Timevariant 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/gentleintroductionautocorrelationpartialautocorrelation/}{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 timeinstant 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 timeseries of \ac{BC} for that node. Given that we have 50 nodes, for any timelag we have 
145 
50 ACF values. The average ACF is computed over the 50 nodes for timelags 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} 