University of Southampton

Complex Networks

Applying and extending network theory to deal with the large-scale and topologically complex networks found in domains such as biology, computing, geography and knowledge representation. Example topics: constraints on networks due to spatial layout, integration of multiple interacting networks, network sampling, network structure in markets, ontology networks, social networks.

Fundamental research into networks underpins our understanding of many natural and engineered systems, e.g., social organisations, critical infrastructure, software agent systems, sensor networks, evolving populations, ecosystems, brains, economies, cities, and cells. Of particular interest are co-evolutionary networks (where the state of the network nodes co-evolves with the configuration of the network edges) and spatially embedded networks (an important sub-class of networks in which nodes tend to be connected to their spatial neighbours and long distance connections are rare or expensive to maintain). A combination of mathematical and simulation modelling is required to understand how real-world networks arise, persist, and change, and also to explore the functional properties of different topologies and dynamics: for instance, the capacity for a network to support efficient collaboration, to reorganise after attack, or to absorb stress without failing.


Spatially embedded networks

Many real-world networks are embedded in space; e.g., the Internet, social networks, neural networks, etc. It is clear that this spatial embedding often influences the structure of the networks, allowing pairs of nearby nodes to be directly connected while discouraging direct connections between nodes that are distant from one another, for example. Yet networks science has tended to abstract away the spatial organisation of these networks in order to concentrate on the topology of their connectivity. By studying a class of Spatially Embedded Random Networks (SERNs), we are able to answer the question: what does spatial embedding contribute to the structure and dynamics of complex networks? In answering this question we have begun to demonstrate the influence of spatial embedding on connectivity such as the effects of spatial symmetry on conditions for scale free degree distributions, and the existence of small-world spatial networks. One interesting result is the lack of a phase transition to a giant component that is characteristic of some other random graphs. We have also been able to show that spatial embedding tends to increase the complexity of network dynamics.


Co-evolutionary networks

Real-world networks are rarely static structures. The properties of the nodes change over time as people age, species evolve, agents learn or neurons interact. Likewise, the connections between the nodes change as people make and break friendships, ecological interactions shift, agents move in and out of communication range, and synaptic connections strengthen or weaken. In truly dynamic networks, nodes and connections also enter and leave the network. What makes these dynamics especially interesting is that they are coupled – changes in the properties of the nodes bring about changes in their connections, and changes in connections between nodes bring about changes the properties of the nodes themselves. Understanding this kind of co-evolutionary reflexivity is important where systems are changing over time, especially as a consequence of adaptive processes such as learning or evolution. Key contexts include social networks where social ties are the relationships through which affiliations, social attitudes and knowledge diffuse, and these properties provide the context for new social ties to form. Other domains include ecological networks, neural networks and agent populations.