The degree to which the nodes of a network are directly connected is called connectivity. A network with high connectivity has a high ratio of edges to the number of nodes. To calculate a networks connectivity , where is the number of edges and is the number of nodes in the network, the following equation is used;

The degree of a node in a network is the number of edges or connections to that node (Newman 2003). The distribution function P(k) gives the probability that a node selected at random has exactly k edges (Albert and Barabási 2002). Plotting P(k) for a network forms a histogram of the degrees of the nodes, this represents the degree distribution (Newman 2003) or the number of nodes that has that number of edges for the network.

The average path length, () of a network is the average number of edges, or connections between nodes, that must be crossed in the shortest path between any 2 nodes (Watts 2003). It is calculated as:

,

where is the minimum distance between nodes i and j.

The diameter of a network is the longest shortest path within a network. The diameter is defined as:

.

A common property of many social networks is cliques. Cliques are groups of friends, where every member of the group knows every other member. The inherent tendency to cluster is quantified by the clustering coefficient (Watts and Strogatz 1998). For a given node i within a network, with k_i neighbours, the degree of clustering around node i is defined to be the fraction of links the exist between the k_i neighbours and the k_i (k_i-1)/2potential links. Let E_i , be the number of links that actually exist between the k_i neighbours. The clustering coefficient is then:

.

One of the first properties of random graphs that Erdös and Rényi studied was the appearance of subgraphs. A graph consisting of the set of nodes and the set of edges is said to be a subgraph of if and . The simplest examples of subgraphs are cycles, trees, and complete subgraphs. One of the most fundamental concepts in graph theory is a walk. Given a graph , a walk is a sequence (ν₀, ν₁), (ν₁, ν₂,), … (ν _k-1, ν_k,) of vertices and edges from vertex to vertex . The number of edges in the walk is its length. A walk in which all vertices are only visited once is known as a path. A walk in which all of the edges are distinct is a trail. A cycle is a closed loop of edges, such that every 2 consecutive edges only have common nodes. A tree is of order if it has nodes and edges, and none of its sub-graphs is a cycle. The average degree of a tree of order is , which approaches the limit 2 for large trees. A complete subgraph of order contains nodes and all the possible edges, in other words, all the nodes in the subgraph are connected to all other nodes (Wilson 1994).

Probably the most important finding from random graph theory was the discovery of a critical threshold at which giant clusters form (in this context, cluster refers to a group of connected nodes) (Erdös and Rényi 1961). Below this threshold, the network exists as a series of disconnected subgraphs. Above this threshold, the graph is one all-encompassing cluster. Figure 5.2 shows this critical phase change using a simple graph model. Initially, all nodes within the graph are disconnected. At each time step, new edges are introduced. Figure 5.2 (a) shows that as edges are added, the nodes very quickly move from being disconnected to being fully connected. While Figure 5.2 (b) shows the standard deviation of the size of the largest connected subregion, the greatest deviation occurs at the critical threshold: at either side of this point the network exists as a series of small-disconnected subregions or as one giant cluster. Finally, Figure 5.2 (c) shows the time required to traverse the graph from one node to another. Again, the maximum time required to traverse the graph exists just below this critical level. This phase change is particularly important in percolation and epidemic processes.

 Figure 5.2. Example of criticality phenomena in the evolution of graphs

Critical phase changes in connectivity of simple random lattice, as the proportion of active cells increases (x-axes). (a) Average size of the largest connected subregion (LCS). (b) Standard deviation in the size of LCS. (c) Traversal time for the LCS. Each point is the result of 1000 iterations of a simulation. Note that the location of the phase change (here ) varies according to the way we defined the connectivity within the model.

Food webs are used regularly by ecologists to quantify the interactions between various species. In such systems, nodes represent species and the edges define predator–prey and other relationships that have positive and negative effects on the interacting species. Weights associated with the edges determines the magnitude of the relationship (May 2001). Solé and Montoya (2001) studied the topological properties of the Ythan Estuary (containing some 134 species with an average of 8.7 interactions per species), the Silwood Park ecosystem (Memmott et al. 2000) (with some 154 species with each species on average having 4.75 interactions) and the Little Rock Lake ecosystem (having a total of 182 species each of which interacts with an average of 26.05 other species). These studies found that these ecosystems were highly clustered and quite resilient against attack.

Studies of human and other animal groups have determined that the structure of many communities conforms to the small worlds model. For example, Liljeros et al. (2001) studied the sexual relationships of 2,810 individuals in Sweden during 1996. The result was a network in which the degrees of the vertices conformed to power–law distribution. Another commonly studied class of systems consists of association networks. Given a centroid, the task is to calculate the distance (number of steps removed) one individual is from another. Perhaps the best known example is the network of collaboration between movie actors (Newman 2000), which takes the popular form of Bacon numbers (Tjaden and Wasson 1997). Other popular examples include Lewinsky numbers and scientific collaboration networks (Newman 2003). The most notable of the scientific collaboration networks are the Erdös numbers (Hoffman 1998) that use the famous mathematician Paul Erdös as the centroid.

