**Module 7**

Graph Theory & Network Analysis

Graph Theory & Network Analysis

**Implications for EEG studies of general anesthesia**

Why networks ?

1. Over the last decade, the study of complex networks has dramatically expanded across diverse fields, from the social sciences to physics and biology.

2. To understand complex systems like weather, society, and biology, we require not only knowledge of elementary components but also knowledge about their global interactions in the system.

3. The network approach can provide fundamental insights into the means by which simple elements organize into dynamic patterns and then adaptively reorganize.

1. Large networks of neurons produce higher cognitive functions like attention, memory and consciousness.

2. It is becoming clear that understanding the dynamic integration of neural networks is essential to understanding consciousness.

3. Brain networks span multiple spatial scales, from the micro-scale of individual cells and synapses to the macro-scale of cognitive systems.

4. Knowledge about network interactions on and across multiple levels of organization is crucial for a more complete understanding of the brain as an integrated system.

In the brain

[Sporns 2011, Networks of the brain]

Why is network analysis important for general anesthesia ?

1. General anesthesia induces various alterations of consciousness.

2. The transition between the conscious and unconscious state is associated with a significant change of brain networks.

3. Mathematical graph theory is the most appropriate tool to analyze the structure and dynamics of brain networks.

4. By applying the graph theoretical network analysis to EEG or fMRI data, we may be able to elucidate anesthetic mechanisms quantitatively in terms of hierarchical structure of multi-scale brain functions.

Origin of graph theory: the 7 bridges of Königsberg

Euler’s problem (1736) was a popular puzzle involving seven bridges across the river Pregel in the East Prussian city of Konigsberg (today’s Kalinigrad). These bridges linked four separate parts of the city. The problem was to find a path by which a person could cross each of these bridges exactly once and return to the starting point. People knew this was impossible, but there was no proof. Euler found a general solution and realized that the problem could be resolved by solely taking into account the relative position of bridges and landmasses, and that precise geographical position or physical distance was unimportant.

Topology of a graph

The topology of connections is the essence of the approach. Each landmass corresponds to a node and the bridge corresponds to the edge in the graph. By studying the topology of the graph we can find a general solution. Euler founded the field he referred to as the ‘geometry of position’ and which is now known as “graph theory”.

Implications

Graph theory is a useful mathematical tool to study the complex and hierarchical functional structure of neural networks, cognitive modalities and other brain features and functions.

In general, a node is a portion of the system that is separable from the other portions of the system in some way; i.e., nodes are meant to be inherently independent or distinct in the system under study.

(Butts 2008, 2009; Rubinov & Sporns 2010)

A cellular nervous system has obvious graphical deconstruction: each cell can be considered an independent and homogeneous node, and the synapses between neurons can be consider as edges.

Define each electrode or signal sensor as a node.

For tract-tracing data, nodes are usually defined cytoarchitectonically as Broddman areas (Hilgetag et al 2000).

For MRI data, each node should comprise an equal number of voxels and these nodes should collectively cover the brain without prior anatomical information (Zalesky et al 2010).

What is a node?

Cellular systems

Electrophysiological data

Tract-tracing and MRI data

What is an edge ?

Without knowledge of the physical connections between nodes, a reasonable specification of edges is challenging.

Two possible ways to define edges :

(1) functional association (2) structural association.

Functional connectivity: measures the extent to which two processes behave similarly over time (correlation coefficient, phase synchrony, synchronization likelihood, etc.).

Effective connectivity: measures the extent to which one process can be predicted or explained by the other (entropy transfer, evolutional map approach, granger causality, dynamic causal modeling, etc.).

Structural association is derived from measures of anatomical connectivity between nodal regions.

Anatomic connectivity can be defined in different ways, based on different kinds of data.

For diffusion tensor or spectrum imaging, it is possible to assign a probability of axonal connection between any pair of gray matter regions on the basis of tractographic analysis.

(2) Structural association

(1) Functional association

How to construct a brain network

The brain network can be constructed with cellular data, electrophysiological data, tract-tracing and fMRI data. The key process in constructing a brain network is to determine nodes and edges, which significantly influence on the network properties.

1. Record neurophysiological data

2. Determining nodes and edges

3. Construct association matrix

