Quantification of Graph Complexity Based on the Edge Weight Distribution Balance: Application to Brain Networks

Area of Science:

• Graph theory
• Network science
• Neuroscience

Background:

• Graph complexity is crucial for understanding system organization.
• Existing measures like graph density have limitations.
• Quantifying the interplay between information and order in complex networks is challenging.

Purpose of the Study:

• Introduce Shannon graph complexity (SGC), a novel global measure for weighted and binary graphs.
• Assess SGC's ability to capture the balance between information (Shannon entropy) and order (disequilibrium).
• Evaluate SGC's performance against graph density (GD) and its application to real-world neuroimaging data.

Main Methods:

• Developed SGC based on Shannon entropy and a disequilibrium measure of edge weight distribution.
• Validated SGC using synthetic graph datasets and electroencephalographic (EEG) recordings.
• Compared SGC with graph density (GD) and analyzed its properties concerning graph size and node degree distribution.

Main Results:

• SGC is invariant to graph density and independent of node degree distribution.
• SGC shows minimal variation with graph size.
• EEG data revealed altered weight distribution balance during cognitive tasks in schizophrenia patients compared to controls.

Conclusions:

• SGC offers a robust and novel approach to quantifying graph complexity.
• SGC is suitable for analyzing complex systems, including brain networks.
• Schizophrenia is associated with impaired brain network dynamic reorganization, particularly in secondary pathways.