Table of Contents

1 Introduction 1
1.1 Network reconstruction from spectra . . . . . . . . . . . . . . . . . . . 2
1.2 Graph energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Inverse line graph algorithms . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Random line graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Social networks with community structure . . . . . . . . . . . . . . . . 9
1.6 Randomness of brain networks . . . . . . . . . . . . . . . . . . . . . . . 11
I Reconstructability and Energy of Networks 13
2 Spectral Perturbation and Reconstructability 15
2.1 Spectral Perturbation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Description and deÖnition of reconstructability . . . . . . . . . . 15
2.1.2 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 The Reconstructability of random graphs . . . . . . . . . . . . . . . . . 19
2.2.1 Weibullian probability distribution of p (N) . . . . . . . . . . . 19
2.2.2 E[p (N)] as a function of N and p . . . . . . . . . . . . . . . . 19
2.3 The Reconstructability of Other Networks . . . . . . . . . . . . . . . . 21
2.3.1 Scale-free networks . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Small-world networks . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3 Deterministic graphs . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 The Linear Scaling Law With Eigenvector Perturbation . . . . . . . . . 26
2.5 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Graph Energy 29
3.1 Graph energy vs. m0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Deterministic graphs . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Graph energy vs. m1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
vi
viii CONTENTS
3.3 Ináuence of assortativity on graph energy . . . . . . . . . . . . . . . . . 33
3.3.1 Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 Grid graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.3 Random trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.4 Small-world graphs . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.5 Scale-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
II Line Graphs and Root Graphs 39
4 MARINLINGA 41
4.1 Link adjacency matrix (LAM) and line graph . . . . . . . . . . . . . . 41
4.2 Properties of the LAM . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.1 The basic forbidden link adjacency patterns in a LAM . . . . . 44
4.3 MARINLINGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.1 Matrix relabeling . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.2 Construction algorithm . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.3 Worst case complexity of MARINLINGA . . . . . . . . . . . . 58
4.4 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5 ILIGRA 61
5.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Theoretical preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.6 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.7 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.7.1 The link density of line graphs . . . . . . . . . . . . . . . . . . . 74
5.8 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6 Random Line Graphs 77
6.1 Theoretical preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.1.1 Formation of line graphs . . . . . . . . . . . . . . . . . . . . . . 78
6.1.2 The bandgaps of the number of links L in line graph H (N; L) . 79
6.2 A random line graph model . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 The assortativity of (H; G) during the merging process . . . . . . . . . 86
6.3.1 Random line graphs with cliques of the same size sj = S for
j = 1; 2;    ; C . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.2 Heterogeneous random line graphs with cliques of di§erent sizes 93
CONTENTS ix
6.4 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
III Social Networks and Brain Networks 97
7 Social Network Modeling 99
7.1 The representation of social networks . . . . . . . . . . . . . . . . . . . 100
7.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.1.2 Hypergraph representation . . . . . . . . . . . . . . . . . . . . . 101
7.1.3 An illustrative example . . . . . . . . . . . . . . . . . . . . . . . 102
7.2 Properties of social networks . . . . . . . . . . . . . . . . . . . . . . . . 103
7.2.1 Topological properties . . . . . . . . . . . . . . . . . . . . . . . 103
7.2.2 Spectral properties . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.3 Characterizing the real-world social networks . . . . . . . . . . . . . . . 106
7.3.1 ArXiv coauthorship networks . . . . . . . . . . . . . . . . . . . 106
7.3.2 IMDB actor collaboration network . . . . . . . . . . . . . . . . 107
7.3.3 The SourceForge software collaboration network . . . . . . . . . 108
7.4 Modeling of social networks . . . . . . . . . . . . . . . . . . . . . . . . 109
7.4.1 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.4.2 Properties of the growing hypergraph model . . . . . . . . . . . 112
7.5 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8 Randomness of Brain Networks 117
8.1 Spectral randomness metric . . . . . . . . . . . . . . . . . . . . . . . . 117
8.2 Metrics partially indicating randomness . . . . . . . . . . . . . . . . . . 119
8.3 Randomness of small-world graphs . . . . . . . . . . . . . . . . . . . . 120
8.3.1 Non-repetitive rewiring . . . . . . . . . . . . . . . . . . . . . . . 120
8.3.2 Randomness of small-world graphs . . . . . . . . . . . . . . . . 120
8.4 Randomness of brain networks . . . . . . . . . . . . . . . . . . . . . . . 121
8.4.1 Description of brain networks . . . . . . . . . . . . . . . . . . . 121
8.4.2 The structure coe¢ cient of brain networks . . . . . . . . . . . . 123
8.5 Chapter conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9 Conclusions 129
9.1 Contribution summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
A Properties of the matrix Ek 135
B Quality of the bound of  137
x CONTENTS
C The Initialization of MARINLINGA When s3 = 0 139
C.1 When s1 = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
C.2 When s1 = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
C.3 When s1 = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
C.4 When s1  4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
C.4.1 When s2  3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
C.4.2 When s2  2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
D Proof of the adapted semicircle law 147
E Notation 149
Bibliography 151
Samenvatting (Summary in Dutch) 159
Acknowledgements 161
Curriculum Vitae 163
Publications by the author 165
NGInfra PhD Thesis Series 167

