Complex Networks Research

Complex networks manifest themselves in all sorts of ways from physical infrastructure networks such as road and traffic networks and computer communications networks to less tangible networks of relationships such as between groups of people, businesses or behaviours.

We are particularly interested in finding quantitative measures of complexity in graph structures and other spatial arrangements.

Some of the models we are using to explore these ideas include:

The Spatial Prisoners' Dilemma (See CSTN-037)
Random Boolean Networks (See CSTN-039)
Small-World Network Models (See Small-World Examples and CSTN-036 )

The spatial prisoners' dilemma (SPD) consists of a network of nodes or agents that play the prisoners' dilemma game against each other repeatedly, adapting their game playing strategy depending upon the outcomes. In this image, a regular mesh network of neighbours dictates which agents playoff against each other. Blue denotes cooperators, red denotes defectors and the yellow and green represent agents that are changing their strategy.

The emergent spatial pattern is goverened by what fraction or pattern of cooperators/defectors or other strategies are set up as the initial configuration, and a parameter that sets the relative advantage of defecting.

This image was produced by an interactive Java program, but detailed studies need much larger systems to attain statistical significance. Our main game-theory simulation programs are written in the D programming language and allow arbitrary network structures with millions or hundreds of millions of nodes.

See:

Technical Note CSTN-037 - Non-Monotonic Phase Transition Edges in the Spatial Prisoners' Dilemma.

The random boolean network (RBN) models are a generalisation of the 1-d cellular automaton model and comprisea network of nodes each of which hosts a boolean function of some number k of inputs. Each input is randomly connected to one of the other nodes, and the network is evolved either synchronously or using some other update rule, starting from a random pattern of boolean values. Depending upon the connectivity k or distribution of k values the network goes into periodically repeating states or random states or a stable unchanging state or an interesting chaotic state.

The RBN is a useful tool for exploring the consequences of different connectivity distributions and our simulation codes can handle various networks of up to 1 million nodes and a range of different network structures. Of particular interest is the study of scale-free networks - that have an exponential distribution of node connectivities and which have interesting phase diagrams and regions of chaotic behaviour.

The images show evolution (shown downwards) in time of a 64 node random boolean network (nodes shown horizontally), where red/white denote the different logical states, and grey/mauve show sites that are changing states. At low connectivity (left) the network rapidly becomes locked into unchanging states, at intermediate "edge-of-chaos" connectivity (middle) there is a mix of fixed and changing nodes, with some in a periodic pattern, and at high connectivity (right) most nodes are changing chaotically.

See:

Technical Note CSTN-039 - Simulating Large Random Boolean Networks.

[ Ken's Homepage | Massey University | IIMS ]