Efficient search for informational cores in complex systems: Application to brain networks.

An important step in understanding the nature of the brain is to identify "cores" in the brain network, where 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, 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, its application is practically impossible because 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 hierarchically partitions systems to narrow down candidates for complexes. The computation time of HPC is polynomial, enabling us to find complexes in large systems (up to several hundred) in a practical amount of time. 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. We applied HPC to electrocorticogram recordings from a monkey and demonstrated that HPC revealed temporally stable and characteristic complexes.