Developing intelligent inference by treating topological patterns in graphs and networks as constraints on a random graph ensemble.

Artificial intelligence of graphs

Capturing in simulations and mathematical form the surface structure of crystals and how they coalesce when heated but not melted.

At the surface of crystals

Applying spectral-like theories to the bipartite network of products and capabilities to find latent potential in countries and firms.

Building blocks of economic complexity

Reconstructing the 3d shape distribution of grains or other objects randomly packed together with access only to 2d slices  through them.

Deducing three dimensions from two

Homer’s Iliad and Wikipedia. One, the first great work in Western literature; the other, the world’s most-used work of reference. The link? Both are the products of collective creativity. The Iliad was created over generations by a series of oral poets, each of whom improved on the previous version, deleting some passages and adding others. Meanwhile, Wikipedia relies on contributions from the public, on the same basis of deleting and inserting. Shared knowledge curation efforts and open source software suggest that explicit cooperation may not be necessary for integrating multiple collaborators in their efforts to achieve a complex goal.
In this project we ask whether anonymous collaboration with constrained freedom can give rise to the spontaneous display of creativity within a non-cooperating group, greater than any one person could achieve alone. By studying simple creativity tasks and the dynamics of games, we devise a theoretical model for collective creativity and extrapolate key design principles for platforms capable of achieving it.
Collective creativity could profoundly extend the limits of human creativity in areas such as scientific collaboration, coding, creative writing and illustration.

Understanding collective creativity: anonymous collaboration under constrained freedom that transcends the creativity of the individual.

Dynamics of collective creativity

Developing new local and global measures for networks derived from social interactions to infer social structure, sentiment and behaviour.

Extracting meaning from social networks

Simulating the molecular structure of materials under pressures so extreme that we are not yet able to study them in the laboratory.

Extreme pressure surprises

Developing radical new approaches to inference and automated decision making using advances in quantum information and statistical physics.

Fundamental advances in machine learning

Understanding the dynamics of memristor networks, a new approach to low-power computation inspired by the structure of the brain.

How to remember currents and voltages

Taming limitations of general relativity, such as the big bang singularity, by formulating theories that admit bouncing or cyclic universes.

Implications of alternative universes

Is space a continuum or is it composed of a discrete set of points? Once a purely philosophical question, there is now a pressing need to describe space and space-time as discretized in order to resolve quantum gravity. Yet despite sophisticated attempts at discretizing space, researchers have failed to construct even the simplest geometries.
In this project we investigate models of discrete space in which continuum-like behavior is recovered at large lengths. We show that if space is discrete, it must be disordered, and develop explicit recipes for growing disordered discrete space by sampling distributions of graphs at low temperature. We also pursue graph formulations of non-Euclidean metrics, especially the Minkowski metric from special relativity.
Models of discrete space and space-time could have profound implications for physics. They may tame the infinities that arise from quantizing gravity, and dispense with the machinery of the real numbers, which has no direct observational support. They also set the stage for digital physics, in which information takes centre stage in describing the universe.

Creating discrete models of space and spacetime that appear continuous over long lengths and set the stage for non-continuum physics. 

Is continuous space an illusion?

Developing a statistical physics model of recursive innovation in which technologies become the building blocks for new technologies.

Is technology a machine for creating itself?

Bootstrap percolation originated as a simple cellular automata model of the spread of infection. Given a set of initially infected sites, in consecutive rounds sites become infected if they satisfy a certain infection rule, for example, more than a given number of their neighbours are infected. Percolation occurs if every node is eventually infected.
In this project we investigate the typical and extremal properties of bootstrap percolation for various infection rules and underlying networks. For sites that are initially randomly infected, we study the critical density of infection that leads to percolation. Alternatively, if the initial infected sites are set by hand, we study how many infected nodes are necessary to infect the whole network.
Bootstrap percolation can be used to model many real-life phenomena, such as pandemics, computer network failure, ferromagnetic behaviour, the spread of voting preferences and information processing in neural networks. A better mathematical theory will help us understand these processes and draw reliable conclusions well beyond what can be achieved through computer simulations.

Advancing the mathematical theory of bootstrap percolation, where active cells on a lattice with few active neighbours cease to be active.