Abstract

The infrastructure networks, including the Internet, telecommunication networks, electrical power grids, transportation networks (road, railway, waterway, and airway networks), gas networks and water networks, are becoming more and more complex. The complex infrastructure networks are crucial to our human society, and it has been a hot research …eld to make our complex infrastructure networks more robust and optimize the performance of them. Besides man-designed infrastructure networks, complex networks also cover many natural networks, such as social networks, ecological networks, and biological networks. In order to tackle some of the di¢ cult social issues, ecological problems, and unsolved medical problems, we must learn how these natural complex networks organize, operate, and function. Complex networks can be represented by graphs. A graph consists of a collection of nodes and a collection of links that connect the nodes. A graph is uniquely described by its adjacency matrix, of which the entry on row i and column j is one only if node i and node j in the graph is connected by a link, otherwise the entry is zero. Each adjacency matrix is associated to a unique set of eigenvalues and corresponding eigenvectors. The eigenvalues and corresponding eigenvectors of a graph, also called the spectrum of the graph, contains all the information of the graph, and the topological/physical meanings of some eigenvalues and eigenvectors are already known. The knowledge on the spectra of networks is of crucial importance to the many aspects of the researches on complex network, such as connectivity of networks and virus spreading in networks. The line graph l (G) of a graph G has a set of nodes mapping the set of links in G, and two nodes in l (G) are adjacent if and only if the corresponding links in G have a node in common. Some problems of graphs can be transformed to much easier ones in the domain of line graphs. For example, partitioning the nodes to …nd the overlapping communities in a graph can be done by partitioning the links in the line graph of the concerned graph. Moreover, the line graphs often share common features with real-world complex networks, like highly clustered and assortative mixing. Hence, the line graphs are considered by many to model real-world complex networks. The robustness and optimization of complex network is a rather broad research fi…eld. We focus on the reconstruction of complex networks from the spectral domain and the line graph domain. This thesis is organized as follows. We …first study the reconstruction of networks from their eigenvalues and eigenvectors and the spectral properties of networks. In the second part of this thesis, we present two algorithms which reconstruct networks from the line graph domain, the properties of the line graphs, and a random line graph model. We at last give the research results on two types of real-world networks. The adjacency matrix of a graph can be computed with its eigenvalues and eigenvectors. When some of the eigenvalues are set to zero, the adjacency matrix can still be correctly computed. We propose a measure, the reconstructability coefficient, de…fined as the maximum number of eigenvalues that can be removed. We …find that the reconstructability coefficient is linear function of the size of the network for all networks that we have studied. We give some results on the spectral metric, the energy of a graph, which is de…fined by the sum of the absolute value of all the eigenvalues. We also explore the relations between graph energy and the topological metric, assortativity, for many different types of networks. For the reconstruction of networks from the line graph domain, we propose two algorithms Marinlinga and Iligra. While all previous algorithms rely on Whitney’’s theorem, Marinlinga is based on the principle of link relabeling and endnode recognition. Iligra reconstructs the graphs from the line graph domain with the linear time complexity. This thesis extends the researches in the line graph domain. We fi…nd that the number of links in a line graph with a fi…xed number of nodes can not take some consecutive natural numbers, and these numbers are called a bandgap of the line graph. We present the exact expressions of the bands and bandgaps of the number of links in line graphs. In order to facilitate the researches in the line graph domain, we propose a model which randomly generates line graphs. The essence of our model is to merge step by step a pair of nodes in cliques, subjecting to some rules to ensure that the resulting graphs are line graphs. Thanks to the random line model, a method to generate a serial of graphs of which the assortativity increases linearly has been invented. This thesis studies two types of real-world networks: social networks and human brain networks. We characterize the overlapping community structure of the social networks of ArXiv coauthorship, IMDB actors collaboration and SourceForge collaboration, and propose a growing hypergraph model, based on preferential attachment. The proposed hypergraph model captures the fundamental properties including the power-law distributions of group size, group degree, overlapping depth, individual degree and interest-sharing number of real-world affiliation networks, and reproduces the properties of high clustering, assortative mixing and short average path length of social networks. To study brain networks, we propose a spectral randomness metric to quantize the randomness of networks. Based on the randomness measuring method, we have found that the brain networks of Alzheimer’s disease are statistically more random than the healthy brain networks.

Terug naar overzicht