Dataset Information

Generalized network dismantling.

ABSTRACT: Finding an optimal subset of nodes in a network that is able to efficiently disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is a highly relevant problem of network science. In this paper, we address the generalized network-dismantling problem, which aims at finding a set of nodes whose removal from the network results in the fragmentation of the network into subcritical network components at minimal overall cost. Compared with previous formulations, we allow the costs of node removals to take arbitrary nonnegative real values, which may depend on topological properties such as node centrality or on nontopological features such as the price or protection level of a node. Interestingly, we show that nonunit costs imply a significantly different dismantling strategy. To solve this optimization problem, we propose a method which is based on the spectral properties of a node-weighted Laplacian operator and combine it with a fine-tuning mechanism related to the weighted vertex cover problem. The proposed method is applicable to large-scale networks with millions of nodes. It outperforms current state-of-the-art methods and opens more directions for understanding the vulnerability and robustness of complex systems.

SUBMITTER: Ren XL

PROVIDER: S-EPMC6452684 | biostudies-literature | 2019 Apr

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Generalized network dismantling.

Ren Xiao-Long XL Gleinig Niels N Helbing Dirk D Antulov-Fantulin Nino N

Proceedings of the National Academy of Sciences of the United States of America 20190315 14

Finding an optimal subset of nodes in a network that is able to efficiently disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is a highly relevant problem of network science. In this paper, we address the generalized network-dismantling problem, which aims at finding a set of nodes whose removal from the network results in the fragmentation of the network into subcritical network components at minimal overall cost. Compared with ...[more]

PMID: 30877241

Similar Datasets

Project description:Generalized spike-wave discharges in idiopathic generalized epilepsy are conventionally assumed to have abrupt onset and offset. However, in rodent models, discharges emerge during a dynamic evolution of brain network states, extending several seconds before and after the discharge. In human idiopathic generalized epilepsy, simultaneous EEG and functional MRI shows cortical regions may be active before discharges, and network connectivity around discharges may not be normal. Here, in human idiopathic generalized epilepsy, we investigated whether generalized spike-wave discharges emerge during a dynamic evolution of brain network states. Using EEG-functional MRI, we studied 43 patients and 34 healthy control subjects. We obtained 95 discharges from 20 patients. We compared data from patients with discharges with data from patients without discharges and healthy controls. Changes in MRI (blood oxygenation level-dependent) signal amplitude in discharge epochs were observed only at and after EEG onset, involving a sequence of parietal and frontal cortical regions then thalamus (P < 0.01, across all regions and measurement time points). Examining MRI signal phase synchrony as a measure of functional connectivity between each pair of 90 brain regions, we found significant connections (P < 0.01, across all connections and measurement time points) involving frontal, parietal and occipital cortex during discharges, and for 20 s after EEG offset. This network prominent during discharges showed significantly low synchrony (below 99% confidence interval for synchrony in this network in non-discharge epochs in patients) from 16 s to 10 s before discharges, then ramped up steeply to a significantly high level of synchrony 2 s before discharge onset. Significant connections were seen in a sensorimotor network in the minute before discharge onset. This network also showed elevated synchrony in patients without discharges compared to healthy controls (P = 0.004). During 6 s prior to discharges, additional significant connections to this sensorimotor network were observed, involving prefrontal and precuneus regions. In healthy subjects, significant connections involved a posterior cortical network. In patients with discharges, this posterior network showed significantly low synchrony during the minute prior to discharge onset. In patients without discharges, this network showed the same level of synchrony as in healthy controls. Our findings suggest persistently high sensorimotor network synchrony, coupled with transiently (at least 1 min) low posterior network synchrony, may be a state predisposing to generalized spike-wave discharge onset. Our findings also show that EEG onset and associated MRI signal amplitude change is embedded in a considerably longer period of evolving brain network states before and after discharge events.

Dataset Information

Generalized network dismantling.

Publications

Generalized network dismantling.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets