Neuronal networks consist of neurons connected by synapses. A major formal mathematical approach to the description of such networks is graph theory, especially the theory of directed graphs (Harary, 1969; Chartrand and Lesniak, 1996; Bang-Jensen and Gutin, 2001). Graphs have two major ingredients, nodes (cells, brain regions) and connections (synapses, pathways). In graph theory terminology, nodes are often referred to as vertices and connections as edges. Figure 1 provides an illustration of several elementary graph-theoretical concepts used in this chapter. In their simplest form, graphs can be described by a connection matrix or adjacency matrix with binary elements aij that represent the presence or absence of a directed edge between vertices j (source) and i (target). If such an edge exists, vertex j can directly communicate signals (spikes) to vertex i. It is important to note that in brain networks such direct connections are not the only way in which neuronal elements can influence each other. Indirect interactions can proceed along paths or cycles (Fig. 1A), defined as ordered sequences of distinct vertices and edges. More sophisticated and realistic formulations of networks as graphs include the weights or strengths of edges (Barrat et al., 2004a; 2000b). These quantitative approaches to weighted graphs have not yet been widely applied to neurobiological data sets.

The analysis of edges and paths within networks allow the quantification of a broad range of network characteristics, summarized in a series of recent reviews of complex networks (Strogatz, 2001; Albert and Barabasi, 2002; Newman, 2003) and of brain networks (Hilgetag et al., 2002; Sporns, 2002; Sporns et al., 2004; Sporns, 2005). A wide spectrum of graph theory measures derive from the concepts of reachability and distance in graphs. The adjacency matrix of a network allows the derivation of the reachability matrix and the distance matrix, both fundamental for structural graph analyses. The reachability matrix indicates, for each ordered pair of vertices j and i, whether a path (of any length) exists from j to i. If all entries of the reachability matrix are ones, the network consists of only one component and is strongly connected. If the reachability matrix can be partitioned into non-overlapping subsets of vertices with no paths between them then the graph contains multiple (disconnected) components. Distance in a graph refers to the lengths

Fig. 1. Illustration of degrees, paths, cycles, clustering coefficient and hierarchical measures. All panels show an example of a digraph composed of N = 10 vertices and K = 23 directed edges. (A) Vertex 1 has indegree = 1, and outdegree = 4. Originating from vertex 1, bold edges indicate a path from vertex 1 to vertex 6, passing through vertex 2, with a length of 2, denoted as path {1,2,6}. The distance d61 is 2. Other valid paths from 1 to 6 include {1,5,6}, {1,3,2,6} and {1,4,9,8,3,2,5,6}. All paths consist of a set of unique vertices and edges, each visited only once. Another set of bold edges marks a cycle from vertex 1 to 3, 4 and back to 1, with a length of 3, denoted {1,3,4,1}. Other cycles are {1,4,1}and {1,3,2,5,4,1}. (B) Clustering coefficient of vertex 1. This vertex's neighbors are 2,3,4 and 5, and they maintain 6 connections among them out of 12 possible (42-4). This results in a clustering coefficient of 6/12=0.5. (C) Hierarchical clustering coefficient and divergence ratio for vertex 1 and d = 1, d = 2. Vertices 2, 3, 4 and 5 are at distance d =1, and vertices 6, 7, 8, 9 and 10 are at distance d = 2 from vertex 1 (stippled circles). To compute the hierarchical measures, only outgoing connections linking successive hierarchical levels and intra-level connections are considered (bold arrows). Hierarchical clustering coefficients are 6/12 and 4/20 for levels d = 1 and d = 2, respectively. The divergence ratio Di is 5/7, given 7 outgoing connections between ring 1 and 2, and 5 vertices on ring 2. Modified after Sporns and Zwi (2004), and Da F. Costa and Sporns (2005)

of paths between vertices. The entries of the distance matrix give the length of the shortest (directed) path between the two vertices j and i. The global maximum of the distance matrix is also called the graph diameter.

