Statistics
| Branch: | Revision:

mobicen / documents / SoA / try.tex @ 9f4f3f35

History | View | Annotate | Download (8.34 KB)

1
\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
2
\PassOptionsToPackage{hyphens}{url}
3
%
4
\documentclass[]{article}
5
\usepackage{lmodern}
6
\usepackage{amssymb,amsmath}
7
\usepackage{ifxetex,ifluatex}
8
\usepackage{fixltx2e} % provides \textsubscript
9
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
10
  \usepackage[T1]{fontenc}
11
  \usepackage[utf8]{inputenc}
12
  \usepackage{textcomp} % provides euro and other symbols
13
\else % if luatex or xelatex
14
  \usepackage{unicode-math}
15
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
16
\fi
17
% use upquote if available, for straight quotes in verbatim environments
18
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
19
% use microtype if available
20
\IfFileExists{microtype.sty}{%
21
\usepackage[]{microtype}
22
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
23
}{}
24
\IfFileExists{parskip.sty}{%
25
\usepackage{parskip}
26
}{% else
27
\setlength{\parindent}{0pt}
28
\setlength{\parskip}{6pt plus 2pt minus 1pt}
29
}
30
\usepackage{hyperref}
31
\hypersetup{
32
            pdfborder={0 0 0},
33
            breaklinks=true}
