Network of Excellence in Internet Science

STRUCTNET

Algebraic Structure of Networks

Partners: London School of Economics, Technische Universiteit Delft, University of Hertfordshire

Surprisingly little is known about the algebraic properties of networks and graphs. Undirected networks fare better because their adjacency matrices are symmetric, which results in real eigenvalues, whereas much less is known about directed networks. In both cases, spectral theory provides information about the topological and other properties of networks that we understand only partially. For example, the intuitive meaning of a network’s eigenvalues is known only for a few eigenvalues and for a few kinds of networks. Our ability to design and analyse complex, large-scale networks, therefore, is correspondingly limited. In this project we will adopt a strongly algebraic perspective to analyse the properties of graphs.

We begin with the applied problem of verifying the efficiency gains in the stability analysis of interdependent networks when suitably defined associated matrices commute. In the second activity we will attempt to relate a network’s algebraic invariants such as its semigroup to its spectrum, with a specific emphasis on developing a formal connection between the algebraic structure theory of semigroups to the decomposition of graphs. The third and final activity is an open-ended exploration of graph spectra that will start with an attempt to extend graph spectral theory to account for local graph properties and not just global aggregate properties. We will publish the theorems and engineering methodology results in mathematical and networking journals and conferences.

Deliverables

Open Call Project Structnet Deliverable 1.1: Construction of Interdependent Networks and Efficiency Improvements in their Stability Calculation

Open Call Project Structnet Deliverable 2.1: Algebraic structure of graphs and semigroups, and its relationship to graph cospectrality

Open Call Project Structnet Deliverable 3.1: Mathematical exploration of the local and global spectral