Complex networks
Physics is a powerful science. Nevertheless, the deterministic Newtonian science lacks words to describe complex behavior. Physics has been the tool that break things down into laws. This reductionist viewpoint has proved to be very successful, but it is now time to reassemble things into a whole again (Wilson, 1998). There is much to be learned on this journey, and a new science has to be developed.Here I take the approach that complex systems are best understood through simple models. Simple, because it should be possible to understand the model in itself. Moreover, a model that contains everything that is known about the system can, by some fiddling with the parameters, in principle predict anything. And a model that can predict anything predicts nothing (Popper, 1963).
Background
Networks are everywhere, have always been, and will always be—social networks, gene networks, cellular networks, ecological networks, computer networks, phonecall networks, airline networks, powerline networks—why this buzz now? The short answer is the Internet.
A longer answer is that mathematicians have had, since Leonard Euler solved the so called Königsberg bridge problem^{1} in 1736, the knowledge to abstract away details from a problem and reduce it to a graph^{2}—a set of nodes and links. The strength with this mathematical object is of course that the nodes are not limited to represent land masses and the links limited to represent bridges. The list of networks above could have been made much longer, since so many systems can be simplified with maintained complexity by a network.
It matters to abstract a system into its underlying network when the interacting units are unique, like humans, proteins, and web pages, but not when they are interchangeable, like atoms, electrons, and spins^{3}. It is therefore not surprising that sociologists, and not physicists, were the first to apply the abstract mathematical objects of graphs to concrete problems. This happend around the 1950s and one challenging question was “How small is the world?” (Kochen, 1989; Milgram, 1967; de Sola Pool and Kochen, 1978). At about the same time the two Hungarian mathematicians Paul Erds and Alfréd Rényi started to develop a statistical theory of dynamic networks (Erdös and Rényi, 1959), originally proposed by Solomonoff and Rapoport (1951).
Why did the field of network research wait another 50 years to take off? The main problem the sociologists faced was the difficulty to create large reliable networks. Especially de Sola Pool and Kochen (1978) asked many fundamental questions, still important today, but they could not answer them in an adequate manner because of the poor experimental data. For example, to estimate how long the shortest chain of friends is between two people chosen at random, they first had to estimate how many friends an individual has. The two problems they faced were: what is a friend and why are people so poor at estimating their number of friends? Try to estimate your number of friends and you will realize that it is not straightforward.
Kochen and de Sola Pool instead turned to the mathematical models by Solomonoff and Rapoport (1951) and Erdös and Rényi (1959), and estimated the average separation to three. Milgram (1967) estimated, by tracing letters sent by chains of aquaintaces, the average distance to six. Obviously there was a problem here. The experiments predicted twice as large average separation as the models. Were the models wrong, or the experiments unsound?
One exception from small and unreliable data from experiments was presented in the pioneering work by Price (1965) on the network of citations between scientific articles. He found that the distribution of citations, corresponding to links in network language, was not peaked at an average value as in the mathematical models of random networks (Erdös and Rényi, 1959). Instead most of the articles had only a few citations and a few articles had many citations: the distribution of citations per article followed a power law. A decade later he presented the model called cumulative advantage based on an idea by Simon (1955) that could explain this observation (Price, 1976).^{4} However, the work by Price considered one particular network, and the concepts did not cross over to other sciences but remained an isolated work.
In the late 1990s, at the same time as the Internet started to become mature and useable^{5}, all necessary ingredients were suddenly at hand (Barabási and Albert, 2002): the emergence of large databases on the topology of various real networks, increased computing power, the noticeable breakdown of boundaries between disciplines, and the new holistic viewpoint to try to understand the system as a whole. Again it became apparent that it is impossible to overestimate the importance of cross fertilization between theory and experiments in science.
The breakthrough originated in the physics community because the tools of statistical mechanics are particularly well suited to analyze the patterns of interactions in networks. For example, in the context of statistical mechanics, physicists have investigated how a system behaves on the macroscopic level from the properties of its constituents, the agents, on the microscopic level. The new idea was that behind every complex system there is an underlying network with a nonrandom topology (Barabási, 2001). It became clear that this pattern of interactions, which forms the network, plays a fundamental role in understanding the system (Newman, 2002b).
Realworld networks
The first network that was large enough for reliable statistical measurements, and at the same time accessible, turned out to be the World Wide Web (WWW).^{6} With the purpose to test a realworld network against the random network model (Erdös and Rényi, 1959), Barabási et al. (2000) analyzed a subdomain of the WWW consisting of more than 300,000 web pages. As in the study by Price (1965), the distribution of the number of links per node did not follow the predicted distribution from the random network model. Again it was powerlaw distributed. However, this study did not remain isolated, because a number of experiments followed shortly. Broder et al. (2000) repeated the experiment on a much larger section of the WWW and confirmed the results. Faloutsos et al. (1999) and Vázquez et al. (2002) showed that the distribution of physical connections in the Internet followed roughly the same distribution.
Were the discovered powerlaw tails of the distributions of links “much ado about nothing?” Yes and no. Yes, because the discovery has led to an unreasonable hunt for power laws in empirical studies and the construction of ad hoc models that produce power laws. No, because the few nodes with a very high number of links, the hubs of the network, have a dramatic effect on the properties of the network.^{7} Moreover, the broad distribution was discovered in other networks than technological as well. Watts and Strogatz (1998) studied movie actor collaborations, Fell and Wagner (2000) the metabolic network of the bacterium E. coli, Jeong et al. (2000) the metabolic networks of more than 40 organisms, Amaral et al. (2000) airline networks, Liljeros et al. (2001) sexual contacts, and we have for example studied city street networks (Rosvall et al., 2005). The list can be made much longer, but the general result was that the networks did neither look like the random network model predicted, nor were they regular, and what they really look like is what the remaining of this text is about.
Network topology
I will begin this section with two examples of realworld networks. This will not only visualize the pattern of links connecting nodes, the network topology or the network structure, in two different systems. It will also illustrate the difference between a cumbersome and detailed, and an efficient but inexact way to extract the underlying network in a system.
Two network examples
The first network in Figure 1 is by Krebs (2002) and describes the September 11 terrorist network. With the aim to “uncover network patterns that would reveal Al Qaeda’s preferred methods of stealth organization,” Krebs gathered information from major newspapers such as the New York Times and the Wall Street Journal. Obviously this method is time consuming and inevitably incomplete.
The second network in Figure 2 consists of a subset of the 100 most influential people in 2006 selected by Time Magazine. In this case I have let Google create the network by asking how many hits two names get together compared with what one of the names gets. If the ratio is above a threshold, 5% in this case, I create a directed link between the two names pointing to the name I compare with. This is a very fast method, but gives of course only a proxy of the real network.