4. Establish thresholds for adjacency matrix

5. Analyze network properties

Small world network

Basic Network Properties

With EEG, the assumption of a stationary system does not always hold. Thus, there is a need to study the dynamics of a brain network, instead of static brain network properties.

EEG has good temporal resolution but has suboptimal spatial resolution. It does not reflect complete a brain network.

EEG preprocessing steps for artifact treatment may substantially alter the topology of brain graphs derived from the association matrices.

Volume conduction produces strong correlation between neighboring sensors. Untreated volume conduction will be represented by a regular lattice-like structure of highly clustered connections between spatially neighboring sensors, and confound the brain network properties such as small-worldness.

Significant change of spectrum in the anesthetized state could produce large spurious correlations or phase synchronizations.

Potential problems in EEG-based graph analysis

**Further reading**

Achard S, Bullmore E (2007). Efficiency and cost of economical brain functional networks. PLoS Comput Biol 3, e17.

Barabási, A.-L., and Albert, R (1999). Emergence of scaling in random networks. Science 286, 509–512.

Bullmore, E., and Sporns, O (2009). Complex brain networks: graph theoretical analysis of structural and functional systems. Nat Rev Neurosci 10, 186–198.

Bassett DS, Bullmore ET (2009). Human brain networks in health and disease. Curr Opin Neurol 22, 340–47.

Bullmore ET, Bassett DS (2011) Brain graphs: graphical models of the human brain connectome. Annu Rev Clin Psychol 7, 113–40.

Hilgetag CC, Burns GA, O’Neill MA, Scannell JW, Young MP (2000). Anatomical connectivity defines the organization of clusters of cortical areas in the macaque monkey and the cat. Philos Trans R Soc London B Biol Sci 355, 91–110.

He Y, Chen ZJ, Evans AC (2008). Structural insights into aberrant topological patterns of large-scale cortical networks in Alzheimer’s disease. J. Neurosci 28, 4756–66.

Le Bihan D, Mangin JF, Poupon C, Clark CA, Pappata S, Molko N, Chabriat H (2001). Diffusion tensor imaging: concepts and applications. J Magn Reson Imaging 13, 534-546.

Lee U, Muller M, Noh GJ, Mashour GA (2011). Dissociable network properties of anesthetic state transitions. Anesthesiology 114, 872-81.

Olaf Sporns, Networks of the brain, The MIT Press, Cambridge, Massachusetts London, England.

Sporns O, Chialvo DR, Kaiser M, Hilgetag CC (2004). Organization, development and function of complex brain networks. Trends Cogn Sci 8, 418–25.

Zalesky A, Fornito A, Harding IH, Cocchi L, Yucel M, et al. (2010). Whole-brain anatomical networks: Does the choice of nodes matter? Neuroimage 50, 970–83.

Brain network: Hagmann P, Cammoun L, Gigandet X, Meuli R, Honey CJ, et al. (2008) Mapping the Structural Core of Human Cerebral Cortex. PLoS Biol 6(7): e159

Protein network from “http://www.visualcomplexity.com/vc/project_details.cfm?id=120&index=120&domain=“

Neural network from “http://www.visualcomplexity.com/vc/project.cfm?id=307”

Brain network from “Denis Le Bihan et al. (2001), Diffusion tensor imaging : concepts and applications, J Mag Res Imag 2001 3, 534-548”

Social netowrk of artist from“ http://www.visualcomplexity.com/vc/project.cfm?id=119”

Disease network from “http://www.northeastern.edu/northeasterncreates/submissions/multimedia.html”

Figures from “Rubinov R, Sporns O. (2010), Complex network measures of brain connectivity: uses and interpretations, neuroimage 52, 1059-69

“Bullmore, E., and Sporns, O (2009). Complex brain networks: graph theoretical analysis of structural and functional systems. Nat Rev Neurosci 10, 186–198”

Typical brain Network figure from “Strogatz et al., 2001, Exploring complex networks, Nature 410, 268-276”

Figure from “ Watts DJ and Strogatz SH(1998) “ Collective dynamics of small world networks, Nature 393 : 409-10”

**Content by: UnCheol Lee and George Mashour**

Prezi by: Andrew Park

Prezi by: Andrew Park