Fast directed <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si222.svg" display="inline" id="d1e594"> <mml:mi>q</mml:mi> </mml:math> -analysis for brain graphs

<h2>Abstract</h2> Recent innovations in reconstructing large scale, full-precision, neuron-synapse-level connectomes demand subsequent improvements to graph analysis methods, to keep up with the growing complexity and size of the data. One such tool is the recently introduced <i>directed</i> <mml:math><mml:mi>q</mml:mi></mml:math><i>-analysis</i>. We present numerous improvements, theoretical and applied, to this technique. On the theoretical side, we introduce modified definitions for key elements of directed <mml:math><mml:mi>q</mml:mi></mml:math>-analysis, which remedy a well-hidden and previously undetected bias. This also leads to new, beneficial perspectives to the associated computational challenges. Most importantly, we present a high-speed, publicly available, low-level implementation that provides speed-ups of several orders of magnitude on <i>C. Elegans</i>. Furthermore, the speed gains grow with the size of the considered graph. This is made possible due to the mathematical and algorithmic improvements as well as a carefully crafted implementation. These speed-ups enable, for the first time, the analysis of full-sized connectomes like those obtained by recent reconstructive methods. Additionally, the speed-ups allow comparative analysis to corresponding null models, appropriately designed randomly structured artificial graphs that do not correspond to actual brains. This in turn, allows for assessing the efficacy and usefulness of directed <mml:math><mml:mi>q</mml:mi></mml:math>-analysis for studying the brain. We report on the results in this paper.