I have already stated that realworld networks are different from the random network model by Erdös and Rényi (1959). This difference refers to the ways the links are organized between the nodes—the network topology. It is for example easy to see that the links in the two networks in Figure 1 and Figure 2 are not randomly distributed, but how much, and in what way are they not? Before answering these questions, we need a benchmark to enable comparison between networks through proper null models. However, I have already used too many concepts that deserve to be defined rigorously before I use them, so it is time to take a step back.
Nodes and links
Technically speaking, a mathematician uses the term graph to represent a structure with a set of objects called vertices connected by links called edges. If the edges have directions (object A links to B, but B does not automatically link to A), the graph is directed. If the edges are also associated with a weight, that for example could represent the distance between two objects, the mathematician uses the term network. However, that network and not graph will be used from now on does not imply that this text is about directed weighted graphs. Instead, undirected and unweighted graphs are almost exclusively the focus of this text. This contradiction originates from the loose language outside mathematics and the tradition to use the term network as something that represents a realworld evolving system upon which distributed dynamic processes might exist (Newman et al., 2006). I will also use the terms nodes and links instead of vertices and edges.
The simplest concepts beyond the nodes and links, still belonging to the local properties of a network, are the degree and the clustering. They will be explained in the following sections together with the shortest path. Degree, clustering, and shortest path were three major concepts in focus in the early studies of complex networks, not least because of their relevance to the fundamental questions raised by de Sola Pool and Kochen (1978).
Degree distribution
The degree k_{v} is the number of links incident to node v and is consequently equal to the number of nearest neighbors of v. In physical literature the degree of a node is also known as the node’s connectivity. There is a spread in the node degree, described by the degree distribution, which is characterized by the distribution function P(k). P(k) gives the probability that a randomly chosen node in the network has exactly k links or equivalently k nearest neighbors. The degree distribution plays a central role in . Powerlaw degree distributions have already been mentioned, and refer to distributions that are proportional to P(k) ∝ k^{γ}. A real network does not of course exactly follow a given parametrization of a distribution, but if it is roughly P(k) ∝ k^{γ} it will be called a broad degree distribution in this text. The important feature in a network with a broad degree distribution is that most nodes have very few links, but a few nodes have very many links. The nodes with very many links are called hubs.
Degree correlations

Maslov and Sneppen (2002) developed a method to test for correlations in the degree of the nodes. The probability P(k_{0},k_{1}) that two nodes of degree k_{0} and k_{1} are connected via a link is calculated and compared with the probability P_{r}(k_{0},k_{1}) in a randomized version of the same network with preserved degree sequence. The idea is a reinvention of the conditional uniform test by Katz and Powell (1957), presented in a network context by Snijders (1991).
In the randomized counterpart of the original network, the null network, all nodes have the same degree as in the original network, but the connections are randomized. The random counterpart is created by first randomly selecting a pair of links, like e_{uv} and e_{xy} in Figure 3. The two links are then rewired in such a way that u becomes connected to y and v to x, or vice versa provided that none of these links already existed. The step is iterated until all information of the original network is lost.
If the above algorithm is repeated, a set of randomized counterparts makes
average expectation values and standarddeviation measurements possible for any
property of the network. The randomized networks will hereafter be called
MSrandomized networks (from Maslov and Sneppen) to avoid confusion with the
random networks, already mentioned but more thoroughly presented in . The
ratio of a property between the original and MSrandomized versions
uncovers deviations from random properties. The nullnetwork approach is
extremely powerful to separate nonrandom features from features that are only
associated to a particular degree distribution and will be used over and over
here.

In Axelsen et al. (2006) we generalized the degreeorganizational view (PastorSatorras et al., 2001) of realworld networks with broad degree distributions (Barabási and Albert, 1999) in a landscape analogy with mountains (highdegree nodes) and valleys (lowdegree nodes) (see Figure 4). For example, with the presented viewpoint, correlated degrees between adjacent nodes correspond to smooth landscapes (social networks) (Newman, 2002a), hierarchical networks to onemountain landscapes (the Internet) (Trusina et al., 2004), and networks with anticorrelated degrees without hierarchical features to rough landscapes with several mountains (Newman, 2003) (see Figure 5).

To quantify the topology, we measured the widths of the mountains and the
separation between different mountains. We also generated ridged landscapes to
model networks organized under constraints imposed by the space the networks
are embedded in, associated to spatial or, in molecular networks, to functional
localization.
Shortest path
The length of all links is here defined to be 1. The distance l_{uv} = l_{vu} between two nodes u and v in the network is consequently defined to be the number of links traced on the shortest path between the nodes. A connected component is a set of nodes that all can be reached from each other, disconnected from other components of the network. If the network only contains one connected component, the network is connected. When this is true, it is straightforward to define the average path length l, as the average over all shortest paths
 (1) 
The node that on average has shortest path length to all other nodes in the network can naturally be defined to be the center node.
If the network is disconnected the average reciprocal distance l^{1}, also called the efficiency, can be used instead of the average path length (Latora and Marchiori, 2001)
 (2) 