Numerous measures of network connectivity can be derived from the adjacency matrix, the reachability matrix and the distance matrix of a graph. For example, the adjacency matrix allows the examination of the degree distribution of a given network. The degree of a vertex is the number of incident edges, sorted into indegree and outdegree, for incoming and outgoing edges, respectively (Fig. 1A). The degree distribution of a network provides important insights into whether the network contains vertices with approximately equal degrees (i.e. conforming to a Gaussian distribution) or whether the network's vertices show an exponential degree distribution. Such an exponential distribution is found when most of a network's vertices maintain few connections, while some of them are very heavily connected to large portions of the network (so-called hubs). Networks with Gaussian and exponential degree distributions are called "one-scale" and "scale-free", respectively (Amaral et al., 2000), and may support very different dynamical behavior. Scale-free networks are found in many technological as well as biological systems, including metabolic and genetic regulatory networks. However, large-scale cortical networks (Sporns and Zwi, 2004) as well as networks of the brainstem reticular formation (Humphries et al., 2005) show little evidence of a scale-free architecture, perhaps due to the fact that major structural hubs cannot be easily accommodated given volume and metabolic limits. The functional interpretation of degree distributions for individual vertices is fairly straightforward. A high indegree indicates that the vertex is influenced by a large number of other vertices (a dynamical "sink"), while a high outdegree indicates a large number of potential functional targets (a dynamical "source"). The relation between the indegree and the outdegree of a vertex has been defined as the transmission index (Kotter and Stephan, 2003), expressed as the ratio between efferent edges (outdegree) and all known edges (indegree plus outdegree) of the vertex. In conjunction with other such vertex-specific indices, the transmission index allows a comparative analysis of the degree to which individual brain regions participate in network interactions. The examination of large-scale connectivity matrices indicates that each region's pattern of interactions is unique. This important fact was noted by Passingham et al. (2002) who suggested that this specific pattern may be crucial for determining the functional specificity of the region. The uniqueness of cortical regional connections led these authors to coin the term "connectional fingerprint" for the pattern of incident edges (connections) on brain regions.

While indegree and outdegree capture information about the local connectivity neighborhood of a given vertex, there are a number of measures that capture something about the global organization of a network. For example, small-world networks (Watts and Strogatz, 1998; Watts, 1999; 2003) combine features of regular and random graphs and appear to be ubiquitous within the natural, social and technological world (e.g. Strogatz, 2001, Albert and Barabasi, 2002). The two main features of small-world networks are a high degree of local clustering and short average path lengths. Interestingly, these two features map onto two previously discussed candidate principles for cortical network organization, segregation and integration (Sporns et al., 2004). A high degree of local clustering in small-world networks is consistent with a high level of local segregation. The capacity to communicate between all their constituent vertices along short paths, measured as the characteristic path length, is consistent with global integration. The average (or median) of all the entries of the distance matrix constitutes the characteristic path length of a graph, A(G). The clustering coefficient of a vertex y(v) (Fig. 1B) indicates how many connections are maintained between this vertex's neighbors, defined as all those vertices that are connected to it, either through an incoming or an outgoing connection. The average of the clustering coefficients for each individual vertex is the clustering coefficient of the graph y(G).

These methods and measures for characterizing anatomical connection patterns have been applied to large-scale connectivity matrices of the cerebral cortex, which have been assembled from hundreds of neuroanatomical studies conducted in a variety of species, including cat (Scannell et al., 1999) and nonhuman primates (Felleman and Van Essen, 1991; Young, 1993). Results indicate that the cerebral cortex is comprised of clusters of densely and reciprocally coupled cortical areas that are globally interconnected (Sporns et al., 2000a; 2000b). Regarding this clustered architecture, there is strong agreement between different clustering methods (Hilgetag et al., 2000; Sporns et al., 2000a). Importantly, large-scale cortical networks share some attributes of small-world networks, including high values for clustering coefficients and short characteristic path lengths (Hilgetag et al., 2000; Sporns et al., 2000a). A recent detailed analysis revealed that these properties are shared by large-scale connection matrices from several species and cortical systems, and are also found in connection matrices generated by making empirically based probabilistic assumptions about local connection densities and arborizations of cortico-cortical connections (Sporns and Zwi, 2004). Interestingly, self-similar or fractal connection matrices also exhibit small-world connectivity patterns, in addition to a number of other characteristics in line with known features of cortical connectivity, giving rise to the hypothesis that self-similar connectivity may also be found in cortex (Sporns, 2006).

