Table of Contents
1 Introduction 1
1.1 Why studying complex networks . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Scope of complex networks research . . . . . . . . . . . . . . . . . . . . 1
1.3 Scope and contribution of thesis . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Modeling of Complex Networks: The Set of Graphs 5
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Random graph of Erd˝os-R´enyi . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Small-World graph of Watts-Strogatz . . . . . . . . . . . . . . . . . . . 6
2.4 Scale-Free graph of Barab´asi-Albert . . . . . . . . . . . . . . . . . . . . 7
3 Characterization of Complex Networks: The Set of Graph Measures 9
3.1 Structural measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Spectral measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Analyzing the Relationship Between Graph Measures 15
4.1 Visual analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Correlation analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Principal component analysis . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Laplacian and Normalized Laplacian Spectrum of Complex Networks 27
5.1 Laplacian spectrum of complex network models . . . . . . . . . . . . . 27
5.1.1 Random graph of Erd˝os-R´enyi . . . . . . . . . . . . . . . . . . . 28
5.1.2 Small-world graph of Watts-Strogatz . . . . . . . . . . . . . . . 30
5.1.3 Scale-free graph of Havel-Hakimi . . . . . . . . . . . . . . . . . 31
5.2 Laplacian spectrum of empirical networks . . . . . . . . . . . . . . . . . 32
5.3 Normalized Laplacian spectrum of empirical networks . . . . . . . . . . 34
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
i
ii CONTENTS
6 Algebraic Connectivity of Complex Networks 37
6.1 Algebraic connectivity in random graph of Erd˝os-R´enyi . . . . . . . . . 38
6.1.1 Asymptotic behavior in random graph of Erd˝os-R´enyi . . . . . . 38
6.1.2 Minimum nodal degree in random graph of Erd˝os-R´enyi . . . . 39
6.1.3 Analytical approximation for algebraic connectivity in random
graph of Erd˝os-R´enyi . . . . . . . . . . . . . . . . . . . . . . . . 40
6.1.4 Verification of analytical approximation . . . . . . . . . . . . . . 41
6.2 Relationship between algebraic, node and link connectivity in random
graph of Erd˝os-R´enyi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7 Spectral Radius of Complex Networks 47
7.1 Upper bounds for spectral radius . . . . . . . . . . . . . . . . . . . . . 47
7.2 Spectral radius of empirical networks . . . . . . . . . . . . . . . . . . . 49
7.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
8 Relationship Between Algebraic Connectivity and Robustness of Complex Networks to Node and Link Failures 55
8.1 Relationship between algebraic connectivity and classical connectivity
measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.2 Relationship between algebraic connectivity and classical connectivity
measures in complex network models . . . . . . . . . . . . . . . . . . . 57
8.2.1 Random graph of Erd˝os-R´enyi . . . . . . . . . . . . . . . . . . . 57
8.2.2 Small-World graph of Watts-Strogatz . . . . . . . . . . . . . . . 59
8.2.3 Scale-Free graph of Barab´asi-Albert . . . . . . . . . . . . . . . . 61
8.2.4 Comparison between complex network models . . . . . . . . . . 63
8.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
9 Influence of Network Structure on Robustness of Complex Networks 67
9.1 Bounds for algebraic connectivity . . . . . . . . . . . . . . . . . . . . . 68
9.2 Relationship between classical connectivity and probability distribution
of algebraic connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 68
9.3 Behavior of algebraic connectivity under random failures . . . . . . . . 70
9.3.1 Random graph of Erd˝os-R´enyi . . . . . . . . . . . . . . . . . . . 71
9.3.2 Small-World graph of Watts-Strogatz . . . . . . . . . . . . . . . 72
9.3.3 Scale-Free graph of Barab´asi-Albert . . . . . . . . . . . . . . . . 75
9.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
10 Conclusions 81
CONTENTS iii
A Summary Statistics of Graph Measures for Number of Empirical Networks 85
B Dependence of Two Arbitrary Degrees in Random Graph of Erd˝osR´enyi 89
C Minimum of Normalized i.i.d. Binomially Distributed Sequence of
Degrees in Random Graph of Erd˝os-R´enyi 91
D Symbols and Acronyms 95
Bibliography 99
Samenvatting 105
Acknowledgements 107
Curriculum Vitae 109
NGInfra PhD Thesis Series on Infrastructures 113
Abstract
This thesis focuses on the topological characterization of complex networks. It specifically focuses on those elementary graph measures that are of interest when quantifying topology-related aspects of the robustness of complex networks. This thesis makes the following contributions to the field of complex networks. Firstly, the thesis analyses the relationships among a variety of graph measures and proposes a definite set, capable of expressing the most relevant topological properties of complex networks. Secondly, the thesis relies on spectral measures to initiate a classification of the qualitative topological properties that characterize specific classes of complex networks. Thirdly, the thesis illustrates the use of spectral measures in a quantitative characterization of topology-related aspects of the network robustness. Finally, this thesis demonstrates the use of spectral measures in a quantitative characterization of the extent to which the robustness to different types of failures manifests itself in the underlying complex networks structure.