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

Area of Science:

• Computational Neuroscience
• Network Science
• Information Theory

Background:

• Identifying 'cores' or essential sub-networks in the brain is crucial for understanding brain function.
• Existing information-theoretic methods for identifying brain network cores ('complexes') are computationally intractable due to exponential growth in computation time with system size.

Purpose of the Study:

• To develop a computationally efficient and exact algorithm for identifying 'complexes' in brain networks.
• To enable the analysis of large-scale brain systems previously limited by computational constraints.

Main Methods:

• Proposed Hierarchical Partitioning for Complex search (HPC), an algorithm that hierarchically partitions systems to identify candidate complexes.
• Demonstrated HPC's polynomial computation time, making it feasible for large systems.
• Proved HPC's exactness for information loss functions satisfying monotonicity, such as mutual information and other submodular functions.

Main Results:

• HPC successfully identifies complexes in large systems (up to several hundred nodes) in practical computation times.
• The algorithm is proven to be exact when using monotonic information loss functions, including mutual information.
• Application of HPC to monkey electrocorticogram recordings revealed temporally stable and characteristic brain network complexes.

Conclusions:

• HPC offers a computationally feasible and exact method for identifying brain network cores ('complexes').
• This framework expands the applicability of information-theoretic approaches to complex network analysis.
• The findings facilitate a deeper understanding of brain organization and function through the identification of stable network structures.