Statistics
| Branch: | Revision:

mobicen / documents / SoA / SoA mobiCen.md @ e1cf8bea

History | View | Annotate | Download (6.49 KB)

1
# SoA Mobility & Centrality
2

    
3
Base del ragionamento: La centralità cambia nel tempo se cambia il grafo
4

    
5
Problem Statement 1: Come aggiornare velocemente la centralità?
6

    
7
Kourtellis, Nicolas, Gianmarco De Francisci Morales, and Francesco Bonchi. "Scalable online betweenness centrality in evolving graphs." IEEE Transactions on Knowledge and Data Engineering 27.9 (2015): 2494-2506.
8

    
9
Lee, Min-Joong, Sunghee Choi, and Chin-Wan Chung. "Efficient algorithms for updating betweenness centrality in fully dynamic graphs." Information Sciences 326 (2016): 278-296.
10

    
11
Bergamini, Elisabetta, and Henning Meyerhenke. "Approximating betweenness centrality in fully dynamic networks." Internet Mathematics 12.5 (2016): 281-314.
12

    
13
Bergamini, Elisabetta, et al. "Faster betweenness centrality updates in evolving networks." arXiv preprint arXiv:1704.08592 (2017).
14

    
15
Bergamini, Elisabetta, and Henning Meyerhenke. "Fully-dynamic approximation of betweenness centrality." Algorithms-ESA 2015. Springer, Berlin, Heidelberg, 2015. 155-166.
16

    
17
Riondato, Matteo, and Eli Upfal. "ABRA: Approximating betweenness centrality in static and dynamic graphs with rademacher averages." ACM Transactions on Knowledge Discovery from Data (TKDD) 12.5 (2018): 61.
18

    
19
Riondato, Matteo, and Evgenios M. Kornaropoulos. "Fast approximation of betweenness centrality through sampling." Data Mining and Knowledge Discovery 30.2 (2016): 438-475.
20

    
21
Step ragionamento: va bene, ma adesso ho solo risolto il problema basilare del computo della centralità. Se volessi studiare i trend della centralità nel tempo? Beh ho bisogno di un modello di grafo dinamico/evolvente/temporale...
22

    
23
Problem Statement 2: Come si studia un grafo temporale? Come lo modello?
24

    
25
Holme, Petter, and Jari Saramäki. "Temporal networks." Physics reports 519.3 (2012): 97-125.
26

    
27
Holme, Petter. "Modern temporal network theory: a colloquium." The European Physical Journal B 88.9 (2015): 234.
28

    
29
Wehmuth, Klaus, Artur Ziviani, and Eric Fleury. "A unifying model for representing time-varying graphs." 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA). IEEE, 2015.
30

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

    
34
Roberts, Steven A., G. Brent Hall, and Paul H. Calamai. "Analysing forest fragmentation using spatial autocorrelation, graphs and GIS." International Journal of Geographical Information Science 14.2 (2000): 185-204.
35

    
36
Hovestadt, Thomas, Stefan Messner, and Joachim Poethke Hans. "Evolution of reduced dispersal mortality and ‘fat-tailed’dispersal kernels in autocorrelated landscapes." Proceedings of the Royal Society of London. Series B: Biological Sciences 268.1465 (2001): 385-391.
37

    
38
Ok non male, sono studi un po' fuori dal settore Computer Networking ma almeno abbiamo delle applicazioni interessanti di quello che potrebbe essere il nostro output finale. Facciamo che "ci provo io" ad impostare uno studio di autocorrelazione della centralità. Parto dall'ipotesi di avere
39
un generatore di mobility pattern che mi fornisce uno stream temporale di coordinate x,y dei miei nodi...come faccio a crearci un grafo sopra
40
per poi calcolare le metriche?
41

    
42
da Fonseca, Guilherme Dias, et al. "On the recognition of unit disk graphs and the Distance Geometry Problem with Ranges." Discrete Applied Mathematics 197 (2015): 3-19.
43

    
44
H. Breu, D. G. Kirkpatrick, Unit disk graphs recognition is NP-hard,
45
Comp. Geom. 9(1–2) (1998) 2–24.
46

    
47
C. McDiarmid, T. Müller, Integer realizations of disk and segment
48
graphs, J. Comb. Theory, Series B 103(1) (2013) 114–143.
49

    
50
Bentley, Jon L., Donald F. Stanat, and E. Hollins Williams Jr. "The complexity of finding fixed-radius near neighbors." Information processing letters 6.6 (1977): 209-212.
51

    
52
Alla fine ce la si fa ben a generare velocemente dei grafi a partire da set di coordinate:
53
- https://www.cse.wustl.edu/~pless/546/lectures/Lecture2.pdf
54
- https://stackoverflow.com/questions/32424604/find-all-nearest-neighbors-within-a-specific-distance
55

    
56
Ma è mai possibile che sia davvero io il primo ad impostare questo tipo di analisi/problema? Magari trovo qualche modulo python già fatto
57
se cerco meglio... OMG: a cercare bene davvero ci sono proprio gli studi belli e pronti!
58

    
59
Kim, Hyoungshick, and Ross Anderson. "Temporal node centrality in complex networks." Physical Review E 85.2 (2012): 026107.
60

    
61
Kim, Hyoungshick, et al. "Centrality prediction in dynamic human contact networks." Computer Networks 56.3 (2012): 983-996.
62

    
63
Braha, Dan, and Yaneer Bar-Yam. "Time-dependent complex networks: Dynamic centrality, dynamic motifs, and cycles of social interactions." Adaptive Networks. Springer, Berlin, Heidelberg, 2009. 39-50.
64

    
65
Liao, Hao, et al. "Ranking in evolving complex networks." Physics Reports 689 (2017): 1-54.
66

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

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

    
72
https://github.com/panisson/ntf-school
73

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

    
76
https://www.youtube.com/watch?v=ehlFqkyre3k
77

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

    
80
Scholtes invece prova un approccio di tipo "multi-layer graphs", sembra molto figo. Lo spiegano bene e lo supportano bene con tool molto ben sviluupati
81

    
82
https://github.com/IngoScholtes/pathpy
83
https://www.youtube.com/watch?v=CxJkVrD2ZlM
84

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