Graph theory provides a useful way to measure and describe functional network structure in the brain (Gits, 2016). Unfortunately, a high barrier to entry has hindered its utilization in cognitive neuroscience. Neuro Graph offers a streamlined process for analyzing functional networks with graph theory, and in future versions aims to improve upon existing visualization methods for functional networks.
Bespoke for the Frontotemporal Disorders Unit at Massachusetts General Hospital/Harvard Medical School, Boston, MA.
Almost any system can be represented in terms of entities and the relationships between them. Therefore, it is no surprise that contemporary network analysis is the culmination of several fields of academic research. One important tip when analyzing networks is being very clear about the terminology being used. For instance, while graph theory is a branch of mathematics that represents entities and relationships as "vertices" and "edges" (Dickson, 2006), the sociological field of social network analysis refers to these as "nodes" and "ties", or sometimes "actors" and "links" (Butts, 2008). Collectively, vertices and edges are referred to as "graphs" or "networks". In the context of analyzing large-scale, functionally connected networks in the brain, we will refer to brain regions as "nodes", relationships between nodes as "connections" and the overall system as a "network". A review by Fellini et al. (2014) summarizes the traditional analysis procedure for network data in neuroscience:
Neuro-graph will simplify or even automate this process using existing infrastructure in the Dickerson Neuroimaging Lab and MGH Memory Disorders Unit. For resting-state functional network analysis, it uses output from the NRG fc-analysis script: the adjacency matrix of Pearson's r values between ROIs. This adjacency matrix represents the strength of connections between all nodes in the network. These values will be binarized by an a-priori threshold (a) and used to represent the underlying functional network (b). Neuro-graph will accomplish this with the open source (statnet) library for R.
The overall processing routine would be as follows:
Just as there are multiple levels of analysis in human subjects research, there are multiple levels of analysis in network analysis. A property which describes an individual node is called a node level index (NLI), while a property that describes the entire graph is called a graph level index (GLI). NLIs tend to describe how important, or "central" a node is based on how many connections it has, how many connections its connections have, the average number of steps it must take to reach all other nodes, and the extent to which it maintains the integrity of the macro-level graph structure (Freeman, 1979). Similarly, GLIs can describe the density of a network's connections, the extent to which a network structure is hierarchical, and the average number of connections all nodes have in the network (Anderson et al., 1999). There are dozens of NLIs and GLIs, only a fraction of which might be relevant in the context of functional brain connectivity. In most analyses, GLIs, or "global network measures", will be of far greater interest. A selection of these indicators are described in the next section.
Common Network Measures Used in Neuroscience Research (Rubinov and Sporns, 2010)
We will use the hypothetical network representation above to describe each indicator below.
-
Characteristic path length (Watts and Strogatz, 1998). The average distance between any two pairs of nodes, computed for all node pairs in the network.
-
Global efficiency (Latora and Marchiori, 2001). A measure of how efficiently a network can exchange information. Comparable to (1/average path length(L)). In our case, imagine an action potential being generated at random for any node. All nodes have an equal probability of generating the AP. How long would it take the AP to diffuse through the entire network? From node E, probably quite quickly. From node G, a bit longer.
-
Clustering coefficient (Watts and Strogatz, 1998). The degree to which nodes tend to cluster together. Essentially calculated as the number of total 2-paths (incompleted triangles) in a graph divided by the number of closed 2-paths (completed triangles). Note: permutations of triangle vertices are calculated as different triangles: A-B-C, B-A-C, and C-A-B count as 3 closed 2-paths.
-
Transitivity (Newman, 2003). The degree to which two-paths tend to be closed (form a triangle). Differs from clustering coefficient only in the way graph nodes are sampled during calculation. Clustering coefficient is a more common metric in contemporary network science. [http://pages.stat.wisc.edu/~karlrohe/netsci/MeasuringTrianglesInGraphs.pdf][(more info)]
-
Local efficiency (Latora and Marchiori, 2001). The local efficiency of a node is defined as the inverse of the average shortest path length between all of its neighbors. This value ranges from 0 to 1, with 1.0 representing an ideally efficient node.
-
Modularity (Newman, 2006). Modularity is a quality function whose optimization represents partitioned communities, or clusters, or points. Newman's method computes eigenvectors over an adjacency matrix, resulting in a "modularity matrix" for spectral analysis. Analogous to k-means and k-nearest neighbors clustering.
-
Closeness centrality (Freeman, 1978). A measure determining how close a node is to all other nodes in the graph. Calculated as the sum of the shortest paths between a node and all other nodes.
-
Betweenness centrality (Freeman, 1978). The fraction of all shortest paths in the network that contain a given node. Nodes with high values of betweenness centrality participate in a large number of shortest paths.
-
Within-module degree z-score (Guimera and Amaral, 2005). A within-module version of degree centrality. Requires a previously determined community/modularity structure (see above).
-
Participation coefficient (Guimera and Amaral, 2005). A measure of diversity of intermodular connections of individual nodes. Requires a previously determined community/modularity structure (see above).
- Degree distribution (Barabasi and Albert, 1999).
- Average neighbor degree (Pastor-Satorras et al., 2001).
- Assortativity coefficient (Newman, 2002).
- Measure of network "small-worldness" (Humphries and Gurney, 2008).
Create Dropbox link for reference literatureReview literatureDetermine node and graph level indices (NLIs; GLIs) of topical interest- Centralize prereqs for learning these techniques
- List all assumptions of input data when using this software
- Decide on input and output filetypes
Plan a data flow chart
- Output NLIs, GLIs
- Contextual links to more information about each measure
- Save output as file
- Automatic atlas-based ROI generation -- Freesurfer atlases -- AAL -- Harvard/Oxford -- Dynamic network measures?
- Maybe just cross-sectional tests for modulation
- visualization (the big one) -- nodes AND edges -- enable colorized factors (network subcomponents?) -- 3D rotation would be nice -- Brain Net Viewer on NITRC
- Graph Analysis Toolbox Software (for Matlab) on NITRC