Amorphous computation, random graphs and complex biological networks

Lead Research Organisation: University of Leeds
Department Name: Sch of Computing

Abstract

In this ``information age'', computation, communication and massive information handling have become the bread and butter of modern society. Internet networks, the web, and popular peer-to-peer networks are all examples of the transition we are witnessing from local, centralised computers to massive distributed networks of relatively low-power individual resources. These are our first glimpses of the amorphous computers of the future. More generally, amorphous computers include any large-scale network of computational units or processes that are connected through a flexible and constantly changing network of interactions. These may be swarms of microscopic robots or large sensor-arrays that monitor climate or pollution. The critically important feature common to these kinds of self-organising distributed systems is that the desired computation emerges and is not explicitly preprogrammed.The transition to amorphous computing brings with it enormous potential as well as risk (such as the virus epidemics that plague the internet). To exploit the advantages and avoid the dangers of amorphous computing, fundamentally new ways of coping with complexity are needed. To do so we plan to develop appropriate mathematical models and tools, on the one hand, and to derive appropriate engineering principles inspired by successful systems, on the other.One of the unifying features of amorphous computers is their active network structure. Thus, a natural mathematical entity for their description is the graph: a structure with nodes (processors) and edges (connections). Since by their very nature, the network structure of amorphous computers is non-prescribed, the study of random graphs is especially promising. To extend the theory of random graphs to real-world applications, new mathematics needs to be developed, including new families of random graphs, new tools for simulating their growth and dynamics and new methods for analysing the dynamics that takes place on these graphs. A key part of this proposal is the development of these tools and their application to specific models of amorphous computers, and ultimately to real systems (such as P2P networks and sensor arrays).One of the challenges of amorphous computing is to find useful analogies that provide insight into the requirements, capabilities and limitations of the systems at hand. In this proposal, we will draw inspiration from biological systems and the powerful computation they perform. Computational aspects of biological functions are found in almost any task: from evolution, though development, to information processing, and are evident on every level of organisation, including macro-molecules (e.g., protein folding), cells (e.g., regulatory networks of proteins and genes) and higher (neural networks and nervous systems). Built of microscopic, noisy and relatively unreliable components, biological systems are surprisingly effective and efficient. Unlike human-engineered computers, they are also dynamic and highly adaptive machines. They are typically distributed and decentralised, with each component following a set of local rules based on its environment to determine its actions. It is the emergence of a functional and coherent whole from an ensemble of simple and unreliable elements that we would like to capture for our own engineering purposes.

Publications

10 25 50
publication icon
Cohen N (2016) Preferential duplication graphs in Journal of Applied Probability

publication icon
Cooper C (2019) The flip Markov chain for connected regular graphs in Discrete Applied Mathematics

publication icon
Cooper C (2011) The cover time of random geometric graphs in Random Structures & Algorithms

publication icon
Voliotis M (2009) Backtracking and proofreading in DNA transcription. in Physical review letters

publication icon
Voliotis M (2008) Fluctuations, pauses, and backtracking in DNA transcription. in Biophysical journal

 
Description Internet networks, the web, and peer-to-peer networks are examples of the transition from local, centralised computers to massive distributed networks of relatively low-power individual resources. These are our first glimpses of the amorphous computers of the future. More generally, amorphous computers include a network of computational units or processes that are connected through a flexible and constantly changing network of interactions. The important feature common to these kinds of self-organising distributed systems is that the desired computation emerges and is not explicitly preprogrammed. Amorphous computing brings with it enormous potential as well as challenges. To exploit the advantages and avoid the dangers of amorphous computing, fundamentally new ways of coping with complexity are needed. To do so we have developed mathematical models and tools, and to studied appropriate engineering principles inspired by biological networks.

One of the unifying features of amorphous computers is their active network structure. In this project, we have studied how networks operate, and how information is processed on them, inspired by biological systems and the powerful computation they perform. Computational aspects of biological functions are found in almost any task: from evolution, though development, to information processing, and are evident on every level of organisation, including macro-molecules (e.g., protein folding), cells (e.g., regulatory networks of proteins and genes) and higher (neural networks and nervous systems). Built of microscopic, noisy and relatively unreliable components, biological systems are surprisingly effective and efficient. Unlike human-engineered computers, they are also dynamic and highly adaptive machines. They are typically distributed and decentralised, with each component following a set of local rules based on its environment to determine its actions. It is the emergence of a functional and coherent whole from an ensemble of simple and unreliable elements that we would like to capture for our own engineering purposes.

The project consisted of five work packages. In this workpackage we studied the spread of disease on networks of individuals who can fall ill, pass the disease on and recover. To this we added the model ingredient that humans also communicate with their neighbours, and formulated one of the first models of this kind. As this communication could include information about whether or not they have heard about the disease, neighbours can learn from this that a disease is around, and take protective measures. We were trying to find out if this can stop a disease from spreading. Our model has model not just one network, but two, overlaying networks: one network on which the disease can spread, and one on which the information can spread. We found that indeed the passing of information about a disease can stop a disease from spreading, but only if the two networks overlap sufficiently. In this way the information network forms an amorphous computer that can give an indication about where on the transmission network the disease is present.

We also wanted to find out how human networks structure themselves, and how this structure affects the way we function in such a network. Together with colleagues in Southampton we made a model to show how the tendency of humans to form connections with others with similar features can structure human societies. We studied social behaviour on these networks, and discovered that an essential structure for social behaviour to emerge and persist, is present in such networks. We then found evidence of this structure in a large internet community. Our work has provided examples of how a collection of agents (humans in our case) who are not programmed for a certain, through their actions can shape a network and perform complicated tasks, much as an amorphous computer would.
Exploitation Route International symposium held 2010. Follow on funding. PhD & PDRA destinations.
Sectors Healthcare,Other

 
Description Advance-Africa
Amount £9,747 (GBP)
Funding ID Amorphous Computing 
Organisation Advance Africa 
Sector Charity/Non Profit
Country Kenya
Start  
 
Description Advance-Africa
Amount £9,747 (GBP)
Funding ID Amorphous Computing 
Organisation Advance Africa 
Sector Charity/Non Profit
Country Kenya
Start  
 
Description Royal Society of London
Amount £12,000 (GBP)
Organisation The Royal Society 
Sector Charity/Non Profit
Country United Kingdom
Start  
 
Description University of Leeds
Amount £46,393 (GBP)
Funding ID University Research Scholarship 
Organisation University of Leeds 
Sector Academic/University
Country United Kingdom
Start 01/2015 
End 12/2017
 
Description University of Leeds
Amount £48,230 (GBP)
Funding ID University Research Scholarship 
Organisation University of Leeds 
Sector Academic/University
Country United Kingdom
Start 01/2013 
End 06/2017
 
Description University of Leeds
Amount £55,380 (GBP)
Funding ID Amorphous Computing 
Organisation University of Leeds 
Sector Academic/University
Country United Kingdom
Start 01/2006 
End 09/2010