34
\urlstyle{same}  % don't use monospace font for urls
35
\setlength{\emergencystretch}{3em}  % prevent overfull lines
36
\providecommand{\tightlist}{%
37
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
38
\setcounter{secnumdepth}{0}
39
% Redefines (sub)paragraphs to behave more like sections
40
\ifx\paragraph\undefined\else
41
\let\oldparagraph\paragraph
42
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
43
\fi
44
\ifx\subparagraph\undefined\else
45
\let\oldsubparagraph\subparagraph
46
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
47
\fi
48

    
49
% set default figure placement to htbp
50
\makeatletter
51
\def\fps@figure{htbp}
52
\makeatother
53

    
54

    
55
\date{}
56

    
57
\begin{document}
58

    
59
\hypertarget{soa-mobility-centrality}{%
60
\section{SoA Mobility \& Centrality}\label{soa-mobility-centrality}}
61

    
62
Base del ragionamento: La centralità cambia nel tempo se cambia il grafo
63

    
64
Problem Statement 1: Come aggiornare velocemente la centralità?
65

    
66
Kourtellis, Nicolas, Gianmarco De Francisci Morales, and Francesco
67
Bonchi. ``Scalable online betweenness centrality in evolving graphs.''
68
IEEE Transactions on Knowledge and Data Engineering 27.9 (2015):
69
2494-2506.
70

    
71
Lee, Min-Joong, Sunghee Choi, and Chin-Wan Chung. ``Efficient algorithms
72
for updating betweenness centrality in fully dynamic graphs.''
73
Information Sciences 326 (2016): 278-296.
74

    
75
Bergamini, Elisabetta, and Henning Meyerhenke. ``Approximating
76
betweenness centrality in fully dynamic networks.'' Internet Mathematics
77
12.5 (2016): 281-314.
78

    
79
Bergamini, Elisabetta, et al. ``Faster betweenness centrality updates in
80
evolving networks.'' arXiv preprint arXiv:1704.08592 (2017).
81

    
82
Bergamini, Elisabetta, and Henning Meyerhenke. ``Fully-dynamic
83
approximation of betweenness centrality.'' Algorithms-ESA 2015.
84
Springer, Berlin, Heidelberg, 2015. 155-166.
85

    
86
Riondato, Matteo, and Eli Upfal. ``ABRA: Approximating betweenness
87
centrality in static and dynamic graphs with rademacher averages.'' ACM
88
Transactions on Knowledge Discovery from Data (TKDD) 12.5 (2018): 61.
89

    
90
Riondato, Matteo, and Evgenios M. Kornaropoulos. ``Fast approximation of
91
betweenness centrality through sampling.'' Data Mining and Knowledge
92
Discovery 30.2 (2016): 438-475.
93

    
94
Step ragionamento: va bene, ma adesso ho solo risolto il problema
95
basilare del computo della centralità. Se volessi studiare i trend della
96
centralità nel tempo? Beh ho bisogno di un modello di grafo
97
dinamico/evolvente/temporale\ldots{}
98

    
99
Problem Statement 2: Come si studia un grafo temporale? Come lo modello?
100

    
101
Holme, Petter, and Jari Saramäki. ``Temporal networks.'' Physics reports
102
519.3 (2012): 97-125.
103

    
104
Holme, Petter. ``Modern temporal network theory: a colloquium.'' The
105
European Physical Journal B 88.9 (2015): 234.
106

    
107
Wehmuth, Klaus, Artur Ziviani, and Eric Fleury. ``A unifying model for
108
representing time-varying graphs.'' 2015 IEEE International Conference
109
on Data Science and Advanced Analytics (DSAA). IEEE, 2015.
110

    
111
Benissimo, ce n'è quanti ne vuoi di modelli e ragionamenti da fare,
112
vediamo di tornare allo studio di centralità o altre metriche
113
interessanti in grafi temporali. C'è quache studio di autocorrelazione
114
di questo tipo?
115

    
116
Roberts, Steven A., G. Brent Hall, and Paul H. Calamai. ``Analysing
117
forest fragmentation using spatial autocorrelation, graphs and GIS.''
118
International Journal of Geographical Information Science 14.2 (2000):
119
185-204.
120

    
121
Hovestadt, Thomas, Stefan Messner, and Joachim Poethke Hans. ``Evolution
122
of reduced dispersal mortality and `fat-tailed'dispersal kernels in
123
autocorrelated landscapes.'' Proceedings of the Royal Society of London.
124
Series B: Biological Sciences 268.1465 (2001): 385-391.
125

    
126
Ok non male, sono studi un po' fuori dal settore Computer Networking ma
127
almeno abbiamo delle applicazioni interessanti di quello che potrebbe
128
essere il nostro output finale. Facciamo che ``ci provo io'' ad
129
impostare uno studio di autocorrelazione della centralità. Parto
130
dall'ipotesi di avere un generatore di mobility pattern che mi fornisce
131
uno stream temporale di coordinate x,y dei miei nodi\ldots{}come faccio
132
a crearci un grafo sopra per poi calcolare le metriche?
133

    
134
da Fonseca, Guilherme Dias, et al. ``On the recognition of unit disk
135
graphs and the Distance Geometry Problem with Ranges.'' Discrete Applied
136
Mathematics 197 (2015): 3-19.
137

    
138
H. Breu, D. G. Kirkpatrick, Unit disk graphs recognition is NP-hard,
139
Comp. Geom. 9(1--2) (1998) 2--24.
140

    
141
C. McDiarmid, T. Müller, Integer realizations of disk and segment
142
graphs, J. Comb. Theory, Series B 103(1) (2013) 114--143.
143

    
144
Bentley, Jon L., Donald F. Stanat, and E. Hollins Williams Jr. ``The
145
complexity of finding fixed-radius near neighbors.'' Information
146
processing letters 6.6 (1977): 209-212.
147

    
148
Alla fine ce la si fa ben a generare velocemente dei grafi a partire da
149
set di coordinate: -
150
https://www.cse.wustl.edu/\textasciitilde{}pless/546/lectures/Lecture2.pdf
151
-
152
https://stackoverflow.com/questions/32424604/find-all-nearest-neighbors-within-a-specific-distance
153

    
154
Ma è mai possibile che sia davvero io il primo ad impostare questo tipo
155
di analisi/problema? Magari trovo qualche modulo python già fatto se
156
cerco meglio\ldots{} OMG: a cercare bene davvero ci sono proprio gli
157
studi belli e pronti!
158

    
159
Kim, Hyoungshick, and Ross Anderson. ``Temporal node centrality in
160
complex networks.'' Physical Review E 85.2 (2012): 026107.
161

    
162
Kim, Hyoungshick, et al. ``Centrality prediction in dynamic human
163
contact networks.'' Computer Networks 56.3 (2012): 983-996.
164

    
165
Braha, Dan, and Yaneer Bar-Yam. ``Time-dependent complex networks:
166
Dynamic centrality, dynamic motifs, and cycles of social interactions.''
167
Adaptive Networks. Springer, Berlin, Heidelberg, 2009. 39-50.
168

    
169
Liao, Hao, et al. ``Ranking in evolving complex networks.'' Physics
170
Reports 689 (2017): 1-54.
171

    
172
Ma in particolare si distinguono due bomber nel panorama della
173
time-analysis di centralità nel tempo: André Panisson e Ingo Scholtes,
174
che mi offrono pure dei modulini Python per impostare il mio lavoro come
175
il loro. Partiamo da Panisson
176

    
177
Panisson modella i temporal graph come tensori, e da abile manipolazione
178
dei tensori tira fuori un sacco di cose interessanti.
179

    
180
https://github.com/panisson/ntf-school
181

    
182
L. Gauvin, A. Panisson, C. Cattuto. Detecting the Community Structure
183
and Activity Patterns of Temporal Networks: A Non-Negative Tensor
184
Factorization Approach PLOS ONE 9.1 (2014): e86028.
185

    
186
https://www.youtube.com/watch?v=ehlFqkyre3k
187

    
188
https://www.slideshare.net/panisson/exploring-temporal-graph-data-with-python-a-study-on-tensor-decomposition-of-wearable-sensor-data
189

    
190
Scholtes invece prova un approccio di tipo ``multi-layer graphs'',
191
sembra molto figo. Lo spiegano bene e lo supportano bene con tool molto
192
ben sviluupati
193

    
194
https://github.com/IngoScholtes/pathpy
195
https://www.youtube.com/watch?v=CxJkVrD2ZlM
196

    
197
I Scholtes: When is a network a network? Multi-Order Graphical Model
198
Selection in Pathways and Temporal Networks, to appear in KDD'17,
199
arXiv:1702.05499 I Scholtes, N Wider, A Garas: Higher-Order Aggregate
200
Networks in the Analysis of Temporal Networks: Path structures and
201
centralities, The European Physical Journal B, 89:61, March 2016 I
202
Scholtes, N Wider, R Pfitzner, A Garas, CJ Tessone, F Schweitzer:
203
Causality-driven slow-down and speed-up of diffusion in non-Markovian
204
temporal networks, Nature Communications, 5, September 2014 R Pfitzner,
205
I Scholtes, A Garas, CJ Tessone, F Schweitzer: Betweenness preference:
206
Quantifying correlations in the topological dynamics of temporal
207
networks, Phys Rev Lett, 110(19), 198701, May 2013
208

    
209
\end{document}