Degree and clustering coefficient evaluate characteristics of connectivity within the immediate topological neighborhood a vertex. A natural extension of such measures involves their application to hierarchical levels around a given vertex (Fig. 1C), defined as the set of vertices that can be reached by minimum paths of increasing lengths d (Da F. Costa, 2004). This generalization allows the calculation of hierarchical measures that capture a much broader context around each vertex, thus more accurately defining how the vertex is embedded in and contributes to the overall network. For example, the divergence ratio D^ of a central vertex is defined as the ratio between the number of hierarchical neighbors at a given distance d +1 and the hierarchical degree (the number of connections linking vertices at distances d and d +1). Similarly, the clustering coefficient can be generalized to apply to a given hierarchical level, with the definition given in the previous paragraph representing the limit case of d = 1. Application of such hierarchical measures to large-scale cortical networks has revealed statistically significant differences between groups of brain regions, such as the dorsal and ventral visual pathway in the macaque (Da F. Costa and Sporns, 2005).

While the existence of paths in brain networks allows for potential interactions across longer distances, a realistic assumption is that much of the processing characteristics and functional contributions of a vertex is determined by its interactions within a local neighborhood (defined in terms of topological, not necessarily metric, distance). To aid in the analysis of such local neighborhoods, large networks or graphs can be decomposed into smaller "building blocks" or "networks-within-networks". Such subgraphs or motifs (Milo et al., 2002; 2004) form a basic structural alphabet - for example, given three vertices, there are only 13 distinct ways to interconnect them (Fig. 2). Motifs

Fig. 2. Definition and detection of structural motifs. (A) Complete set of 13 motifs for 3 vertices. Number refers to the motif class (motif ID). (B) Example digraph with 9 numbered vertices and 18 edges. Graph (top) and adjacency matrix (bottom) are shown. Entries on the main diagonal of the adjacency matrix are shown in gray, edges are shown in black. (C) Motif detection within graph shown in panel B. Instances of motif classes 13, 6, 3 and 9 are highlighted. (D) Complete motif frequency spectrum for the graph shown in panel B

Fig. 2. Definition and detection of structural motifs. (A) Complete set of 13 motifs for 3 vertices. Number refers to the motif class (motif ID). (B) Example digraph with 9 numbered vertices and 18 edges. Graph (top) and adjacency matrix (bottom) are shown. Entries on the main diagonal of the adjacency matrix are shown in gray, edges are shown in black. (C) Motif detection within graph shown in panel B. Instances of motif classes 13, 6, 3 and 9 are highlighted. (D) Complete motif frequency spectrum for the graph shown in panel B

occur in characteristic numbers and distributions that can be highly characteristic of and informative about the large-scale structural and functional characteristics of the global network. Milo et al., reported that some specific motifs are statistically increased in biological networks, as compared to equivalent random networks. Large-scale cortical networks also contain specific motifs in greater than expected abundance, shared across at least two mammalian species (Sporns and Kotter, 2004; Fig. 3). This analysis also revealed that, globally, large-scale brain networks contain relatively few structural motifs

Fig. 3. Structural motifs in macaque visual cortex. (A) Adjacency matrix of macaque visual cortex. (B) Structural motif frequency spectrum for macaque visual cortex (left), as well as equivalent random matrices (middle) and equivalent lattice matrices (right). (C) Motif 9 is the only structural motifs that is significantly increased over both random and lattice networks. (D) Motif fingerprints of areas V4 and PIVv demonstrate that individual brain regions make different contributions to the overall motif frequency spectrum shown in panel B. V4 is one of only a few areas that show very high proportions of motif 9. Modified after Sporns and Zwi (2004), and Sporns and Kotter (2004)

