CHARMNET - Characterising Models for Networks

Networks have emerged as useful tool to represent and analyse complex data sets. These data sets appear in many contexts - for example, biological networks are used to represent the interplay of agents within a cell, social networks represent interactions between individuals or social entities such as websites referring to other websites, trade networks reflect trade relationships between countries.

Due to the complexity of the data which they represent, networks pose considerable obstacles for analysis. Typically the standard statistical framework of independent observations no longer applies - networks are used to represent the data precisely because they are often not independent of each other. While each network itself can be viewed as an observation, usually there are no independent observations of the whole network available.

To understand networks, probabilistic models can be employed. The behaviour of networks which are generated from such models can then be studied with tools from applied probability. Even relatively simple models provide challenges in their analysis, with more realistic complex models often out of reach of a rigorous mathematical treatment.

Hence, depending on the network behaviour of interest, it may be reasonable to approximate a complex model with a simpler model. Assessing the error in such an approximation is crucial to determine whether the approximation is suitable. This project will derive characterisations of network models which relate to a common underlying process. This common underlying process will then allow to compare models through comparing their characterisations.

Based on such comparisons, approximate test procedures can be derived by first using the simpler model to obtain the distribution of the test statistic under the null hypothesis and then taking the approximation error into account. In practice, for a given data set, a model would be fitted to the data. This fitting process introduces some variability which in itself will result in some deviations from the model. Using tools from theoretical statistics as well as applied probability, these deviations can again be assessed, with an explicit error term.

The project will exploit the observation that the method for assessing this approximation error is well adapted to analyse so-called graph neural networks, which are emerging as a tool in Artificial Intelligence. Thus the project will yield a new connection between Probability and Artificial Intelligence which will spark ideas beyond the application to network analysis.

The results will be applied to three network sets which are publicly available: protein-protein interaction networks, political blog networks, and World Trade networks. These networks are chosen because of the challenges they pose: there is to date no generally accepted model for protein-protein interaction network; moreover, the data underlying these networks contain a large amount of errors. Political blog data are used as a benchmark; several models have been proposed for these networks, and our approach will allow to compare them quantitatively. World Trade networks are weighted, directed, dynamic and spatial, and thus illustrate the complexity which our approach will be able to tackle.

Key questions which this project addresses are

(1) What is the expected behaviour of complex models for networks? Once the expected behaviour is understood, deviations from it can be exploited to detect anomalies in networks.
(2) How can networks such as infrastructure networks and reporting networks be designed to achieve efficiency and resilience? Understanding the behaviour of models for networks can guide the design of such networks.
(3) How can the interconnectedness of people, things and data be taken into account when drawing statistical conclusions? Tests for assessing models which could include explanatory variables as parameters will be tackled in this project.

Impact will be achieved through lectures, publications, a blogpost, and through existing contacts with

(a) Accenture on anomaly detection in networks
(b) e-Therapeutics, Novo Nordisk and UCB pharma on drug target development and understanding biological disease processes
(c) Legume Technology to improve nitrogen uptake in legumes.

At least two students per year, one undergraduate student and one Master-level student, will be trained in the area of probability, network analysis and AI. The project will also generate outreach events, a blog, and webinars.