Computer networks and other communication networks have in recent times attracted a lot of attention. The World Wide Web (WWW), the largest information network, contained close to 1 billion nodes (pages) by the end of 1999 (Lawrence and Giles 1998). Albert et al. (2000) studied subsets of the WWW and found that they conformed to a scale free network. Other networks, such as the Internet and mobile phone networks, were also found to conform to the scale free network model (Faloutsos et al. 1999).

Studies of the simple neural structure of earthworms (Watts and Strogatz 1998) were able to study the topological properties of underlying networks. In Watts and Strogatz’s model of these brains, nodes represented neurons, and edges were used to depict the synaptic connections. The neural structure of the earthworm was found to conform to the small world network model, in which groups of neurons were highly clustered with random connections to other clusters.

 Figure 5.3. Examples of complex networks

(a) the Internet, where nodes are routers and edges show physical network connections. (b) an ecosystem (c) professional collaboration networks between doctors; and (d) rail network of Barcelona, where nodes are subway stations and edges represent rail connections.

Paul Erdös and Alfred Rényi (1959, 1960, 1961) were the first to introduce the concept of random graphs in 1959. The simple model of a network involves taking some number of vertices, N and connecting nodes by selecting edges from the N(N-1)/2 possible edges at random (Albert and Barabási 2002; Newman 2003). Figure 5.4 shows three random graphs where the probability of an edge being selected is p=0, p=0.1 and p=0.2.

 Figure 5.4. Erdös-Rényi model of random graph evolution

(a) Initially 20 nodes are isolated. (b) Pairs of nodes are connected with a probability of p of selecting an edge. In this case (b) p=0.1 , (c) p=0.2, notice how the nodes become quickly connected

The Erdös and Rényi random graph studies explore how the expected topology of the random graph changes as a function of the number of links (Strogatz 2001). It has been shown that when the number of links is below, the graph is fragmented into small isolated clusters. Above this threshold the network becomes connected as one single cluster or giant component (Figures 5.2 and 5.4). At the threshold the behaviour is indeterminate (Strogatz 2001). Random graphs also show the emergence of subgraphs. Erdös and Rényi (1959, 1960, 1961) explored the emergence of these structures, which form patterns such as trees, cycles and loops. Like the giant component, these subgraphs have distinct thresholds where they form (See Figure 5.5).

 Figure 5.5. Different subgraphs appear at varying threshold probabilities in a random graph (After Albert and Barabási 2002)

In the late 1960s, Stanley Milgram (1967) performed the famous small-worlds experiment. While no physical networks were constructed during this experiment, the results do provide valuable insights into the structure of social networks. Essentially, the experiment examined the distribution of paths lengths in an acquaintance network by asking participants to pass a letter to one of their first-name acquaintances in an attempt to get the letter to the designated target. While most of the letters were lost, about one quarter reached the target person. One average the letter passed through the hands of between 5 and 6 people. This experiment was the source of the popular concept of 6 degrees of separation.

The ground breaking work of Watts and Strogatz (1998) showed that many complex networks display two key features: they possessed the 6 degrees of separation phenomenon, that Milgram discovered; but locally they had many properties similar to that of a regular lattice. In an attempt to model these systems Watts and Strogatz (1998) proposed a one-parameter model, which interpolates between an ordered finite dimensional lattice and a random graph. The algorithm behind the model is as follows: start with a regular ring lattice with nodes in which every node is connected to its first neighbours ( neighbours on either side); and then randomly rewire each edge of the lattice with a probability such that self-connections and duplicate edges are excluded. This process introduces long-range edges which connect nodes that otherwise would be part of different neighbourhoods. Varying the value of moves the system from being fully ordered to random . Figure 5.6 shows steps in this transition. Small world networks have been used to describe a wide variety of real world networks and processes; Newman (2000) and Albert and Barabási (2002) provide excellent review of the work done in this field.

 Figure 5.6. Progressive transition between regular and random graphs

Source: Watts and Strogatz 1998

The second class of graphs is referred to as scale free networks. Specifically, the frequency of nodes with connections follows a power-law distribution , in which most nodes are connected with small proportion of other nodes, and a small proportion of nodes are highly connected (Albert and Barabási 2002). In exponential networks the probability that a node has a high number of connections is very low. In scale free networks, however, highly connected nodes (i.e. are statistically significant (Albert and Barabási 2002).