Fig. 3. Structural motifs in macaque visual cortex. (A) Adjacency matrix of macaque visual cortex. (B) Structural motif frequency spectrum for macaque visual cortex (left), as well as equivalent random matrices (middle) and equivalent lattice matrices (right). (C) Motif 9 is the only structural motifs that is significantly increased over both random and lattice networks. (D) Motif fingerprints of areas V4 and PIVv demonstrate that individual brain regions make different contributions to the overall motif frequency spectrum shown in panel B. V4 is one of only a few areas that show very high proportions of motif 9. Modified after Sporns and Zwi (2004), and Sporns and Kotter (2004)

compared to randomized controls, while at the same time maximizing the number of potential functional patterns. More recently, motif analysis has also been applied to single neuron networks between layer 5 cortical pyramidal neurons (Song et al., 2005), confirming the non-randomness of neural connections at this organizational level. A significant further extension of the concept of motifs was introduced by Onnela et al. (2005), who derived measures of motif intensity and coherence which allow motif counts to be applied to weighted networks.

An important issue concerns the connection between motifs and the kind of dynamics they support. Zhigulin (2004) developed an approach to extracting and quantifying dynamical motifs, defined as small subnetworks with nontrivial dynamics. Zhigulin observed that the appearance of specific types of dynamics in large networks was linked to the appearance of periodic and chaotic dynamical motifs. Prill et al. (2005) have drawn relationships between motif patterns and a specific dynamical property, stability or robustness to small perturbations. These authors argue that at least some of the non-randomness of biological networks can be explained by adaptive advantages conferred by robust dynamical stability.

A large literature centers on how complex natural or technological networks are affected by damage to their connection pattern. The world wide web, an example of a scale-free network (Barabasi and Albert, 1999), has been shown to be surprisingly robust with respect to random deletion of nodes, but rather vulnerable to targeted attack on heavily connected hubs (Albert et al., 2000; Doyle et al., 2005), which often results in disintegration of the network. In the brain, the mapping of functional deficits to underlying structural perturbations is experimentally challenging, but essential for a more complete understanding of brain damage and recovery. It is currently unknown which structural measures best capture the potential effects of vertex or edge lesions, although candidate measures of edge vulnerability (Kaiser and Hilgetag Kaiser, 2004) have been defined and have led to the identification of edges whose loss most affects global structural measures. Such edges often correspond to "bridges", i.e. edges linking segregated clusters of brain regions. The issue of defining measures of robustness or vulnerability in brain networks is conceptually linked to the problem of objectively defining the functional contributions of individual network elements (Keinan et al., 2004).

Finally, we should note that measures of structural, functional and effective connectivity increasingly intersect, as in the analysis of functional or effective connectivity patterns as graphs (Dodel et al., 2002; Salvador et al., 2005a; Eichler, 2005). Applications of connectivity analyses to EEG, MEG and fMRI data sets have been reviewed in several other chapters in this volume (Feree and Nunez, 2007; Darvas and Leahy, 2007; Bressler and Mcintosh, 2007). Essentially, patterns of cross-correlation or coherence can be conceptualized as undirected graphs with edges that represent the existence and, in some cases, the strength of the statistical relationship between the linked vertices. Studies of patterns of functional connectivity (based on coherence or correlation) among cortical regions have demonstrated that functional brain networks exhibit small-world (Stam, 2004; Salvador et al., 2005b; Achard et al., 2006; Salvador et al., 2007) and scale-free properties (Eguiluz et al., 2005), possibly reflecting the underlying structural organization of anatomical connections. For example, it is an open question if nodes in structural and functional neuronal connectivity matrices maintain similar patterns of connectivity and exhibit similar local properties such as clustering.

Was this article helpful?

## Post a comment