By Michael Mcphail
Many real world systems can be represented in the form of a complex network by representing objects/people/groups as points, known as nodes or vertices, and showing that a relationship occurs between them using lines known as edges. Examples of the different kinds of systems that can be represented as complex networks are; the internet, the power grid, friendships between people, flights between airports and many more. Measuring certain properties of the network can give you information on the physical system that it represents. However it is often difficult to know how important or special a measurement is, especially if you have nothing to compare the network too. My AMSI vacation project involved generating networks that are similar to some real world networks and comparing the two.
The degree of a node is the number of edges attached to this node. Any network has a property called its “Degree distribution” which is the number of nodes in the network with each degree. In generating new networks for comparison it is this property that we will conserve, i.e. all the networks I compare to an original network have the same degree distribution as the original network. This way we know that the things we are comparing have at least one thing the same.
In order to generate networks with the same degree distribution as an original network, we start with the original network and the change the wiring (the edges) between nodes in such a way that if we separate two nodes, we attach both of them to two different nodes that we also separate. This is essentially just switching the edges between two unconnected pairs of connected nodes. After this action is complete, the degree distribution of the new network is the same however the local structure of the network is different (this is like re-routing flights between airports). After performing enough of these edge switches the over all structure of the network becomes independent of the initial wiring of the real world network however it has the same degree distribution.
By measuring the properties of networks generated in this way, we can compare these measurements to the initial network. What we find is that by generating and measuring enough networks in this way, we start to see a distribution form on the properties we measure. Once we have this distribution, we can see how typical the real network is compared to the generated networks. I found that in real networks, most properties are in fact atypical which suggests that the purpose of real world networks make them specialised in a whole range of properties.
By doing this project I learnt a lot of new and useful skills as well as meeting lots of new people with similar interests to myself. I would definitely recommend this scholarship to anyone and would like to thank AMSI for providing the opportunity to take part in this project. Also a special thank you to my supervisor Professor Michael Small for his time and energy.
Michael Mcphail was one of the recipients of a 2013/14 AMSI Vacation Research Scholarship.