Leaps in long-range connectivity

Trust is a keystone for industry and society. It accelerates transactions in business and it ensures matched standards between seekers and providers. But web search engines are not effective at finding individuals based on trust, such as workers, partners and service providers.
In this project we formulate and build a trust-based search engine that combines technological efficiency with the human inclination towards trust. It recursively harnesses the trusted contacts between individuals to build and track trust corridors: trust between two people based on a pathway of trusted connections between them. Using branching stochastic processes, we develop a mathematical theory of how trust trees grow and how we can efficiently traverse them. We then build an incentivized search engine based on these insights.
By harnessing multiple individuals’ knowledge of their contacts, trust-based search navigates complex social networks to turn six-degrees of separation into a reality. Searching on the basis of trust will help businesses recruit the right workers and citizens choose the right doctors, tradesmen and professional services.

Developing a mathematical theory of how trust trees grow and how we can traverse them to exploit trust corridors in society for searching.

Making six degrees of separation a reality

Examining the effect of public opinion on stock market returns and harnessing social sentiment to make quantitative market predictions.

Markets and the mind

Innovation is to technology what evolution is to life: it is how technology improves and adapts to a changing environment. Yet despite advances in our understanding of evolution, what drives innovation has remained elusive. Is the process of innovation essentially Darwinian—variation, selection and inheritance—or are there fundamentally different forces at work? 
In this project we develop a simple mathematical model of innovation in which technologies are made up of components and new components become available over time. In this expanding space of building blocks, we find that innovation has a structure all its own. While the choice of components plays an important role in determining the innovation rate, this is countered by an intrinsic rate specific to each domain. 
Our work helps structure the empirical investigation of innovation in the real world, and highlights the intrinsic versus intervenable aspects of technological change. Speeding up innovation in sectors such as energy production, software development and drug discovery will have far-reaching effects on sustainability, technological progress and the health of society.

Creating a mathematical model of combinatorial innovation to understand how innovation rates can be influenced as components are acquired.

Mathematical structure of innovation

Modern medicine can access vast amounts of patient-specific data, such as individual genomes, blood bio-markers and medical images. But it fails to use this information effectively. Analysing next-generation data with previous-generation tools causes avoidable patient harm, misses clues to new treatments and contributes to the high failure rate of clinical trials.
In this project we create more powerful mathematical methods for predicting disease outcomes. Most present-day mathematical and machine learning methods have a common Achilles heel. When the amount of information becomes too large, they confuse real patterns with noise and miss the wood for the trees—a breakdown known as overfitting. Our approach to bypassing this is founded on treating topological patterns in medical data as constraints on a random graph ensemble.
More accurate clinical prediction reduces the likelihood of harmful, ineffective treatments and saves lives. Each doomed trial that gets stopped early by better analysis of preliminary data saves over £100m for health services and the drug industry. And rescuing failing trials by identifying appropriate drug recipients broadens the range of available drugs.

Creating powerful mathematical methods for predicting the outcomes of diseases that pinpoint the right treatments and speed up drug trials.

Mathematics for personalized medicine

The design of efficient exchange devices is an important problem in engineering and biology. In industrial settings a variety of heat exchangers are employed, such as plate, coil and counter-current devices. In nature, lungs, leaf venation and blood circulation networks have evolved to meet multiple physiological needs. A distinctive feature of the biological examples is their fractal structure, with branching and usually anastomosing geometries. The fractal design provides a large surface for exchange but within a compact volume.
In this project we design optimal heat exchangers for industrial and domestic use that incorporate the design efficiencies of their biological counterparts. We develop a theory that links efficiency to the geometry of the exchange surface and supply network. By crumpling the exchange area into a fractal surface, our designs can be optimized for volume as well as performance. They are especially suited to 3D printing because they are not load bearing.
Optimal heat exchangers increase the efficiency of industrial processes and reduce the cost and size of passive heat exchange in houses. The underlying theory also provides insights into respiration, which may help develop diagnostic tests for breathing disorders.

Designing optimal self-similar structures for compact counter-current heat exchangers to reduce heating costs and greenhouse emissions. 

Moving mass while keeping heat stationary

Investigating the adverse effects of information asymmetry and deliberate errors in social media and the press and attempts to remedy them.

News and fake news in a connected world

Densely packed objects of a similar shape, from rocks to foams to spheres, have intrigued mathematicians since the ancients. The mechanical properties of these materials are determined by how big the gaps are between them—in particular, how close they are to their maximum random-packed density. Predicting this maximum, and how the material properties vary around it, is a geometric and physics challenge.
In this project we investigate the packing of spheres of the same size and mixtures of spheres with a range of sizes. While simulating packing is easy to program, the running time scales poorly with system size. To overcome this obstacle, we develop new mathematical techniques for determining the properties of dense packings using a simplified 1d model. This powerful approach captures essential features of higher-dimensional systems.
Understanding how objects fit closely together under pressure or by design is at the heart of materials science and branches of fluid dynamics. Predicting the behaviour of dense packings also sets the stage for reverse-engineering new composite materials to have desired properties.

Predicting the geometry and behaviour of densely packed objects in the natural and man-made worlds, from rocks to foams to spheres.

Packing things into a crowded place

The simplest model of dimension is the hypercube. When the coordinates are given by a binary string, the distance between two strings is the number of spelling mistakes between them. By considering strings made of up more than two symbols, and connecting strings that differ by just one spelling mistake, the hypercube can be generalized into Hamming graphs. In information theory, messages are sent as strings which are subject to errors in transmission. To correct these mistakes, variants of a string must code for the same message as the string itself. In this way error correction is deeply connected to partitioning the Hamming graph into compact clusters.
In this project, we investigate the spectral properties of subgraphs of the hypercube and Hamming graphs. By studying a diffusing population on these graphs, we develop an analogy between mutational robustness and the eigenvalues of subgraphs that code for the same phenotype.
The spectral theory of Hamming graphs has direct applications to the theory of neutral evolution, in which biological information is carried by strings of nucleotides or amino acids. It is also at the heart of Hamming and other error correcting codes, and Hamming graphs feature in association schemes in coding theory.

Exploring the spectral properties of subgraphs of the hypercube and Hamming graphs for insights into coding theory and models of evolution. 

Point, line, square, cube, tesseract

Using ideas from statistical physics to reconstruct the average properties of financial networks from partial sets of information.

Reconstructing a credit network

To be sure of achieving a goal in the face of an uncertain future, individuals and organizations pursue plans that can cope with mistakes and unexpected events. One way of doing so is to choose a robust plan: one that is able to absorb any one setback and thereby achieve the goal with certainty. A different strategy is to choose a repairable plan: one that can be easily modified in the face of setbacks such that the goal is achieved, even though the original plan might have failed without modification.
In this project we develop a theory of systems that achieve resilience by being repairable instead of robust. Our approach is to minimize the typical cost of a workaround, averaged over all possible failure modes. We deduce design principles for easily repairable systems and show that repairability is a superior strategy whenever the number of failure modes is high.
Adopting a paradigm of repairability will increase the resilience of technologies and infrastructure to natural and man-made disasters when the next type of failure mode is hard to predict. This includes communication grids, transport networks and technologies for exploring space. It also suggests alternative strategies for sustainability in the face of environmental change.

Developing a new approach to resilience in which mistakes and unexpected events are mitigated by easy repairs rather than redundancy.

Repairable as an alternative to robust

Most simple rules give rise to simple behaviours. But occasionally they generate surprisingly rich and varied dynamics. Some simple rules, such as Conway’s game of life, are even equivalent to a universal Turing machine and can compute any computable function. While applying simple rules is easy, deducing the rules from observed behaviour is both important and usually hard, as evidenced by the deduction of the laws of physics through science.
In this project we investigate different families of simple rules for discrete dynamics. We help classify elementary cellular automata by deducing general characteristics of their behaviour. We study the self-assembly of polyominoes and the reverse engineering of structures made from them. In simple models of competition, mathematical models help us track the long-term behaviour of a population.
Reverse engineering simple rules that generate desired behaviour can help us design efficient algorithms and low-cost methods for manufacturing. Understanding which rules give rise to dynamics that are neither fully stable nor entirely chaotic may help design systems for artificial life and synthetic biology.

