Abstract:
The Key Player Problem (KPP), introduced by Stephen P. Borgatti, aims to identify a set of
k nodes (KP set) whose removal maximally disrupts communication within a network. These disruptions
can impair the integrity, strength, or efficiency of connections. While the KPP has been applied to various
complex networks, its use in brain networks remains largely unexplored. In brain networks, such disrup
tions are common in aging, neurological disorders, tumors, and brain injuries. However, in brain networks,
edge removal representing the loss or weakening of connections between regions—is more prevalent. These
edges may represent anatomical pathways or functional links. To address this research gap, we introduce
the Key Connection Problem (KCP), defined as identifying a set of k edges (KC set) whose removal most
severely disrupts network communication. We developed two algorithms Exhaustive k-Node Removal for
Global Efficiency Minimization (EnGEM) and Exhaustive k-Edge Removal for Global Efficiency Minimiza
tion (EnGEM-E) to detect both Key Players and Key Connections in a network. For the application of these
algorithms, structural brain networks were constructed from neuroimaging data of 100 cognitively normal
older adults (NC) and 100 Alzheimer’s disease (AD) subjects, each comprising 80 nodes and edges denoting
anatomical pathways. Key Player analysis revealed that in normal aging, the most disruption-causing nodes
were predominantly left-lateralized subcortical and memory related regions, whereas in Alzheimer’s disease,
they shifted toward the right hemisphere and frontal regions, reflecting disease-related changes in network
vulnerability. Key Connection analysis revealed that normal aging networks rely on posterior and limbic
connections, while Alzheimer’s disease networks show disrupted frontal–subcortical connections, reflecting
disease-specific structural connectivity alterations. This is the first study to formally define and investigate
the KPP and KCP in brain networks, providing a new framework for analyzing structural connectivity dis
ruptions in clinical neuroscience.
