Making Sense Of Networks
4 MAY 1999
"Biological and Economic Network"
Dr Eric Bonabeau
Santa Fe Institute, New Mexico, U.S.A.
Director of Research : Eve Mitleton- Kelly
London School of Economics
Houghton Street
London WC2A 2A
Dr Eric Bonabeau who has studied insect and human social organisations introduces network theory and analysis of a number of examples. Network structure and dynamics were discussed as well as function and evolution. The manipulation of computer models can give a better appreciation of hidden structure, phase change and possible emergent properties of real systems. Understanding biological networks helps in making sense of networks in the economic and business world.
Compiled For The L.S.E. by Geoffrey J.C. Higgs
Introduction
We are surrounded by networks of all kinds: computer networks, road networks, ecological networks, economic networks etc. We are collections of biological networks such as the neural and immune system and we belong to many different social networks. Although all these networks operate over a wide spectrum of scales and implement a huge variety of functions they may share essential structural and/or dynamical features. By understanding the operating principles we can formulate better strategies for managing commercial organisations.
Network Structure:
Networks can be represented by graphs consisting of points(nodes) and connecting lines(connections or links) between them. Usually the distribution of nodes and links is not homogeneous and may contain structure which can be brought out. Nodes may be permanent or transitory and may represent variables which may be digital or analogue in function. For example node A may represent the fox population in an ecosystem and be connected to node B which is the rabbit population. The link would indicate that foxes eat rabbits and it would be directional in that the reverse is not true. As the foxes go down the rabbits come up but the relationship may also be influenced by links to other nodes in the system which would affect the fox and rabbit population. Links can themselves have a certain 'strength' of connection; how much foxes like rabbits perhaps or it might be composite and take a number of factors into consideration.
What the nodes and links represent depends on what the model is designed to do. In a network simulation of a company the nodes might be divisions or employees and the links interaction between them. Or it might be a network of companies with links consisting of goods money or information flow. Neural networks consist of neurons and synapses, phone networks have switching stations, data bases will have correlations between words and social networks may have many informal connections of varying strength or interaction. All systems are embedded to some extent in a larger environment and the extent to which it is considered in isolation is a modelling one. In real situations, even if there are no apparent links between a system and its environment the unexpected may happen. The dinosaurs were no doubt living quite happily until a meteor hit the Earth about 65 million years ago.
The aim of a graph is to identify central or principal nodes and to get some idea of the overall connectivity, but though a graph may seem an obvious way to visualise the distribution of nodes and links it doesn't take many points and lines to become totally confusing.A simulation can be projected as a three dimensional graph on a computer monitor though human perception has almost as much difficulty in interpreting this and a number of algorithms have been developed to modify the network in order to reveal hidden structure.
A number of technical terms have sprung up in order to describe structure more formally. The 'degree' of a node is the number of connections it has with other nodes. The 'centrality' of a node is the fraction of the network to which the node is connected. 'Global centrality' is a measure of proximity to all other nodes and found by dividing the sum of the shortest paths to all other nodes into one. Thus a globally central node is one connected with the fewest steps to all other nodes. A 'peak' is a node which has a large number of connections and 'bridges' are links between peaks. 'Betweenness' is a measure of how often a node is visited in going from one node to another via the shortest path. For example a graph of the network of cities in Russia in the 12th century shows that each was of equal importance in terms of trade but by the 15th century Moscow had emerged as the most important and had the highest betweenness.
Algorithms can be used on a computer generated image to stretch or shrink its dimensions in order to reveal hidden structure. Space on the graph can be made a function of link length, crossings minimised and clustering of nodes revealed. A graph of the primate visual cortex can be partitioned by reducing links until the two visual nerve pathways are clearly visible. Nodes can be sorted in terms of their connectivity using a 'force directed' algorithm in which nodes drag other nodes to themselves according to their strength of connections.
One of the important questions to ask of a network is whether it is possible to reach any node from any other node. If it is found to not be possible then it is an indication that a network must have at least two components. In a network where every node is connected to every other node it is useful to have some measure of the overall degree of connectivity. A 'small world' is one in which it is possible to go from any node to any other node via a small number of connections. 'Small' is measured in 'degrees of separation' (e.g. each person in the world is related to anyone else in the world by six degrees of separation - which is a lot!) Research at the Santa Fe Institute has showed that starting from a regular network such as a uniform grid it is possible simply by rewiring a small number of links to create a small world. This has had important implications for communication networks where satellites have enormously increased the accessibility of the telephone system.
Network Function:
A network may or may not have an identifiable function. An ecosystem has no apparent function. The network is shaped by who eats whom and other selective pressures on the nodes which appear and disappear. The telephone network however has an explicit function: to enable anyone who has a telephone to call anyone else who has a telephone. It's important in this case that the time taken for a message to go from source to destination is a minimum. The blood circulatory system has a function as does the central nervous system. A road system may be planned but a network of footpaths simply has grown. Social networks can come about because people have their own reasons for making connections. Economic alliances may initially come about through local events but in the hands of strategists gain a global function. In other words it may be the case that networks start off by being informal and end up having to be designed. Or they could start off being designed and end up having emergent properties that no one could have foreseen.Though it is important in designing networks for people to take account of a social theory of interactions there is a limit to how far human behaviour can be modelled. In general, social science in terms of network analysis took off at the same time as complexity theory and both have benefited from advances in non-linear mathematics and computational power.
Network Dynamics:
An important feature of the dynamics of networks is that though local change may be gradual, global change may be dramatic and occur in a series of so called 'phase' transitions. When the number of links divided by the number of nodes (i.e. the ratio) approaches 2, a cluster, or the whole network undergoes such a phase change. This can be appreciated by considering two dense clusters with a further node in the middle. Increasing the connectivity just a little results in a huge increase in the size of the cluster. Where there is randomness small changes can bring sudden order to the whole system.
Network dynamics can be simulated at a number of levels in which nodes and links may come and go and wax and wane. Usually node dynamics are slower than link dynamics but not always. Local changes can rapidly lead to global changes and cycles within the system give rise to 'emergent' properties. Cycles are such that if node A is activated there is a pattern of interaction starting with A and ending with A. The number of cycles in a network has a profound effect on the overall behaviour of a system and leads to evolution and counterintuitive properties.
The evolution of networks may be stimulated at the individual or global level. For an ecosystem the selection pressure operates at the level of the individual. At a global level a network evolves to implement a certain function due to selection pressures which if the selection pressures remain the same will achieve some optimum adaptation. It is important to distinguish those systems which experience selection pressure on the whole from those that experiences selection pressure on the individual in order to see how one relates to the other. Neural networks function as a whole, the blood circulation system functions as a whole. These are optimal because they allow for the most efficient flow for the minimum amount of energy. Researchers at the Santa Fe Institute and at Los Alamos have shown that optimal distribution networks have very specific properties that can be observed in a wide range of biological systems.
Global Selection pressure:
There's an ant species in Switzerland which forms what may be regarded as a super colony in that it consists of a number of sub-nests usually with one or several queens. As a food distribution network there is a minimum spanning between the sub-nests which means there is a minimum network of tunnels connecting them. This has evolved because of the global pressure on the colony. The ants can travel between the nests (nodes) securely and the movement of food is sufficient to keep the colony going. Ant behaviour has evolved so that the system functions as a co-ordinated whole.
Similarly there is an army ant colony in South America which is nomadic and when on the move the front of the swarm forms a tree-like structure called a 'bivouac' which is actually optimal as a food distribution network for the energy expended. The swarm pattern of each species is adapted to its diet. A species that indiscriminately preys on anything living has a different pattern from one that only eats other ant colonies. In the first case the colony finds a lot of small food sources though it may use intermediate caches in order to preserve it, and in the second the colony finds a few large sources.
Such models, based on how much food can be brought back to the nest for a certain expenditure of energy were used to find optimum values for efficiency and these were found to be the same for different types of diet. In the model, branches were made to represent frequency of finding food sources and probabilities were found for different feeding habits. What was interesting was that the optimal parameters were the same in each case and that there was selective pressure on the efficiency of the whole system.
Local Selection Pressure:
In the case of food webs in ecosystems there is selective pressure on the nodes (species). The dynamics of such networks can be sub divided into the population dynamics at each node and evolution dynamics. Population dynamics is fast, evolution dynamics is slow. In the model the system was a random network but each node had a certain variability dependent on the nodes to which it was connected. This might be 'catalytic' in that each interaction promotes the growth of the node or 'immune response' type which means that the input to the node has to be of a particular kind in order for the node to proliferate otherwise it decreases. Evolution dynamics in the models consisted of the removal of nodes (species) that were not 'fit' when the population dynamics had reached some sort of stationary state. 'Not fit' was taken as the smallest population which was removed and replaced with a fresh, randomly connected node before the system was evolved further.
Stationary States and Keystone Species:
The question for which a model provides possible answers is a very general one but it is amazing how simple models can produce very interesting results. After transient stages have died out the network may have a highly specific structure. For example, modelling an initial random network with catalytic nodes and the two kinds of dynamics described, one might imagine that we would end up with a completely homogeneous random network. Yet what is obtained is a very specific structure that can be observed in nature and contains what are called 'keystone' species. Keystone species are those which have a lot of 'out going' connections to other species which means that if they are removed from the system the network is severely disrupted. For example in a network of 100 nodes which has evolved to a stationary state we might see that most of the nodes have incoming links with a very few key species having a large number of outgoing links. Removal of a key species results in collapse of the system which then recovers and builds up to another state where species removal produces further 'avalanches' of extinction. In the model the links are directional; it could be understood as 'who helps whom' in which case an 'incoming' link to node A would mean that another node is helping A and an 'outgoing' node means that A is helping some other node. The model does not tell us anything about whether it is better to be a helper or to be helped but if there are cluster sites then the largest will undergo a phase transition when the link to node ratio goes above 2. Thus cluster size can have an influence on the dynamics of each node and the larger the cluster in which a node is embedded the better it might be for that node. Other considerations would be how often a node is deleted and replaced with another node. There might, for example, be a core of nodes which remain permanent and a periphery at which nodes are constantly appearing and disappearing. Alternatively the evolutionary dynamics might result in none of the original nodes remaining long giving a short average life cycle. It is the complexity of the feedback that leads to very specific types of structure with keystone species.
Uses:
The relevance of such models to the real world is that they suggest the possible dynamics involved though they start with the abstract question 'what is the stationary structure of a network that undergoes the two kinds of dynamics described'. It so happens that when you use a population dynamics that is very similar to that observed in food webs then you get structures which fit what we know about food webs though the structure obtained is neither explicitly or implicitly put into the model. Though the model shows the right emergent properties no one would try to sell it as a model of an ecosystem.
Of course the model described is a simple example. It assumes a fixed number of nodes and the weakest node as the smallest population. In simulations of the immune system for example a variable number of nodes was assumed but it becomes much more difficult to find stationary structure and it means displaying perhaps thousands of graphs and trying thousands of measurements to see if the graphs are non trivial. If patterns such as cycles or clusters are found then the sensitivity can be explored by making small changes in the distributions of link numbers for each node but great deal of work may be involved.
Economic networks can be modelled in a similar way to show the evolution of industry. New companies come into a local industry ecosystem and have connections to other companies that are already in the system and some of the companies disappear. The reasons why they disappear may be strongly connected with the underlying human behaviour which is difficult to model so understanding why a business succeeds or not remains guesswork. Models usually assume an average behaviour ( average over the individuals in a population)which is randomly applied. A network that contains cycles or loops shows complex behaviour. Such systems are not predictable though making small changes and observing the results is a useful guide to adjusting a real system. Consultants engaged to advise on real human networks cannot assume random distributions of average human behaviour since as soon as they give advice the behaviour is neither average nor random. If there is a fundamental distinction between human systems and other complex systems it is that there are certain levels at which average behaviour is important and others at which non average or behaviour of the individual becomes important. It may be that the main difference between the human species and any other lies in the extent to which we can learn to adapt to such complex systems. We may have a duty to do so not as individuals but as a system ourselves.
Some Problems:
Average behaviour in populations can be technically problematic. Distributions which have the same average may represent very different behaviours. People who buy some of cookie A perhaps also buy some of cookie B, but this would have the same average as half of the people only buying A and the other half only buying B. The average is the same but the behaviour is very different.
It can be controversial as to what constitutes a phase change. In general it is the change from a system where it is not possible to go from any node to any other node to one where it is possible to go from almost any node to almost any other node. Connectivity is a stepwise function and a phase transition is the emergence of a macroscopic cluster that spans a huge portion of the network. If for example there are individuals with personal computers and connections between them are being added then the aggregate may continue for a while as the sum of individual components until suddenly it will become non linear in function because the behaviour of each element will depend on the behaviour of all the others.
Practical considerations:
Networks may have ideal functions but reality is usually a compromise. The British Telecom network in the U.K. is a connected network but it is not possible to go from any node to any other node with only one connection. Variations in the number of nodes have necessitated 'routing' involving switching stations. What this means is that an algorithm is required to facilitate the communication of a message from node A to node B in an acceptable time without loss of information. Improving the system either means optimising the network or optimising the routing algorithm. and in general there is a trade off between minimal pathways and cost. The telephone network has a wiring cost, a road network has a building and maintenance cost, even social networks have a cost in terms of time and effort in maintaining connections. In modelling terms the balance is between average length between nodes and the maintenance cost per unit length. The aim though is to create a 'small world' where the degrees of separation between each node are small. When simulations are run on the use of networks the thickening of connecting lines indicates the degree of maintenance costs and also gives some idea of the disruption to the system that would be caused by their removal.
Another example of using a network simulation to reveal hidden structure was the analysis of interactions of individual people in a work situation. Of course it depended on identifying the interactions as work related and the time scale and so on. It was possible that there would be too few connections at a daily level but too many at a yearly level, but as the frequency of interactions was decreased so the connectivity increased to reveal sources of information. Of course in social systems the quality of interaction is difficult to define, but it is possible to carry out surveys to determine whether interactions are bi-directional and to analyse information flow in terms of particular problem solving. Quality of interaction also depends on who is making the judgment. For example in one study at IBM there was an individual that the management rated as low quality but was in fact an expert that a lot of people turned to. In terms of the number of interactions this person was of high quality.
In general, in producing a work network one asks the question: 'What are the patterns which are expected but in fact are absent?' Something may be the very opposite of what was expected; for example, you thought someone was a small cog and they turn out to be a big wheel or you thought someone was well connected in the organisation and they turn out to be completely out of it. Analysis can reveal emerging groups and communities of practice and a correlation between formal and informal organisations. It may be possible to shape the emerging structure by finding emergent leaders or under utilised people, finding resource and information bottle-necks, gaps in communication or flow and the extent to which organisational groups are isolated or open to each other and the environment.
It is possible to sort nodes in terms of their connectivity so that for example individuals appearing at the periphery of a graph are those that tend to be isolated. This requires a force directed algorithm, i.e. nodes drag other nodes to themselves according to their connections. As the network gets denser and denser the relative positions of individuals may change.Clustering which may come and go as the frequency of interactions is increased or decreased. If a food web is sorted in terms of predators and prey then those at the top of the food chain could be placed at the periphery, perhaps in a corner and the most preyed upon species at the centre. Each numbered node in this case might represent an aggregate of other nodes. We could, for example, lump 29 parasites together, 13 of which feed on the larva of one weevil and 10 on another. The model is very flexible.
What is also useful in an organisation network is the ability to show how some particular reorganisations could have harmful effects. The IBM consultancy group recently evaluated fifteen of their clients on the effectiveness of their business transformation programmes and assigned a measure of change index to each of them according to the degree of difficulty, speed of change etc. Perhaps a truly adaptable organisation wouldn't dream of implementing a business change programme but there is a whole army of consultants out there that tends to impose some kind of uniformity on the way that companies operate. Companies do not as a rule have a program of spontaneous reorganisation and non-adaptable organisations can be persuaded to change, though admittedly it is an open question as to whether there is a direct correlation between efficiency and employing a consultant. The level of change index is a measure of the adaptability of an organisation and it is interesting to associate those with high levels with network properties. Network properties that are tightly correlated to efficiency have been found to be short information paths between nodes and the presence of emergent leaders . It is the presence of emergent leaders that leads to an overall reduction in the average length between nodes. If for example there is a network in which there are two dominant experts then paths are shortened because most go through them.
Inasmuch as companies are networks then increasing efficiency becomes a question of how the network can be shaped. Moreover the merging of companies becomes a question of how networks can be integrated to ensure company integrity and maintain or enhance productivity. How, for example, do you merge retail networks to reduce costs, whilst retaining flexibility and reliability.
Social networks have been studied for about sixty years though their analysis really took off with two books: 'Getting a Job' by (?) which was a study of how people used their social network to find work and which showed the importance of weak links and 'The Search for an Abortionist' by (?). This second example was a study of how women used their social network to find an abortionist when the operation was illegal.
Today there is an international society on social network analysis ( INSNA?) and two journals called 'Social Networks' and 'Connections'. There's also a book by R.S.Burt called 'Structural Holes'.
AT&T created a model of a social network in order to enhance a recommendation system. The field that they chose was computational complexity and the network they constructed from public documents was 'who co-authors with whom?'. Scientists don't always interact directly but when they write a paper there is a strong possibility that they know each other and are friendly in a scientific sort of way and this is reflected in who cites whom. If we analysed such a citations network we would find clusters; people actually making sure that each other gets published.How the network can be used is that a person enters his or her name and field of expertise and receives and receives patterns of collaborations between experts. Starting from a 'You are here' position you can go to anybody you think might be useful. Of course the network has to be exposed first and surprising facts can emerge.
Evolutionary computation techniques are very useful both for understanding both natural networks such as those for the army ant and for the design of optimised networks of the kind described above but it is important to have a good understanding of underlying behaviour or function of the whole. Simulation is also very useful for exploring the evolution of non controllable networks such as alliances though again it is crucial to have a good model otherwise extremely disastrous conclusions can be drawn. And of course it as well to remember that detailed descriptions are very computation intensive.
What is important in shaping networks is to gain some idea when a phase transition in efficiency will occur. Imagine that a telephone company's cash flow is proportional to the largest cluster in a market network. If a company sells telephones and only one person has a phone (node) then it isn't much use. There is a cost of installing the first node and then the second and so on but at some point there is a phase transition such that beyond this point their are increasing returns for each phone installed. What a good business will try to do is to reach the phase transition as quickly as possible and leave when returns begin to tail off because the market has become saturated or the competition too great. So a strategy might have two uses for network analysis :to see how structure alteration might increase efficiency and to what phase changes occur in order to optimise returns.
Similar thinking applies behind forming an alliance, for example between computer hardware and software sellers or VCRs and video tapes. The more VCRs that are sold the more video tapes so again the marginal cost of producing the goods decreases and the easier it is for the brands to dominate the market. A further advantage to the sellers and buyers is standardisation. Though this may have a high initial cost to producers it becomes easier for the end customer to buy the whole package from one source and again the marginal cost decreases in a stepwise fashion. Competition may be good because it creates a disproportionately bigger market even if it means that some company has a smaller share. Collaborating with competitors is worthwhile if you know how much an alliance network will increase the size of the pie.
Improving networks can make a business more efficient but there can be problems with privacy, security and viruses. Just as the intercontinental travel network spread the 1968 influenza virus very quickly so any 'small' world (in the technical sense) consisting of computers is vulnerable. A small shock can result in a big change. The 'Intel' bug for example cost billions of dollars because the network effect of people telling each other about it was overlooked. Informational networks are particularly subject to overload and access of information must always be balanced against this.
Conclusion:
Understanding how networks work enables us to manage and design systems that lead to more efficient social organisation. We can see this in terms of an optimum between the energy that we have to put into a system to build and maintain it against an ideal function. Increasing the number of nodes and the connectivity between them leads to more integrated wholes but flexibility of the whole may also lead to vulnerability in terms of key structures, the removal of which may result in serious breakdown. The presence of behaviour cycles in the system at a local level also results in unpredictability of the whole, when managing becomes as much a question of how we can adapt ourselves to it as adapting it to ourselves.