Introduction

This version of the plugin, represents a complete overhaul, refactoring and redesign of the previous version. Major new features include the functionality of browsing the opened VMRs, support for protocol files (with some restrictions), new interactive plots and numerous of bug triages and fixes.

Goal

The purpose of the plugin, is to provide an extra layer in the analysis of brain connectivity, through a graph theoretical approach. It is comprised of two distinct entities, one is the brainnets, and the other, the plugin itself. brainnets is our in-house library for dealing with graph networks. The backbone network algorithms and features are implemented in this library. The plugin on the other, acts as GUI and glue between BrainVoyager 21.x and brainnets. It helps the user load the requested data, configure an analysis pipeline, compute and report different graph features and metrics, and visualize the results in an interactive manner.

Basic concepts of Graph Theory

Here shortly, we will give the basic concepts and notations for graph theoery as usually used. For more comprehensive materials on the topic, the interested readers are encouraged to consult (Sporns, 2010).

A set of vertices (or nodes) \(V\) and their associated edges (or connections) \(E\), make up a graph structure \(G = (V, E)\). The edges \(E\) can be either weighted (\(W\)) or binary (\(B\)) in which case they just indicate the presence of a connection between the nodes. Moreover, we can further distinguish the types edges based on the directionality of the connections, directed (\(D\)) or undirected(\(U\)).

Below is a sample connectivity matrix (weighted) and its representation as a graph structure. For the adjacency matrix, notice the symmetricity,which also implies undirectionality. For the graph, notice that the lines’ weights are relative to the connections’ weights as well as their color.

Usage

The minimum required version, is BrainVoyager 21.x. Make sure you have the plugin installed into the proper directory and it’s visible and accessible in the Plugins menu. Also, you have to have currently opened your VMR files beforehand. The plugin will fetch the the list of currently opened VMR files and prompt the user to select which one to work with. In case you load a VMR after you execute the plugin, it will not show up.

Supported formats

File formats

The curernt version supports VMR/VTC and VOI files. The protocol (PRT) files, for now support triggers only in Volume Resolution. Also, the begin and end volume must be identical. For example, consider the contents of the following protocol file, how the triggers are defined:

NrOfConditions:     4

TriggerXX
4
  31   31
  65   65
  75   75
  89   89
Color: 255 0 0

This setup is experimental, and we plan to make it more robust.

Transformation spaces

We have tested ACPC, MNI and TAL/aTAL spaces with different datasets.

Resolution

The voxels are accessed without any interpolation (i.e. trilinear) whether or not the resolution of the VMR/VTC pair is a match. In any case the voxels are access directly by their X, Y, Z coordinates (transformed into the target space). Consider the following pairs of resolutions:

VMR VTC Behavior
1x1x1 1x1x1 If both resolutions match, the resulting time series will be identical with BrainVoyager.
3x3x3 1x1x1 The accessed voxels will be different from BrainVoyager because we do not (for the time being) interpolate the values of the voxels (i.e. trilinear).

Settings

The latest version of the plugin, supports an array of settings stored externally in an ini file. The ini file must be named cganalysis_plugin.ini and placed in the same directory with the plugin (i.e. ~/Documents/BVExtensions/Plugins64/).

The contents of the plugin may look like the following:

[plugin]

[brainnets]
dump_all=true
dump_output_dir=c:/Temp/

In the future more settings will be exposed to the user.

Group plugin

The settings in this group are of general nature. For example enabling verbose logging capabilities for the plugin, or the number of threads to use.

For now it is a placeholder.

Group brainnets

The settings in this group affect and control some aspects of the library brainnets.

  • Saving matrices and time series.

    Variable Default Value Accepted Values Description
    dump_all false true or false Enables/disables the dumping of the matrices.
    dump_output_dir c:/Temp/ An existing directory

    The produced files in sequence are:

    # Step Filename Description
    #1 connectivity_ts.csv Extracted time series; they will be used for estimating the connectivity.
    #2 correlation_mtx_0.csv Estimated connectivity matrix.
    #3 correlation_mtx_0_treatment_pass_1.csv 1st treatment pass; filter positive, negative or absolute values from the connectivity matrix.
    #4 correlation_mtx_0_treatment_pass_2.csv 2nd treatment pass; replace NaNs and INFs with 0.0.
    #5 correlation_mtx_0_mst.csv Optional, the MST-filtered matrix.

    The final connectivity matrix is given by Step #4, or if enabled, Step #5.

