Table of Contents
Preface v
Acknowledgments vii
1 Introduction 1
2 Mathematical toolbox 7
2.1 Probability 7
2.1.1 Discrete variables 7
2.1.2 Continuous variables 10
2.2 Renewal processes 11
2.2.1 Poisson processes 11
2.2.2 General renewal processes 15
2.3 Random walks and diffusion 18
2.3.1 Discrete time 18
2.3.2 Continuous time 19
2.4 Power-law distributions 21
2.5 Maximum likelihood 25
2.6 Entropy, information and similarity measures 26
2.7 Matrix algebra 28
2.8 Linear stability 30
2.9 Markov chains 31
2.10 Brandling processes 33
3 Static networks 37
3.1 Definition 37
3.2 Degree distribution 39
3.3 Measures derived from walks and paths 41
3.4 Clustering coefficient 43
3.5 Spectral properties 43
3.6 Discrete-time random walks on networks 46
3.7 Centrality 48
3.7.1 Closeness centrality 49
3.7.2 Betweenness centrality 49
3.7.3 Katz centrality 49
3.7.4 PageRank 50
3.8 Models of networks 53
3.8.1 Erdos-Rényi random graph 54
3.8.2 Configuration model 57
3.8.3 Growing network with preferential attachment 59
3.9 Network motifs 61
3.10 Community detection 62
3.10.1 Modularity 63
3.10.2 Markov stability 66
3.10.3 Infomap 68
3.10.4 Overlapping communities 71
4 Analysis of temporal networks 73
4.1 Definition 73
4.2 Temporal walks and paths 76
4.2.1 Definition 76
4.2.2 Temporal distances 78
4.2.3 Vector clock 82
4.3 Components 84
4.4 Temporal coherence of a triangle 86
4.5 Centrality 88
4.5.1 Time-independent centrality 89
4.5.2 Time-dependent centrality 94
1.6 Statistical properties of event times 99
4.6.1 Distribution of inter-event times 100
4.6.2 Coefficient of variation 101
4.6.3 Local variation 102
4.6.4 Detrending 102
4.6.5 Fano factor 104
4.6.6 Detrended fluctuation analysis 107
4.7 Temporal correlation 109
4.8 Nidi models and randomisation procedures 114
4.9 Temporal motifs 115
4.10 Detection of change points and anomalies 119
4.11 Link prediction 122
4.12 Communities in temporal networks 124
4.12.1 Modularity maximisation under estrangement constraint 126
4.12.2 Community matching approach 127
4.12.3 Mapping change 129
4.12.4 Model-based approach 133
4.12.5 Multilayer modularity 133
4.12.6 Tensor factorisation approach 137
5 Models of temporal networks 141
5.1 Models of non-Markoviamty 141
5.2 Stochastic temporal networks 142
5.3 Activity driven model 143
5.4 Priority queue models 148
5.5 Self-exciting processes 154
5.5.1 Hawkes processes 154
5.5.2 Cascading Poisson processes 158
5.6 Markovian log-linear models 161
5.7 Memory networks 164
5.8 Metapopulation model 170
6 Dynamics on temporal networks 175
6.1 Waiting-time paradox 176
6.2 Gillespie algorithms 179
6.3 Random walks 185
6.3.1 Node-centric random walks 185
6.3.2 Link-centric random walks 189
6.4 Epidemic processes 191
6.4.1 Models of epidemic processes 191
6.4.2 SIS dynamics on metapopulation models 195
6.4.3 SIR. dynamics on the neighbour exchange network model 197
6.4.4 Viral spreading dynamics under bursty interaction 201
6.4.5 SIR dynamics on a tree-like stochastic temporal network 207
6.5 Synchronisation 208
Appendix A Discrete-time random walks on the hue 213
Appendix B Transient and absorbing states of Markov chains 215
Appendix C Derivation of the degree distribution of the Barabási-Albert model 217
Bibliography 219
Index 235
