Introduction to Networks

Networks (also called graphs by mathematicians) are simply a collection of vertices (also called nodes) and a collection of edges (sometimes called links). The edges just connect pairs of vertices. The alternative terms noted here already indicate how the terminology of networks is not always fixed. This reflects its long cross-disciplinary heritage with input from mathematicians, social scientists, computer scientists, physicists and engineers amongst others. There are rigorous definitions of some concepts but not everyone uses the same definitions.

Plot of number of papers whose title contains words starting with Network

Plot of the ratio of the number of Network papers (whose title contains words starting with Network) compared to Model papers (those papers whose title contains the word model). For comparison, ratio of Complexity papers to Model papers is shown in green.

There has been an explosion of interest in networks over the last fifteen years. The fraction of papers on networks doubled between 1999  and 2009 (see plot). This phenomenal rise has been driven by the opportunities provided by the vast number of new large data sets and the computing power to analyse them.  Their value to society is immense as with the right tools the data provides new windows on human behaviour (e.g. via Facebook or mobile phone usage) and on our complicated infrastructure (e.g. power grids, the internet or transport links).

Networks are a natural, useful and extremely flexible  way of representing many of these large electronic data sets. For instance the nodes can be web pages and the edges are web links. Another example is where the nodes can be Facebook users and the edges represent connections between them. Networks are a key part of the `digital humanities’ revolution. The arrival of these new data sets brought a new wave of interest from physicists around in 1998 (Watts and Strogatz). In particular scale-free networks were those thought to have certain types of power-law distributions within them (e.g. Barabasi and Albert, 1999).

I have a review of Complex Networks in Contemporary Physics 45 (2004) 455-474 (or download from arXiv:cond-mat/0405123). This review is a bit dated now in some places but it is still a good basic introduction to researchers new to the field. I would also highly recommend the first article/editorial in a new journal “What is network science?” (Brandes et al. Network Science, 2013, 1, 1-15) which set out the motivation and nature of network research, also highlighting what it is notThe slides from some general talks I have given are also available. My most recent general talk on networks was “Netplexity – Networks and Complexity for the Real World“. This was a keynote address for the Second annual Student Conference on Complexity Science given on 10th August 2012. I gave a general overview of networks along with a longer more detailed look at the mathematics of networks as part of the International Summer School and research workshop
on Complexity in Istanbul in September 2011. In 2010, I gave an invited talk in Manchester, entitled “The Mathematical Description of Networks“. Finally in May 2005 I gave  a colloquium for the Physics Department of Imperial College  entitled Complex Networks: Six Degrees of Separation and all that. For a wider range of resources for networks some including courses and texts (some of which are free) see links under resources.