Tab: Data

Below, is the main window you will be prompted with, when you execute the plugin. You will have to load a pair of VTC / VOI files and provide a sample name for the current analysis. It is recommended to fill in a short, meaningful name.

You may also, optionaly, load and use a protocol (PRT) file. If there is such a protocol referenced in the VTC file, it will be loaded and linked automatically. In case you use a protocol, the connectivity matrices will be estimated invdividually for each condition.

In either case, in case of an error occuring (i.e. the transformation spaces do not match, or the resolution is not supported) you will be promted to take action.

As soon as all the files have been loaded successfuly, you will no longer be able to load other file on the specific subject.

Loading Data

Protocol Support

Tab: Functional Connectivity

As soon as, the data have been loaded into memory, you are able to navigate and scroll through the available options in the “Functional Connectivity” tab. Here, you will find all the necessary settings to conduct a connectivity study.

Depending on which kind of study you are interested “Voxel to Voxel” or “Seed to Seed”, you will be presented with similar prompts.

Seed to Seed (VOI to VOI)

When opting-in for the “seed to seed” approach, you will be prompted to selected which VOIs you would like to include in the connectivity analysis. At least two must be available and selected. To select the desired VOIs, left-click with the mouse, and scroll over the list (if possible), or, select each VOI individually, one at a time with “control + left-click”.

In our simple demostration, will use the later option. Notice that we supress the subject’s results dialog by unchecking “Show Single Subject’s Results Dialog”. We wil show how to access this dialog in the subsequent “Group Analysis” tab.

Voxel to Voxel

Please note that (in the current version, this option has been disabled)

In the case “Voxel to Voxel”, the dropdown list will be populated with the available VOIs defined in the VOI file. The connectivity will be estimated within the selected VOI, amongst its voxels.

One, may have noticed that we deselected the option “Show subject’s dialog”. This is done to suppress the results dialog, and is useful when analysing multiple subjects. How to access a subject’s results dialog is shown in the next paragraph.

Tab: Group Analysis

The tab “Group Analysis”, bears a two-fold functionality. Firstly, on the top table, all the subjects’ analysis run, will be listed there and you can browse them; to open a subject’s dialog window just double-click on the name. So, even if you clock a subject’s results dialog, you can always access through this table.

The main functionality of this tab is the comparison of connectivity matrices of multiple subjects/studies. To do so, just choose the subjects from the list you would like to include, and then launch the comparison with the Compute button. You may optionally use the MST filtered matrices if they have been computed.

Subject’s Dialog

The subject’s dialog provides numerous options and actions; most of the them are self-explanatory. We will go through, the two most improtant tabs in the plugin, the Visualization and Graph Analysis.

Visualization

We supply two methods of visualizing the connectivity matrices. The first one, is the standard “Block matrix” (similar and alike to MATLAB’s visualization). And the other one, is a more intuitive plot, called, Circular Plot. There are a few options for both plots, however more emphasis is given to the circular plot.

In the following animation, we plot the connectivity matrix within a VOI, in a Voxel to Voxel level (thus the numeric labels); and having compute the Minimum Spanning Tree. By default, in the circular plot, all lines are black and their width is dictated by their adjacent connectivity value. The important links, as identified by the MST algorithm are drawn in red. Subsequently, we switch the colormap, and from black, the links are color based on their associated connectivity value. There are a few visualization and interaction options, i.e. the nodes’ size, the thickness of the lines, etc.

Simple Example

Example with Protocol Support

This example demonstrates how a dataset with a supported protocol is handled, with the conditions shown above the sliding bar. The triggers are represent with their name (just plain text) and no network is plotted. Also, notice the interactive features, such as filtering the plots when the mouse moves over a VOI.

