Free
Editorial Views  |   January 2015
Big Brain, Small World?
Author Notes
  • From the Department of Anesthesiology, Leiden University Medical Center, Leiden, The Netherlands.
  • Corresponding article on page 140.
    Corresponding article on page 140.×
  • Accepted for publication August 29, 2014.
    Accepted for publication August 29, 2014.×
  • Address correspondence to Dr. Dahan: a.dahan@lumc.nl
Article Information
Editorial Views / Central and Peripheral Nervous Systems
Editorial Views   |   January 2015
Big Brain, Small World?
Anesthesiology 01 2015, Vol.122, 8-11. doi:10.1097/ALN.0000000000000517
Anesthesiology 01 2015, Vol.122, 8-11. doi:10.1097/ALN.0000000000000517
Image: ©Thinkstock.
Image: ©Thinkstock.
Image: ©Thinkstock.
×
THE electroencephalogram is the scalp recording of the electrical activity of the brain and reflects the activity of millions of neurons on and just below the surface of the brain.
The electroencephalogram is used extensively as surrogate marker of anesthetic effect. The rhythmic pattern of the electroencephalogram is complex and while some patterns are easily recognized by the eye, such as sleep spindles during stage 2 sleep, sophisticated analyses techniques have been developed to disentangle the complexities of electroencephalographic behavior. In this issue of Anesthesiology, Khodayari-Rostamabad et al.1  present data on the effect of the opioid remifentanil on the electroencephalogram. They first performed a functional connectivity analysis to establish the characteristics of the cortical network and subsequently analyzed the network with a technique based on graph theory. Functional connectivity represents statistical covariation between brain regions (i.e., brain regions with similar rhythmic activity), however, without any implications regarding causality or mechanism. To construct the network, Khodayari-Rostamabad et al.1  calculated the coherence matrix of the electroencephalogram in the standard bands, assuming that the electrodes serve as nodes to the network. Apart from the electroencephalogram, other techniques, such as functional magnetic imaging, may be used to define functional brain connectivity.2 
Graph Theory
Graph theory can be described as the mathematical analysis of networks in which the graph represents a set of network nodes.3  A well-known example of a graph theoretical problem was published by Stanley Milgram in 19674  in his famous paper entitled “The small-world problem.” He studied the number of intermediate sequential acquaintances (nodes) that are required to connect two random individuals in the United States. In one of his studies, the Nebraska study, the number of connections ranged from 2 to 10 with a median of 6, very close to an earlier prediction by Frigyes Karinthy in 1929,5  who predicted that a network of just five acquaintances of 1.5 billion people suffices to connect two inhabitants of our planet. We are all aware of the complex networks in our lives. Another intuitive example of a small-world network is the existing network of airports. To get around the world, we fly to a highly connected “hub” airport that creates a shortcut throughout the network and allows us to travel most efficiently to our destination.
A major step forward to further understanding small-world networks was made by Watts and Strogatz.6  They explored networks that varied in complexity from a regular network to a network with an increased amount of disorder to a randomly connected network (fig. 1).6  The networks are described in terms of nodes (vertices) and connecting paths (edges) with characteristic path length L (fig. 2). Three connected vertices (e.g., positioned in a triangle) make up a cluster with clustering coefficient C (note that clusters may be defined in alternative ways). Clustering coefficient C is defined as the average across vertices of the ratio of existing triangles and possible triangles; the characteristic path length L as the average shortest distance between vertices (one step between vertices equals a path length of 1).6,7  As recently explained, for brain networks, the characteristic path length represents the global efficiency in information transmission in the brain network; the clustering coefficient represents a measure of local functional segregation of brain activities.8,9  The highly regular network of Watts and Strogatz6  has high values for C and L, indicative of a network in which the vertices are highly connected but the flow of information between vertices is slow. The total random network of Watts and Strogatz6  has low values for C and L, which indicates that the vertices are locally segregated but information between vertices travels fast. Intermediate, there is a network with high C and low L, which Watts and Strogatz6  describe as “small-world” (fig. 1). In their article, Khodayari-Rostamabad et al.1  assess the effect of remifentanil by quantitation of the ratio S, where S = C/L, which is the relative small-worldness and in fact, a measure of the balance between global integration (L) and local segregation (C).7 
Fig. 1.
The networks described by Watts and Strogatz.6  The networks vary in complexity from a regular network (C = 0.5, L = 2.89, S = 0.173) to a small-world network with an increased amount of disorder (C = 0.453, L = 2.58, S = 0.175) to a randomly connected network (C = 0.343, L = 2.35, S = 0.146). P is the probability of reconnection of edges (see ref. 6  for further explanation).
The networks described by Watts and Strogatz.6 The networks vary in complexity from a regular network (C = 0.5, L = 2.89, S = 0.173) to a small-world network with an increased amount of disorder (C = 0.453, L = 2.58, S = 0.175) to a randomly connected network (C = 0.343, L = 2.35, S = 0.146). P is the probability of reconnection of edges (see ref. 6 for further explanation).
Fig. 1.
The networks described by Watts and Strogatz.6  The networks vary in complexity from a regular network (C = 0.5, L = 2.89, S = 0.173) to a small-world network with an increased amount of disorder (C = 0.453, L = 2.58, S = 0.175) to a randomly connected network (C = 0.343, L = 2.35, S = 0.146). P is the probability of reconnection of edges (see ref. 6  for further explanation).
×
Fig. 2.
Graph illustrating a network with multiple nodes (vertices, numbered from 1 to 9) and connections (edges) between nodes. There are two clusters present (i.e., triangle networks). One possible path is given in red with path length 4 (1-3-7-6-4).
Graph illustrating a network with multiple nodes (vertices, numbered from 1 to 9) and connections (edges) between nodes. There are two clusters present (i.e., triangle networks). One possible path is given in red with path length 4 (1-3-7-6-4).
Fig. 2.
Graph illustrating a network with multiple nodes (vertices, numbered from 1 to 9) and connections (edges) between nodes. There are two clusters present (i.e., triangle networks). One possible path is given in red with path length 4 (1-3-7-6-4).
×
To explain the calculation of C, L, and S, we give a series of examples in figure 3 in which the vertices or nodes represent people. People who are connected know each other, similar to experiments of Milgram.4  The constructed networks represent the flow of information, in these cases as simple as a person-to-person conversation. See the legend of figure 3 for an explanation of the calculations of C, L, and S. Evidently, for more complex networks, the analysis requires potent computing power. Sometimes alternative measures of small-worldness are calculated, for example, by normalizing C and L by values obtained from a random graph.10  Khodayari-Rostamabad et al.1  use a weighted graph, in which edges are not present or absent, but their existence is a weight between 0 and 1. The weights are given by the correlation between electrodes in the usual frequency bands.
Fig. 3.
Seven example graphs with their graph theoretical properties based on ref. 7 . C is the clustering coefficient (the average across vertices of the ratio of existing triangles and possible triangles), L is the characteristic path length (the average shortest distance between vertices; each step between vertices equals 1), and S is the relative small-worldness where S = C/L. (A) Persons 1 and 2 know each other and are therefore connected by the arrowed line. In this, simple 1 on 1 network C is undefined, L is 1 because the average shortest path length = (1→2 + 2→1)/2 = (1+1)/2 = 1, and relative small-worldness, C/L, is undefined as well. (B) Individual 3 has two friends that do not know each other: C = 0 (since no triangle network is present), L ≈ 1.33 (the average path length = (3→1 + 1→3 + 2→1 + 1→2 + 1→3→2 + 3→2→1)/6 = (1+1+1+1+2+2)/6 ≈ 1.33), and S = 0/1.33 = 0. (C) This is a triangle network. C = 1 since for each of the three vertices (people) there is just one possible triangle connection. Hence, C = (1/1 + 1/1 +1/1)/3 = 1. The average path length equals (1→2 + 2→1 + 1→3 + 3→1 + 2→3 + 3→2)/6 = 6/6 = 1. Relative small-worldness = 1. (D) The square network the relative “small-worldness” equals zero as C = 0 as for none of the people a triangle is present, although for each of the people two triangles connections would be possible (e.g., 1-2-3-1). Hence, C = (0/2 + 0/2 + 0/2 +0/2)/4 = 0. (E) We need to calculate C by counting the number of possible and existing triangles in the network for each vertex (person). For persons 1 and 2, there is one triangle connection of one possible; the network of person 3 has one existing triangle connection (3-2-1-3), but there are two additional possible triangles (3-4-1-3 and 3-4-2-3); in other words, for person 3, there is one triangle of three possible ones; finally for person 4, there are no triangles of a two possible; the average C = (1/1 + 1/1 + 1/3 + 0/2)/4 ≈ 0.58. The average shortest path length, calculated as presented before, equals ≈ 1.33, so that S ≈ 0.44. (F and G) The calculations for these more complex networks follow from the earlier examples. In G, the broken blue arrow is an emerging connection between persons 3 and 4. Values for C, L, and S differ for the state in which 3 and 4 are not connected compared to the state in which they are. Parameter values are given for both the unconnected state (S ≈ 0.34) and the connected state (S ≈ 0.39).
Seven example graphs with their graph theoretical properties based on ref. 7. C is the clustering coefficient (the average across vertices of the ratio of existing triangles and possible triangles), L is the characteristic path length (the average shortest distance between vertices; each step between vertices equals 1), and S is the relative small-worldness where S = C/L. (A) Persons 1 and 2 know each other and are therefore connected by the arrowed line. In this, simple 1 on 1 network C is undefined, L is 1 because the average shortest path length = (1→2 + 2→1)/2 = (1+1)/2 = 1, and relative small-worldness, C/L, is undefined as well. (B) Individual 3 has two friends that do not know each other: C = 0 (since no triangle network is present), L ≈ 1.33 (the average path length = (3→1 + 1→3 + 2→1 + 1→2 + 1→3→2 + 3→2→1)/6 = (1+1+1+1+2+2)/6 ≈ 1.33), and S = 0/1.33 = 0. (C) This is a triangle network. C = 1 since for each of the three vertices (people) there is just one possible triangle connection. Hence, C = (1/1 + 1/1 +1/1)/3 = 1. The average path length equals (1→2 + 2→1 + 1→3 + 3→1 + 2→3 + 3→2)/6 = 6/6 = 1. Relative small-worldness = 1. (D) The square network the relative “small-worldness” equals zero as C = 0 as for none of the people a triangle is present, although for each of the people two triangles connections would be possible (e.g., 1-2-3-1). Hence, C = (0/2 + 0/2 + 0/2 +0/2)/4 = 0. (E) We need to calculate C by counting the number of possible and existing triangles in the network for each vertex (person). For persons 1 and 2, there is one triangle connection of one possible; the network of person 3 has one existing triangle connection (3-2-1-3), but there are two additional possible triangles (3-4-1-3 and 3-4-2-3); in other words, for person 3, there is one triangle of three possible ones; finally for person 4, there are no triangles of a two possible; the average C = (1/1 + 1/1 + 1/3 + 0/2)/4 ≈ 0.58. The average shortest path length, calculated as presented before, equals ≈ 1.33, so that S ≈ 0.44. (F and G) The calculations for these more complex networks follow from the earlier examples. In G, the broken blue arrow is an emerging connection between persons 3 and 4. Values for C, L, and S differ for the state in which 3 and 4 are not connected compared to the state in which they are. Parameter values are given for both the unconnected state (S ≈ 0.34) and the connected state (S ≈ 0.39).
Fig. 3.
Seven example graphs with their graph theoretical properties based on ref. 7 . C is the clustering coefficient (the average across vertices of the ratio of existing triangles and possible triangles), L is the characteristic path length (the average shortest distance between vertices; each step between vertices equals 1), and S is the relative small-worldness where S = C/L. (A) Persons 1 and 2 know each other and are therefore connected by the arrowed line. In this, simple 1 on 1 network C is undefined, L is 1 because the average shortest path length = (1→2 + 2→1)/2 = (1+1)/2 = 1, and relative small-worldness, C/L, is undefined as well. (B) Individual 3 has two friends that do not know each other: C = 0 (since no triangle network is present), L ≈ 1.33 (the average path length = (3→1 + 1→3 + 2→1 + 1→2 + 1→3→2 + 3→2→1)/6 = (1+1+1+1+2+2)/6 ≈ 1.33), and S = 0/1.33 = 0. (C) This is a triangle network. C = 1 since for each of the three vertices (people) there is just one possible triangle connection. Hence, C = (1/1 + 1/1 +1/1)/3 = 1. The average path length equals (1→2 + 2→1 + 1→3 + 3→1 + 2→3 + 3→2)/6 = 6/6 = 1. Relative small-worldness = 1. (D) The square network the relative “small-worldness” equals zero as C = 0 as for none of the people a triangle is present, although for each of the people two triangles connections would be possible (e.g., 1-2-3-1). Hence, C = (0/2 + 0/2 + 0/2 +0/2)/4 = 0. (E) We need to calculate C by counting the number of possible and existing triangles in the network for each vertex (person). For persons 1 and 2, there is one triangle connection of one possible; the network of person 3 has one existing triangle connection (3-2-1-3), but there are two additional possible triangles (3-4-1-3 and 3-4-2-3); in other words, for person 3, there is one triangle of three possible ones; finally for person 4, there are no triangles of a two possible; the average C = (1/1 + 1/1 + 1/3 + 0/2)/4 ≈ 0.58. The average shortest path length, calculated as presented before, equals ≈ 1.33, so that S ≈ 0.44. (F and G) The calculations for these more complex networks follow from the earlier examples. In G, the broken blue arrow is an emerging connection between persons 3 and 4. Values for C, L, and S differ for the state in which 3 and 4 are not connected compared to the state in which they are. Parameter values are given for both the unconnected state (S ≈ 0.34) and the connected state (S ≈ 0.39).
×
The network depicted in figure 3G represents a typical “small-world experience.” Persons 3 and 4 initially did not know each other, but find out that they share a common friend (no. 7 in the network). Interestingly, as they start talking, a connection between them is being established, giving rise to a change in small-worldness. The changes in C, L, and S due to the newly formed connection are given in the figure.
Small-worldness of the Brain
Khodayari-Rostamabad et al.1  show that remifentanil at an approximate effect-site concentration of 2 ng/ml had marked effects on the graph theoretical measures of the electroencephalogram, especially in the β1 and to a lesser extent in the α bands. Remifentanil increased the characteristic path length L and decreased the clustering coefficient C and relative small-worldness. As stated, these effects are suggestive of a “disruption of the complex cortical network subserving normal brain function.” In terms of our simple examples, network 3C reverts to network 3B. As correctly mentioned by the authors, it is important to realize that while the observed opioid-induced changes suggest a change of the balance between integration and segregation of the brain networks that make up the electroencephalogram, they give us no indication of the underlying neurobiological, mechanistic, or functional changes within the brain.
The results of Khodayari-Rostamabad et al.1  contrast earlier reports on the observation that anesthesia-induced unconsciousness is not associated with changes in brain small-worldness.11–13  In animal and human studies, induction, maintenance, and recovery from isoflurane or propofol anesthesia had no effect on spatial organization of brain networks, as defined by resting-state functional magnetic imaging or multichannel electroencephalography. In this light, the findings of Khodayari-Rostamabad et al.1  seem surprising. The authors suggest that their findings are opioid-specific, a remarkable postulation, given the fact that the observed changes in small-worldness were associated with changes in vigilance and attention rather than with antinociception (a surrogate marker of analgesia). Evidently, the findings of Khodayari-Rostamabad et al.1  deserve confirmation in future studies.
Networks are present in a multitude of systems in our daily lives. The graph theoretical description of these networks has various advantages as it improves insight and understanding of these systems that seem unimaginably complex at first sight but do harbor an underlying systematic. Currently, studies focus on possibly one of the most complex networks, the brain functional network. Khodayari-Rostamabad et al.1  tested the effect of the opioid remifentanil on cortical small-worldness and showed a disruptive effect. The presented outcome is difficult to interpret in terms of clinical utility. We look forward to further (confirmatory) studies that increase our insight in the behavior of small-work networks during the administration of centrally acting drugs and determine applicability in clinical practice.
Competing Interests
The authors are not supported by, nor maintain any financial interest in, any commercial activity that may be associated with the topic of this article.
References
Khodayari-Rostamabad, A, Olesen, SS, Graversen, C, Malver, LP, Kurita, GP, Sjøgren, P, Christrup, LL, Drewes, AM Disruption of cortical connectivity during remifentanil administration is associated with cognitive impairment but not with analgesia.. Anesthesiology. (2015). 122 140–9
Niesters, M, Khalili-Mahani, N, Martini, C, Aarts, L, van Gerven, J, van Buchem, MA, Dahan, A, Rombouts, S Effect of subanesthetic ketamine on intrinsic functional brain connectivity: A placebo-controlled functional magnetic resonance imaging study in healthy male volunteers.. Anesthesiology. (2012). 117 868–77 [Article] [PubMed]
Stam, CJ, Reijneveld, JC Graph theoretical analysis of complex networks in the brain.. Nonlinear Biomed Phys. (2007). 1 3 [Article] [PubMed]
Milgram, S The small-world problem.. Psychol Today. (1967). 1 61–7
Karinthy, FLáncszemek [Chains]. Published in Minden masképpen van [Everything Is Different]. (1929). Budapest Atheneum Irodai es Nyomdai R. - T. Kiadasa(translation available at: http://electriceye.org.uk/sites/default/files/Chains.pdf. Accessed October 30, 2014)
Watts, DJ, Strogatz, SH Collective dynamics of ‘small-world’ networks.. Nature. (1998). 393 440–2 [Article] [PubMed]
Rubinov, M, Sporns, O Complex network measures of brain connectivity: Uses and interpretations.. Neuroimage. (2010). 52 1059–69 [Article] [PubMed]
Lee, H, Mashour, GA, Noh, GJ, Kim, S, Lee, U Reconfiguration of network hub structure after propofol-induced unconsciousness.. Anesthesiology. (2013). 119 1347–59 [Article] [PubMed]
Mashour, GA, Avidan, MS Postoperative delirium: Disconnecting the network?. Anesthesiology. (2014). 121 214–6 [Article] [PubMed]
Humphries, MD, Gurney, K Network ‘small-world-ness’: A qualitative method for determining canonical network equivalence. PloS One. (2008). 3 1–10 [Article]
Lee, U, Oh, G, Kim, S, Noh, G, Choi, B, Mashour, GA Brain networks maintain a scale-free organization across consciousness, anesthesia, and recovery: Evidence for adaptive reconfiguration.. Anesthesiology. (2010). 113 1081–91 [Article] [PubMed]
Schröter, MS, Spoormaker, VI, Schorer, A, Wohlschläger, A, Czisch, M, Kochs, EF, Zimmer, C, Hemmer, B, Schneider, G, Jordan, D, Ilg, R Spatiotemporal reconfiguration of large-scale brain functional networks during propofol-induced loss of consciousness.. J Neurosci. (2012). 32 12832–40 [Article] [PubMed]
Liang, Z, King, J, Zhang, N Intrinsic organization of the anesthetized brain.. J Neurosci. (2012). 32 10183–91 [Article] [PubMed]
Image: ©Thinkstock.
Image: ©Thinkstock.
Image: ©Thinkstock.
×
Fig. 1.
The networks described by Watts and Strogatz.6  The networks vary in complexity from a regular network (C = 0.5, L = 2.89, S = 0.173) to a small-world network with an increased amount of disorder (C = 0.453, L = 2.58, S = 0.175) to a randomly connected network (C = 0.343, L = 2.35, S = 0.146). P is the probability of reconnection of edges (see ref. 6  for further explanation).
The networks described by Watts and Strogatz.6 The networks vary in complexity from a regular network (C = 0.5, L = 2.89, S = 0.173) to a small-world network with an increased amount of disorder (C = 0.453, L = 2.58, S = 0.175) to a randomly connected network (C = 0.343, L = 2.35, S = 0.146). P is the probability of reconnection of edges (see ref. 6 for further explanation).
Fig. 1.
The networks described by Watts and Strogatz.6  The networks vary in complexity from a regular network (C = 0.5, L = 2.89, S = 0.173) to a small-world network with an increased amount of disorder (C = 0.453, L = 2.58, S = 0.175) to a randomly connected network (C = 0.343, L = 2.35, S = 0.146). P is the probability of reconnection of edges (see ref. 6  for further explanation).
×
Fig. 2.
Graph illustrating a network with multiple nodes (vertices, numbered from 1 to 9) and connections (edges) between nodes. There are two clusters present (i.e., triangle networks). One possible path is given in red with path length 4 (1-3-7-6-4).
Graph illustrating a network with multiple nodes (vertices, numbered from 1 to 9) and connections (edges) between nodes. There are two clusters present (i.e., triangle networks). One possible path is given in red with path length 4 (1-3-7-6-4).
Fig. 2.
Graph illustrating a network with multiple nodes (vertices, numbered from 1 to 9) and connections (edges) between nodes. There are two clusters present (i.e., triangle networks). One possible path is given in red with path length 4 (1-3-7-6-4).
×
Fig. 3.
Seven example graphs with their graph theoretical properties based on ref. 7 . C is the clustering coefficient (the average across vertices of the ratio of existing triangles and possible triangles), L is the characteristic path length (the average shortest distance between vertices; each step between vertices equals 1), and S is the relative small-worldness where S = C/L. (A) Persons 1 and 2 know each other and are therefore connected by the arrowed line. In this, simple 1 on 1 network C is undefined, L is 1 because the average shortest path length = (1→2 + 2→1)/2 = (1+1)/2 = 1, and relative small-worldness, C/L, is undefined as well. (B) Individual 3 has two friends that do not know each other: C = 0 (since no triangle network is present), L ≈ 1.33 (the average path length = (3→1 + 1→3 + 2→1 + 1→2 + 1→3→2 + 3→2→1)/6 = (1+1+1+1+2+2)/6 ≈ 1.33), and S = 0/1.33 = 0. (C) This is a triangle network. C = 1 since for each of the three vertices (people) there is just one possible triangle connection. Hence, C = (1/1 + 1/1 +1/1)/3 = 1. The average path length equals (1→2 + 2→1 + 1→3 + 3→1 + 2→3 + 3→2)/6 = 6/6 = 1. Relative small-worldness = 1. (D) The square network the relative “small-worldness” equals zero as C = 0 as for none of the people a triangle is present, although for each of the people two triangles connections would be possible (e.g., 1-2-3-1). Hence, C = (0/2 + 0/2 + 0/2 +0/2)/4 = 0. (E) We need to calculate C by counting the number of possible and existing triangles in the network for each vertex (person). For persons 1 and 2, there is one triangle connection of one possible; the network of person 3 has one existing triangle connection (3-2-1-3), but there are two additional possible triangles (3-4-1-3 and 3-4-2-3); in other words, for person 3, there is one triangle of three possible ones; finally for person 4, there are no triangles of a two possible; the average C = (1/1 + 1/1 + 1/3 + 0/2)/4 ≈ 0.58. The average shortest path length, calculated as presented before, equals ≈ 1.33, so that S ≈ 0.44. (F and G) The calculations for these more complex networks follow from the earlier examples. In G, the broken blue arrow is an emerging connection between persons 3 and 4. Values for C, L, and S differ for the state in which 3 and 4 are not connected compared to the state in which they are. Parameter values are given for both the unconnected state (S ≈ 0.34) and the connected state (S ≈ 0.39).
Seven example graphs with their graph theoretical properties based on ref. 7. C is the clustering coefficient (the average across vertices of the ratio of existing triangles and possible triangles), L is the characteristic path length (the average shortest distance between vertices; each step between vertices equals 1), and S is the relative small-worldness where S = C/L. (A) Persons 1 and 2 know each other and are therefore connected by the arrowed line. In this, simple 1 on 1 network C is undefined, L is 1 because the average shortest path length = (1→2 + 2→1)/2 = (1+1)/2 = 1, and relative small-worldness, C/L, is undefined as well. (B) Individual 3 has two friends that do not know each other: C = 0 (since no triangle network is present), L ≈ 1.33 (the average path length = (3→1 + 1→3 + 2→1 + 1→2 + 1→3→2 + 3→2→1)/6 = (1+1+1+1+2+2)/6 ≈ 1.33), and S = 0/1.33 = 0. (C) This is a triangle network. C = 1 since for each of the three vertices (people) there is just one possible triangle connection. Hence, C = (1/1 + 1/1 +1/1)/3 = 1. The average path length equals (1→2 + 2→1 + 1→3 + 3→1 + 2→3 + 3→2)/6 = 6/6 = 1. Relative small-worldness = 1. (D) The square network the relative “small-worldness” equals zero as C = 0 as for none of the people a triangle is present, although for each of the people two triangles connections would be possible (e.g., 1-2-3-1). Hence, C = (0/2 + 0/2 + 0/2 +0/2)/4 = 0. (E) We need to calculate C by counting the number of possible and existing triangles in the network for each vertex (person). For persons 1 and 2, there is one triangle connection of one possible; the network of person 3 has one existing triangle connection (3-2-1-3), but there are two additional possible triangles (3-4-1-3 and 3-4-2-3); in other words, for person 3, there is one triangle of three possible ones; finally for person 4, there are no triangles of a two possible; the average C = (1/1 + 1/1 + 1/3 + 0/2)/4 ≈ 0.58. The average shortest path length, calculated as presented before, equals ≈ 1.33, so that S ≈ 0.44. (F and G) The calculations for these more complex networks follow from the earlier examples. In G, the broken blue arrow is an emerging connection between persons 3 and 4. Values for C, L, and S differ for the state in which 3 and 4 are not connected compared to the state in which they are. Parameter values are given for both the unconnected state (S ≈ 0.34) and the connected state (S ≈ 0.39).
Fig. 3.
Seven example graphs with their graph theoretical properties based on ref. 7 . C is the clustering coefficient (the average across vertices of the ratio of existing triangles and possible triangles), L is the characteristic path length (the average shortest distance between vertices; each step between vertices equals 1), and S is the relative small-worldness where S = C/L. (A) Persons 1 and 2 know each other and are therefore connected by the arrowed line. In this, simple 1 on 1 network C is undefined, L is 1 because the average shortest path length = (1→2 + 2→1)/2 = (1+1)/2 = 1, and relative small-worldness, C/L, is undefined as well. (B) Individual 3 has two friends that do not know each other: C = 0 (since no triangle network is present), L ≈ 1.33 (the average path length = (3→1 + 1→3 + 2→1 + 1→2 + 1→3→2 + 3→2→1)/6 = (1+1+1+1+2+2)/6 ≈ 1.33), and S = 0/1.33 = 0. (C) This is a triangle network. C = 1 since for each of the three vertices (people) there is just one possible triangle connection. Hence, C = (1/1 + 1/1 +1/1)/3 = 1. The average path length equals (1→2 + 2→1 + 1→3 + 3→1 + 2→3 + 3→2)/6 = 6/6 = 1. Relative small-worldness = 1. (D) The square network the relative “small-worldness” equals zero as C = 0 as for none of the people a triangle is present, although for each of the people two triangles connections would be possible (e.g., 1-2-3-1). Hence, C = (0/2 + 0/2 + 0/2 +0/2)/4 = 0. (E) We need to calculate C by counting the number of possible and existing triangles in the network for each vertex (person). For persons 1 and 2, there is one triangle connection of one possible; the network of person 3 has one existing triangle connection (3-2-1-3), but there are two additional possible triangles (3-4-1-3 and 3-4-2-3); in other words, for person 3, there is one triangle of three possible ones; finally for person 4, there are no triangles of a two possible; the average C = (1/1 + 1/1 + 1/3 + 0/2)/4 ≈ 0.58. The average shortest path length, calculated as presented before, equals ≈ 1.33, so that S ≈ 0.44. (F and G) The calculations for these more complex networks follow from the earlier examples. In G, the broken blue arrow is an emerging connection between persons 3 and 4. Values for C, L, and S differ for the state in which 3 and 4 are not connected compared to the state in which they are. Parameter values are given for both the unconnected state (S ≈ 0.34) and the connected state (S ≈ 0.39).
×