bioRxiv2020
To understand the nature of the complex behavior of the brain, one important step is to identify "cores" in the brain network, where neurons or brain areas strongly interact with each other. Cores can be considered as essential sub-networks for brain functions. In the last few decades, an information-theoretic approach to identifying cores has been developed. In this approach, many-to-many nonlinear interactions between parts are measured by an information loss function, which quantifies how much information would be lost if interactions between parts were removed. Then, a core called a "complex" is defined as a subsystem wherein the amount of information loss is locally maximal. Although identifying complexes can be a novel and useful approach to revealing essential properties of the brain network, its practical application is hindered by the fact that computation time grows exponentially with system size. Here we propose a fast and exact algorithm for finding complexes, called Hierarchical Partitioning for Complex search (HPC). HPC finds complexes by hierarchically partitioning systems to narrow down candidates for complexes. The computation time of HPC is polynomial, which is dramatically smaller than exponential. We prove that HPC is exact when an information loss function satisfies a mathematical property, monotonicity. We show that mutual information is one such information loss function. We also show that a broad class of submodular functions can be considered as such information loss functions, indicating the expandability of our framework to the class. In simulations, we show that HPC can find complexes in large systems (up to several hundred) in a practical amount of time when mutual information is used as an information loss function. Finally, we demonstrate the use of HPC in electrocorticogram recordings from monkeys. HPC revealed temporally stable and characteristic complexes, indicating that it can be reliably utilized to characterize brain networks. Author summaryAn important step in understanding the nature of the brain is to identify "cores" in the brain network, which can be considered as essential areas for brain functions and cognition. In the last few decades, a novel definition of cores has been developed, which takes account of many-to-many interactions among elements of the network. Although considering many-to-many interactions can be important in understanding the complex brain network, identifying cores in large systems has been impossible because of the extremely large computational costs required. Here, we propose a fast and exact algorithm for finding cores. We show that the proposed algorithm enables us to find cores in large systems consisting of several hundred elements in a practical amount of time. We applied our algorithm to electrocorticogram recordings from a monkey that monitored electrical activity of the brain with electrodes placed directly on the brain surface, and demonstrated that there are stable and characteristic core structures in the brain network. This result indicates that our algorithm can be reliably applied to uncovering the essential network structures of the brain.