Complex networks: topology, spectrum and linear processes

The concept of a network, defined as a collection of interconnected nodes or entities, has become a foundation for a new field of inquiry, namely network science. Despite the apparent simplicity of the concept, the pairwise representation of interconnecting nodes has enabled a plethora of insights into the structure of networks and the effects of interactions on dynamic processes. This generality of the network concept has paved the way for novel approaches with the aim of understanding complex systems, from social networks to biological pathways. It has opened up new avenues for research into
the fundamental mechanisms underlying these systems. As such, network science has become a highly active and dynamic field, driving the development of new theoretical frameworks, computational tools, and empirical methods that continuously push the boundaries of knowledge and understanding in numerous science and engineering domains.

The first part of this thesis centres on the structural properties of complex networks and their practical applications. We demonstrate that the orthogonal eigenvectors of the adjacency matrix of a simple, unweighted, and undirected graph are sufficient to recover that graph, albeit potentially not in a unique manner (Chapter 2). This observation led us to uncover co-eigenvector graphs, which are graphs that share the same eigenvectors while having distinct eigenvalues. Co-eigenvector graphs are the dual counterparts of cospectral graphs, which share identical eigenvalues but possess distinct eigenvectors.
In an unweighted graph, the number of walks between node pairs of a particular length can be expressed in terms of the corresponding power of the adjacency matrix. However, deriving a similar solution for the number of paths is significantly more intricate (Chapter 3). We present three distinct analytical solutions in matrix form for computing the number of paths of any length between node pairs, utilising different types of walks and leveraging principles from the mathematical field of combinatorics. The computational complexity of these solutions varies depending on the sparsity of the graph. The effective resistance metric, which characterises the entire network as perceived from the
vantage point of two given nodes, represents a powerful tool for addressing a wide range of challenges in network theory. In Chapter 4, we leverage the information contained in effective resistance to solve the inverse all shortest path problem, wherein a weighted graph satisfying given upper bounds on the shortest path weights between node pairs is sought, with sparsity being a critical consideration. Additionally, we propose a novel graph sparsification algorithm that selectively removes links from an unweighted graph in a stepwise manner, with the goal of either minimising or maximising the effective resistance
of the resultant graph.

The second part of this thesis pertains to linear processes on complex networks, exploring their properties and applications. Our research reveals that a simple process of attraction and repulsion between adjacent nodes on a one-dimensional line, based on the similarity of their neighbourhoods, can effectively group together nodes from the same community (Chapter 5). Our linear clustering process generally produces more accurate partitions than the most prevalent modularity-based clustering methods in the literature, requiring a comparable amount of computational complexity. An empirical part of our research on processes in complex networks became possible thanks to
our network construction based on a unique data set containing each municipality’s area, population and its geographically adjacent neighbouring municipalities. Thanks to this network construction, research became possible on a dynamic network of connected municipal nodes at a national level over the period from 1830 to 2019 (Chapter 6). By connecting the population data, area data and municipal merger data of all Dutch municipalities, we discovered that the logarithm of the municipal area and population size yields an almost linear difference equation over time. Research into the municipal merger process over the period 1830-2019 has shown that 873 of the 1228 Dutch municipalities
have merged into adjacent larger municipalities with a larger population.
Our simulation of municipality mergers based on network effects caused by population growth by municipality resulted in a county-level predictive accuracy of 91.7 % over a 200-year period. Suppose every node within a network exhibits linear internal dynamics of a specific order, and the dynamic interactions between these nodes are also linear. In that case, the entire network conforms to a collection of linear differential equations (Chapter 7). Our study offers an analytical solution for the comprehensive network dynamics in state space form, achieved by merging the fundamental topology and internal linear dynamics of every individual node.