Understanding complex dynamical behaviours generated by simple rules, such as cellular automata, polyominoes and models of competition.

Surprising results of simple rules

Technological progress is widely acknowledged as the main driver of economic growth, so any method for forecasting technological change is potentially very useful. But given that technological progress depends on innovation—generally thought of as something new and unanticipated—forecasting it might seem to be an oxymoron. In fact there are several postulated laws for technological improvement, such as Moore’s law and Wright’s law, but these are technology-dependent and we do not know how confident to be in their predictions.
In this project we investigate how to combine the forecasts of many technologies to make reliable distributional forecasts for a given technology. We use network theory and time series analysis to analyse performance curves and the large historical records of patenting activity to map the progress of technological ecosystems into the future.
The ability to forecast technological change with specified uncertainties can provide a foundation for a theory of economic growth. It can also offer clear recommendations for sustainability investments, where long-term planning is key. From a policy perspective, our insights provide an objective point of comparison to expert forecasts, which can be biased by vested interests.

Forecasting the rate of technological progress by harnessing empirical regularities captured by Moore’s law and Wright’s law.

The future of technological progress

Networks represent interactions between multiple elements. Widely accessible and large data sets makes it easy to build networks, but extracting meaning from them remains a challenge. Part of the problem is that mathematical methods for characterizing networks are primitive and sundry. While the theory of graphs—idealized networks containing internal symmetry—is more advanced, the mathematical foundations for both networks and graphs, and their relation, are underdeveloped.
In this project we investigate new mathematical methods to describe the topology and geometry of networks and graphs, without regard to the kinds of data from which they are derived. The broad range of techniques under development include applications and extensions of spectral graph theory, tailored graph ensembles, replica methods, community detection and enumerative combinatorics.
A deeper understanding of network and graph structure underpins many other research endeavours. Examples range from biomedical data for personalized medicine to predicting behaviour from social interaction networks to the stability of interconnected financial institutions.

Creating mathematical tools for characterizing the structure of ideal graphs and irregular networks, and the behaviour of processes on them.

The structure of how things relate

Ever since Maxwell’s demon helped establish the link between thermodynamics and information, scientists have been formulating the thermodynamics of memories, information flows and feedback processes, especially in the 21st century. Quantum information thermodynamics extends these ideas to quantum measurement and feedback.
In this project we investigate the relation between information and energy in the classical and quantum regimes. Using analytical techniques and simulations, we pursue a collection of hypotheses about the physical nature of information, how to extract energy from fluctuations in the environment, and new technologies that take advantage of these and further insights.
A better understanding of information thermodynamics will help advance the nascent fields of quantum computing, nano-scale devices and biomolecular engineering. Sustained energy extraction could reduce the need for batteries in small autonomous devices. Quantifying the energy required by organisms and synthetic devices to gather and act on information could help form a foundational theory of life and artificial life.

Understanding the physical nature of information and how it relates to energy transfer and new technologies that make use of these insights.

Thermodynamics of information

Applying ideas from diversification and cascading failures to mitigate the propagation of risk across inter-connected institutions.

What to do when failure is contagious

A fractal has the property that any part of it, when magnified, resembles the whole. Remarkably, biology employs fractal designs to achieve high efficiency: spongy bone for stiffness and self-similar spiral shells for pressure resistance. But in the man-made world, fractal designs are rarely used for mechanical efficiency. Transmission towers and the branching columns of Gaudi’s cathedral hint at fractal design principles; but the small amount of hierarchy and lack of quantitative understanding suggest these are heuristic.
In this project we create a new class of light and strong structures based on fractal principles with new strength-to-mass scaling laws. Our fractal structures offer extraordinary mechanical efficiency because the advantage achieved at each generation can be passed on to the next generation, and so on down to the smallest scale.
Fractal structures can extend the limits of architecture and civil engineering. They can increase the range and payload capabilities of drones and planes. In space, where launching structures is weight-critial, they offer new opportunities for building space stations and exploring space.

Using fractal, or self-similar, patterns to design the lightest possible load-bearing structures with new strength-to-mass scaling laws.