A measurement related to the shortest path is the betweenness. The betweenness of a node is the number of times the node is on the shortest path between all other pairs of nodes. The quantity was introduced to investigate the participation rates of nodes in networks with the shortest paths as proxies for communication channels (Freeman, 1977). An alternative center node in this context is the one with the highest betweenness.
Clustering
The clustering coefficient C is the probability that the two nearest neighbors of a node also are nearest neighbors to one another. In the network, such a relation forms a triangle of links. Accordingly, a high clustering coefficient reflects an increased number of triangles in the network, and gives a hint about a dense topology on the local network level. A common definition of the clustering coefficient is given by Barrat and Weigt (2000):
where N_{△} is the number of triangles in the network and N_{⊔} is the number of connected triples of nodes in the network. Triangles are trios of nodes with every node connected to both of the others. Connected triples are trios of nodes with at least one connected to both of the others. The factor 3 compensates for the fact that each triangle corresponds to three connected triples. The factor constrains C to lie in the range between 0 and 1. In a social network, where nodes are persons and links symbolize friendship, C corresponds to the probability that two of one’s friends also are friends with one another. Whereas the shortest path is a global property of the network, clustering is a local property.The drawback of the definition of the clustering above is that it is dependent on the global properties of the network. To overcome that problem we use the nullnetwork approach. We think that the best way to calculate the clustering in a network is to count the number of triangles in the network and compare with the number of triangles in its random counterparts. This is a good way to avoid the direct effect of the degree distribution on the clustering, and we use this method in all presented papers.
Beyond simple measures
There are plenty of other measures invented to reveal the structure of realworld networks, too many to all be mentioned here. However, by just looking at the networks in Figure 1 and Figure 2 it is clear that they both have a higher order structure than the broad distributions of links and the many triangles. It looks like the terrorist network could easily be divided into three groups, and the network of influential people could be divided into two groups. By looking more closely at the names it is clear that political leaders form one group and people from showbiz form the other group, and that Oprah Winfrey falls somewhere in between.
Community structure
No one has contributed more than Newman (2004a) on how to detect groups in networks, or community structures, which they are often called. For example, Girvan and Newman (2002) presented a method based on the betweenness. They showed that it is possible to partition the network by successively removing the link with the highest betweenness until the network falls apart into two disconnected components. This brute force method can then be repeated on the components formed.
Later Newman and Girvan (2004) introduced a measure of the community structure under the name modularity. It resembles the process we perform when we look at the networks in Figure 1 and Figure 2 to identify the groups. A meaningful division of the networks is not only one in which there are few links between the groups—it is one where there are fewer than expected. They formulated this mathematically and have shown that it gives rise to meaningful partitions of networks (Newman, 2004b). Newman (2006) presented a method for the maximization of the modularity over possible divisions of a network based on a matrix method that is very efficient.
The other way to look at the problem is to study the formation process, and what dynamic features the community structure brings? This is indirectly the topic of the two final chapters of my thesis. The formation process has also been studied by for example Grönlund and Holme (2004), and the effect of the community structure on the spread of fads by Grönlund and Holme (2005). For example, Boguná and PastorSatorras (2002) showed that the epidemic threshold can be nonzero even in networks with powerlaw degree distribution if the network is modular or has high clustering.
Before going into more detail here, and to be able to connect the network topology with its intrinsic function and the underlying evolutionary process, the next chapter will be about network models.
^{1}Seven bridges connected the four different land masses in Königsberg, and the question was, “Does there exist any single path that crosses all seven bridges exactly once each?”
^{2}The difference between the mathematicians graph and the networks discussed here is subtle, but where a graph is mainly a mathematical object, a network often refers to a decentralized, naturally evolving system (Newman et al., 2006).
^{3}Spin is the intrinsic angular momentum in elementary particles.
^{4}This model is very similar to the preferential attachment model discussed in the next chapter.
^{5}Notable: Ines Usman, the former Swedish secretary of transport and communications, said in 1996 that “The Internet is a fad that may just pass by.”
^{6}The network of the WWW consists of web pages linked by the hyperlinks we click on to go from page to page.
^{7}PastorSatorras and Vespignani (2001) showed that networks with powerlaw distribution of links per node may not have an epidemic threshold and a disease will therefore always spread.
Martin Rosvall Associate professor +46 70 239 1973 Department of Physics Umeå University SE901 87 Umeå Sweden
mapequation.org IceLab CMOL Eigenfactor.org Carl Bergstrom Infobaleen