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

Pedro Vitor Rodrigues Da Conceicao, Dejan Govc, Janis Lazovskis, Ran Levi* (Corresponding Author), Henri Riihimaki, Jason P Smith

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
5 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)528-551
Number of pages24
JournalNetwork Neuroscience
Issue number2
Early online date2 Mar 2022
Publication statusPublished - 1 Jun 2022

Bibliographical note

Ran Levi, Engineering and Physical Sciences Research Council (, Award ID: EP/P025072/1. Dejan Govc, Javna Agencija za Raziskovalno Dejavnost RS (, Award ID: P1-0292-0083.

The authors wish to thank Michael Reimann of the Blue Brain Project for supporting this project and sharing his wisdom and knowledge with us, and Daniela Egas Santander for suggestions to advance our ideas.


  • binary dynamics
  • directed graphs
  • graph and topological parameters
  • neural networks
  • signal classification
  • Graph and topological parameters
  • Neural networks
  • Directed graphs
  • Binary dynamics
  • Signal classification


Dive into the research topics of 'An application of neighbourhoods in digraphs to the classification of binary dynamics'. Together they form a unique fingerprint.

Cite this