Except for the empty graph, we show that the orthogonal matrix X of the adjacency matrix A determines that adjacency matrix completely, but not always uniquely. The proof relies on interesting properties of the Hadamard product Ξ = X ◦ X. As a consequence of the theory, we show that irregular co-eigenvector graphs exist only if the number of nodes N ≥ 6. Coeigenvector graphs possess the same orthogonal eigenvector matrix X, but different eigenvalues of the adjacency matrix. Co-eigenvector graphs are the dual of co-spectral graphs, that share all eigenvalues of the adjacency matrix, but possess a different orthogonal eigenvector matrix. We deduce general properties of co-eigenvector graph and start to enumerate all co-eigenvector graphs on N = 6 and N = 7 nodes. Finally, we list many open problems.@en

Although resource management schemes and algorithms for networks are well established, we present two novel ideas, based on graph theory, that solve inverse all shortest path problem. Given a symmetric and non-negative demand matrix, the inverse all shortest path problem (IASPP) asks to find a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix are not larger than those of the demand matrix. In contrast to many inverse shortest path problems that are NP-complete, we propose the Descending Order Recovery (DOR) that exactly solves a variant of IASPP, referred to as optimised IASPP. The network provided by DOR minimized the number of links and the sum of the link weights among all the graphs with the same shortest path weight matrix. Our second proposed algorithm, Omega-based Link Removal (OLR), solves the optimised IASPP by utilising the effective resistance from flow networks. The essence of our idea is the applications of properties of flow networks, such as electrical power grids, to compute the needed resources in path networks subject to end-To-end demands, such as telecommunication networks where quality of service constraints specify the end-To-end demands.

@en

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.@en

We propose a linear clustering process on a network consisting of two opposite forces: attraction and repulsion between adjacent nodes. Each node is mapped to a position on a one-dimensional line. The attraction and repulsion forces move the nodal position on the line, depending on how similar or different the neighbourhoods of two adjacent nodes are. Based on each node position, the number of clusters in a network and each node's cluster membership is estimated. The performance of the proposed linear clustering process is benchmarked on synthetic networks against widely accepted clustering algorithms such as modularity, Leiden method, Louvain method and the non-back tracking matrix. The proposed linear clustering process outperforms the most popular modularity-based methods, such as the Louvain method, on synthetic and real-world networks, while possessing a comparable computational complexity.

@en

This article studies the dynamics of complex networks with a time-invariant underlying topology, composed of nodes with linear internal dynamics and linear dynamic interactions between them. While graph theory defines the underlying topology of a network, a linear time-invariant state-space model analytically describes the internal dynamics of each node in the network. By combining linear systems theory and graph theory, we provide an explicit analytical solution for the network dynamics in discrete-time, continuous-time and the Laplace domain. The proposed theoretical framework is scalable and allows hierarchical structuring of complex networks with linear processes while preserving the information about network, which makes the approach reversible and applicable to large-scale networks.

@en