Definitions

adjacency matrix

The directed adjacency matrix describes how nodes are directionally connected to a graph

adapted from
PLoS supp. material by Hermann Cuntz

← a_tree_is_a_graph
→ using_graph_theory

When neuronal trees are regarded as graphs, their branching structure can be well described with the corresponding directed adjacency matrix dA (see “dA_tree”), a quadratic matrix of size NxN where N is the number of nodes in the tree. As mentioned earlier, the direction of the edges shows away from the first point, representing the arbitrary starting vertex S (= 1), the root of the tree. Note that the widely used .swc format (Cannon RC, Turner DA, Pyapali GK, Wheal HV, 1998, J Neurosci Methods 84: 49-54) for storing neuronal morphology is nothing else than a sparse representation of the adjacency matrix since it simply attributes to all nodes (row index) a parent node (column index).

Not each possible directed adjacency matrix represents a possible neuronal tree, since loops and branching points with more than two child branches are possible, but do not exist in natural dendritic trees. dA therefore never contains more than two entries in one column and no entry will lay directly on the diagonal. Also, each node has exactly one parent, apart from the root, which has none. Each row of dA therefore contains exactly one entry apart from the first, which contains none.

In order to derive most dendritic branching statistics using the typical descriptions, an algorithmic formulation by recursion is required to “walk” through a tree and collect statistics. Many operations for example on dendritic trees require processing with a stack and can therefore not be written analytically. With repeated matrix multiplication on the directed adjacency matrix as in dA^r the (i, j)-entry represents the number of distinct r-walks from node i to node j in the graph.