Graph Analysis

The backbone of the plugin. The connectivity matrix is translated into a graph, and thus, you can compute and extract the different graph theoretical features of a graph. Some features produce only a scalar result, such as the “Global Effieciency”, and it’s displayed inplace, within the same window. However, most of the other features, produce either arrays or matrices, which you will able to inspect their plots, using the associated “inspect” button.

For example, computing the Global Efficiency in our example dataset, yields the following result:

Simple Example

In case of a simple dataset, the Strength, because it yields a scalar value for each Node in the graph, it returns an array which can be visualized using the “inspect” button (the following results are obtained using Seed to Seed).

Example with Multiple Conditions

When mutliple conditions are present, their features will be plotted in order and color-distinguished.

Example with Protocol Support

In case of a protocol file is used, the strength will be computed for each individual connectivity matrix belonging to each condition and plotted accordingly. On The legend the triggers will be also shown. This is work in progress.

Export

You may export the timeseries and the connectivity matrices from the “Metadata” tab.

Features

Connectivity profiles

Seed to Seed (VOI to VOI)

Given a number of VOIs (\(N_s\)), the average time series wihin each one of the VOIs is used. The connectivity is estimated using these average time series. The resuling adjacency matrix is of size \(N_s \times N_s\).

Voxel to Voxel

Please note that (in the current version, this option has been disabled)

All voxels within a given VOI are used, and the connectivity is estimated between them. This approach would be very interesting in cases where there is a relatively small number of voxels (\(N_v\)) within a VOI. The resulting adjacency matrix is of size \(N_s \times N_s\).

Connectivity estimators

Pearson’s correlation coefficient (\(\rho\))

Given two random variables \(X\) and \(Y\), we can measure their linear relationship. It is given from the following formula: \(\rho_{XY} = \frac{ \sum_{i=1}^n{(X_i - \overline{X})(Y_i - \overline{Y}) } }{(n-1)s_Xs_Y}\), where \(\overline{X}\) and \(\overline{Y}\) denote the means values, and \(s_X\), \(s_Y\) the standard deviations of \(X\) and \(Y\) respectively. The estimated values range in \([-1.0, 1.0]\).

Partial Correlation

It measures the degree of association between two random variables \(X\) and \(Y\), with the effect of a set of controlling random variables removed. We are using the matrix inversion formula to compute the partial correlation. Given \(\Omega(X, Y)\) a positive definite and invertible, correlation matrix, we can define \(P=\Omega^{-1}\) and thus, \(\rho_{X,Y}=- \frac{X}{\sqrt{XY}}\). The estimated values range in \([-1.0, 1.0]\).

Covariance

It is a measurement of the relationship of the variation of two random variables \(X\) and \(Y\). \(cov(X, Y) = \frac{1}{N - 1} (X - \overline{X})^*(Y - \overline{Y})\).

Graph features

The following graph features are support in the plugin organized in the folllwing categories.

Segragation

  • Clustering Coefficient

    The clustering coefficient of a node is the probability that the neighors of this node are also connected to each other. It is considered to be a measure of the local connectivity or cliqueness of a graph.

  • Local Effiency

    The local efficiency is the global efficiency computed on the neighborhood of the node, and is related to the clustering coefficient.

Integration

  • Global Efficiency

    The global efficiency is the average inverse shortest path length in the network, and is inversely related to the characteristic path length.

Centrality

  • Degree

    Measures the importance of a node through their number of connections/neighbors. One can take into account the incoming, outgoing or all connection from/to a node. This directionality is crucial to consider when working to directed adjancency matrices.

  • Eigenvector Centrality

    Eigenector centrality is a self-referential measure of centrality; nodes have higher values if they connect to other nodes that also exhibit high eigenvector centrality.

Nodal measures

  • Strength

    The sum of the weights of the connections of each node.

  • Nodal Global Efficiency

    The average of the inverse shortest path length from a node to the other in the graph.

