Reconstruction of causal networks through discrete optimisation

The study of complex networks is at the heart of an increasing range of scien- tific fields, from microbiology to sociology. This abstract view of structure in sys- tems preserves only the essential information, allowing scientists to tackle otherwise intractable problems. To examine the network underlying a system is key to under- standing, and an increasing array of tools are available to analyse networks. But in many cases the ground truth structure is not a priori known, and instead must be in- ferred. We approach the problem of reconstructing networks from a particular type of data, the traces left by markers diffusing through an underlying network. We first present work based on the novel NETCOVER algorithm, which reduces the task of network inference to the well-known Set Covering problem. We verify the algorithm first on synthetic data, before applying it to data gathered from the social networking site Twitter. We then outline three extensions to the basic algorithm, demonstrating how some of its original assumptions may be relaxed. We first show that reconstruction can be performed even in the presence of noise, and then when the system in question is not completely closed. Finally we relax the assumption of stationary markers, showing that when markers evolve as they propagate, this extra . information can be used to achieve improved reconstructions. We demonstrate the algorithm on data gathered from the international news media. In the final chapter we build on the NETINF algorithm, independently developed by another group, first comparing its performance to our own, before outlining an extension. We introduce explicit modelling of additive noise, where a hidden 'supern- ode' is responsible for multiple seedings into the observed network. We show that this explicit modelling of marker injection improves performance. Finally, we outline the possible future directions for research.EThOS - Electronic Theses Online ServiceGBUnited Kingdo