An application of neighbourhoods in digraphs to the classification of binary dynamics

• A binary state on a graph means an assignment of binary values to its vertices. A time-dependent sequence of binary states is referred to as binary dynamics. We describe a method for the classification of binary dynamics of digraphs, using particular choices of closed neighbourhoods. Our motivation and application comes from neuroscience, where a directed graph is an abstraction of neurons and their connections, and where the simplification of large amounts of data is key to any computation. We present a topological/graph theoretic method for extracting information out of binary dynamics on a graph, based on a selection of a relatively small number of vertices and their neighbourhoods. We consider existing and introduce new real-valued functions on closed neighbourhoods, comparing them by their ability to accurately classify different binary dynamics. We describe a classification algorithm that uses two parameters and sets up a machine learning pipeline. We demonstrate the effectiveness of the method on simulated activity on a digital reconstruction of cortical tissue of a rat, and on a nonbiological random graph with similar density. Author Summary We explore the mathematical concept of a closed neighbourhood in a digraph in relation to classifying binary dynamics on a digraph, with particular emphasis on dynamics on a neuronal network. Using methodology based on selecting neighbourhoods and vectorising them by combinatorial and topological parameters, we experimented with a dataset implemented on the Blue Brain Project reconstruction of a neocortical column, and on an artificial neural network with random underlying graph implemented on the NEST simulator. In both cases the outcome was run through a support vector machine algorithm reaching classification accuracy of up to 88% for the Blue Brain Project data and up to 81% for the NEST data. This work is open to generalisation to other types of networks and the dynamics on them.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

HUMANIORA  -- Filosofi, etik och religion -- Filosofi (hsv//swe)

HUMANITIES  -- Philosophy, Ethics and Religion -- Philosophy (hsv//eng)

TEKNIK OCH TEKNOLOGIER  -- Samhällsbyggnadsteknik -- Infrastrukturteknik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Civil Engineering -- Infrastructure Engineering (hsv//eng)

Keyword

Binary dynamics

Directed graphs

Graph and topological parameters

Neural networks

Signal classification

Publication and Content Type

ref (subject category)

art (subject category)