Filtering

  • Minimum Spanning Trees

    We use a Kruskal’s greedy algorithm for the computation of MSTs (Kruskal, 1956). MSTs are used as an alternative, bias-free indicators for node significance, diminishing the need for statistical methods. Internally the weights are inversed with \(1.0 / A\), so as higher correlation values are represented as smaller distances.

Other

  • Laplacian Matrix

    The Laplacian matrix of a given graph \(G\) is easily computed as following: \[ L = D - A \] Where \(D\) denotes the degree matrix, and \(A\) the adjacency matrix. There are other special cases of the Laplacian matrix, but they are out of scope of our interest. The Laplacian matrix preserves the same information as the adjacency matrix but carries different properties and meanings, such as its eigenvalues and spectrum.

Graph distances

These methods are used to quantify the (dis)similarity between two or more adjacency matrices. For example, one would like to make a study on (something along the lines):

How do the connectivity profiles between the subjects of a control group and a target group compare.

Many methods have been proposed in the very active literature. Currently we have implemented the following methods:

Spectral Euclidean Distance

The spectral distance (Wilson & Zhu, 2008) between two adjacency (\(G\) and \(H\)) matrices is simply the Euclidean distance between their spectra (\(g\) and \(h\)). Also, one can use the Laplacian counterparts of the adjacency matrices. is computed using the following formula:

\[ d(G, H) = \sqrt{ \sum_i{ (g_i - h_j)^2 } } \]

Spectral Euclidean Distance Top-\(K\)

Given two matrices \(G\) and \(H\), we can use their \(k\) largest positive eigenvalues of their Laplacian counterparts (\(g\) and \(h\)) estimate their distance:

\[ d(G, H) = \begin{cases} \begin{matrix} \sqrt{\frac{ \sum_{i=1}^k{(g_i - h_i)^2} }{ \sum_{i=1}^l{g_i^2} }} & ,\sum_{i=1}^l{g_i^2} \leq \sum_{j=1}^l{h_j^2} \\ \sqrt{\frac{ \sum_{i=1}^k{(g_i - h_i)^2} }{ \sum_{j=1}^l{g_i^2} }} & , \sum_{i=1}^l{g_i^2} > \sum_{j=1}^l{h_j^2} \end{matrix} \end{cases} \]

For more details and information the interested readers are suggested to reference the papers (Jakobson & Rivin, 2000, p. @pincombe2007detecting).

TODO

We have some plans and ideas already, but if you would like to propose new features, please contact me.

Some of the requested and scheduled features include:

Updates

Plase check BrainVoyager’s support website for regular updates.

Thanks

I want to express my gratitude to the following people (in random order) who dedicated time and effort to test the plugin and provide valuable feedback:

Judith Eck
Rainer Goebel
Michael Luhrs
Armin Heinecke
Judith Peters

Open source

Changelog

20200113#1 (2.0.3-beta)
- General
 * Add support for ini settings file.
 * Allow from the ini file to toggle to dump the computed matrices in CSV files.
 * Experimental code for checking for update, accessing the voxels via threads and keeping track which voxels we accessed, is disabled for now.

- Visualization
 * Force the color of the labels to be black.
 
- Documentation
 * Update the documentation; add information about the interpolation of the voxels and the new ini file functionality.

Consult the accompanying file CHANGELOG for more details.

Download

Fetch the most recent releases:

Platform Version Link
Windows x64 2.0.3-beta (latest) win_x64
Linux x64 2.0.3-beta (latest) lnx_x64
mac OS X 2.0.3-beta (latest) macosx_x64

References

Jakobson, D., & Rivin, I. (2000). Extremal metrics on graphs i. arXiv Preprint Math/0001169.

Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50.

Pincombe, B. (2007). Detecting changes in time series of network graphs using minimum mean squared error and cumulative summation. ANZIAM Journal, 48, 450–473.

Sporns, O. (2010). Networks of the brain. MIT press.

Wilson, R. C., & Zhu, P. (2008). A study of graph spectra for comparing graphs and trees. Pattern Recognition, 41(9), 2833–2841.