The theory of optimal percolation is currently being applied to understand the structure of the brain following our recent studies in Morone, Makse, Nature (Aug 2015). We have developed the analytical solution to the problem of identifying of the most influential nodes (essential nodes) in complex networks ; a long-standing problem in data science . This problem belongs to the class of non-deterministic polynomial-time hard problems (NP-hard), and therefore it is analogous to the hardest problems in computational science and spin glasses.
Our group has developed a large-scale search engine for localizing the most influential nodes in networks: the Collective Influence (CI) theory. CI combines optimality, scalability and versatility, making it applicable to a large class of problems, e.g., from finding influential areas in the brain, to containing epidemic outbreaks through targeted immunizations, maximizing the spreading of information in social media, or quantifying systemic risk in banking systems. We show that tools of combinatorial optimization, spectral theory, spin glasses and machine learning can be used to find the essential nodes in the network. The theory provides a ranking of nodes whose inhibition produces the largest disrupting cascading eﬀect extending to a large portion of the brain. Applying the theory of collective influence in the brain is the focus of our current and future research program as discussed next.
Fig. 1: In brain networks, some nodes are more important than others. Morone and Makse, Nature 2015 . The most important nodes are those whose elimination induces the network’s collapse, and identifying them is crucial in many circumstances, for example, to understand critical areas in the brain. But this is a hard task, and most methods available for the purpose are essentially based on trial-and-error. Morone and I have devised a rigorous method to determine the most influential nodes in net-works. We find that low-degree nodes surrounded by hubs as shown here play a much more important role in the network than previously thought.
The data that we used in this study can be downloaded here.
Theory of Collective Influence in the Brain
Accumulating evidence suggests that alterations in the functional brain network may lie behind a number of neurological and neuropsychiatric conditions. Existing interventional techniques (e.g. deep brain stimulation, transcranial magnetic stimulation) are currently being applied without taking into account the alterations in network dynamics thought to be at the root of neurological maladies. Our main hypothesis is that a therapeutic window exist to control network dynamics with targeted interventions to essential node’s activity rigorously predicted by our network theory of Collective Influence in the brain. The rationale is that the activation/deactivation patterns applied to the essential influential nodes predicted by our graph optimization theory will propagate through the central nervous system to impact and modulate brain network dynamics. Our theoretical advances allows researchers and treating clinicians to accurately identify new targets for focal therapy and to move away from “trial and error” therapeutic approach often currently employed. Our theories will allow neuroradiologists, neurosurgeons and the broad neuroscience community to identify and analyze the most influential parts of the brain in various disease states. The tools developed by us will aid in the understanding, diagnosis, and therapy of brain disorders thought to be due to disruptions of brain connectivity (e.g. brain tumors, Alzheimer’s disease, ADHD, strokes or traumatic brain injury). To this end, we are following two complementary research programs in rodents and humans that are providing the scaﬀold to test our hypotheses.
A. Manipulating essential nodes for integration in a in-vivo animal model of learning and memory guided by network optimization theory (NSF-CRCNS)
Our goal is to identify and manipulate nodes in the brain that are essential for global integration of information. This is crucial for a fundamental understanding of how the brain works as well as to treat neurological and psychiatric conditions. Evidence suggests that a few essential nodes in the brain control a number of crucial functions, such as memory formation, conscious perception and attention, as well as critically participating in brain dysfunctions. However, finding and manipulating essential nodes to control brain network dynamics has not been possible due to the lack of a theoretical framework that could guide prospective interventions.
Selection of targets and stimulation protocols in most studies are based on a questionable trial-and-error approach. What is fundamentally lacking is a network theory to guide these interventions. Advanced network theory applied to the brain will allow researchers and clinicians to prescribe targeted interventions to critical brain nodes.
Our Collective Influence network optimization theory [3, 2] allows to accurately predict the eﬀect of targeted inactivation of essential nodes in the network. Specifically, we use optimal percolation theory to identify the most influential nodes in a system-wide brain network formed in an in-vivo animal model of learning and memory (Fig. 2). Our network optimization theory predicts that the nucleus accumbens (NAc), a well-known structure in the meso-cortico-limbic system, is the most influential node for the interaction between the hippocampus (HC) and the prefrontal cortex (PFC) and the formation of an integrated memory network. This prediction is confirmed by the inhibition of a single core node in the NAc, using a targeted pharmacogenetic intervention, which remarkably, completely eliminates the formation of the memory (Fig. 3) .
In our experiments the nucleus accumbens (NAc) is identified as the essential node in the memory network–a finding that had not been anticipated by conventional hub-centric theory. Importantly, this empirical finding alters the prevailing view of the role of the NAc in memory formation. Previously the NAc had been seen as down-stream of the hippocampus and prefrontal cortex. Our data ascribes to the NAc an important up-stream modulatory role in memory formation.
Fig. 2: Collective Influence theory  predicts the es-sential nodes in a memory network induced by LTP in rats. a, Relative size of the giant connected component G of the memory network formed by HC, PFC and NAc under LTP as a function of the fraction of inactivated nodes, q. Shown are two strategies for choosing the essential nodes: Hub-inactivation (triangles) and CI-inactivation (circles). Most of the hubs (red symbols) are located in HC, yet, they are not essential for integra-tion: the hub-inactivation curve shows minimal damage to G upon removal of hubs. On the contrary, by just inactivating 7% of high CI nodes, the giant component collapses to almost zero. This in-dicates that the high CI nodes are the essential nodes in the NoN. Most of the essential nodes are in the NAc as seen by the major-ity of green symbols along the curve. b, Representative NoN for the same system as in a, displaying the PFC-HC-NAc networks. The size of nodes is proportional to CI. Most of the high CI nodes are in the NAc. c, We inactivate the top 3% of high CI nodes (yellow circles) and G is drastically reduced to less than 40% of its original value. These top CI nodes are all in NAc except for two nodes in PFC. d, Further inactivating upto 7% of the high CI nodes completely prevents integration of G. Yellow circles indicate the essential nodes which are in their majority located in NAc. e, Average CI map indicating how many times every node appears as a top CI node over six animals. Color bar represents the average CI rank. White areas correspond to the top essential nodes for integration which are all located in the NAc.
The ability to identify essential nodes in the brain has a profound importance in that it helps to understand global information processing. Most importantly, it represents a new paradigm in the identification of brain targets of neuropathological interest and open new therapeutic opportunities oriented to treat network dynamics. Even though we are currently focusing only on memory consolidation in the brain, our theory allows to design intervention protocols for a wide range of tasks due to its generality; interventions are being planned in the near future.
Fig. 3: Experimental confirmation in the memory model . a, The inhibitory version of DREADD receptors (hM4Di) is expressed in the NAc using a combination of two adenoassociated viruses (AAVs) injected stereotaxically in the nucleus as indicated. b, Histological verification 4 weeks after the viral infection. c, d, and e, Left side panels: single subject fMRI maps showing voxels activated by perforant path stimulation and overlaid on an anatomical T2-weighted image. Right side panels: BOLD time courses averaged (mean SEM) across animals (n=6) and extracted from ipsilateral and contralateral HC and ipsilateral PFC. c, LTP experiment for comparison ((-) AAV infection, (-) CNO administration) showing the expected activation of HC, PFC and NAc in POST-LTP. We note the evoked BOLD responses bilaterally in the HC (right panels), a landmark of HC-response after LTP induction. d, Upper: AAV infection in the NAc ((+) AAV, (-) CNO) preserves activation of the HC under perforant path stimulation before LTP. BOLD signal responses (left panel) are only evident in the ipsilateral HC as expected from PRE-LTP condition. Lower: inactivating the NAc by administration of CNO in the same animal ((+) AAV, (+) CNO) does not alter functional maps nor BOLD responses in the baseline (PRE-LTP) condition. e, NAc inactivation ((+) AAV, (+) CNO) prevents the activation of NAc and PFC induced by LTP (POST-LTP) as predicted by theory.
B. Predicting essential functional areas in the brain with tumor using Collective Influence Theory (NIH-Brain Initiative)
The identification of core influential nodes essential for proper brain function is applicable to tumor neurosurgery. Typically, neurosurgeons are presented with fMRI activation maps, which depict the locations of eloquent cortices (such as language and motor areas) adjacent to tumors, which neurosurgeons use to plan and guide the resection of gliomas and other intracranial masses. Notwithstanding its advantages, fMRI clearly has limitations. One of the main problems facing the preoperative evaluation of brain tumors by fMRI is that this technology depicts activations of both ’essential’ and ’non-essential’ functional areas. For a neurosurgeon, this distinction is of paramount importance. ’Essential’ language areas are defined as those, whose direct, intraoperative stimulation by electrodes leads to speech arrest. Resection of such an area leads to severe language deficits. In contradistinction, ’non-essential’ language areas are defined as those whose direct stimulation by electrodes does not lead to speech arrest. Resection of such areas is thought to be safe. The current fMRI technology does not allow one to diﬀerentiate between these areas. Our Collective Influence method  raises the distinct possibility of distinguishing between ’essential’ and ’non-essential’ nodes. By establishing the relative importance of various brain areas following Collective Influence theory, we inform the operating neurosurgeon more precisely of the relative importance of each section of the brain that s/he is planning to resect. Such an advance clearly leads to further improvements in the neurosurgical management of brain tumor patients. The ideas developed in functional brain imaging are tested against the current ’gold standard’ of localizing brain function – direct cortical stimulation of the exposed brain during neurosurgery in collaboration with Dr. Andrei Holodny at the Department of Radiology of Memorial Sloan-Kettering Cancer Center in New York City.
Network of Networks in the Brain
Neural activity measured in the human brain exhibits weak correlations over long distances. At the same time, activity forms highly correlated and tightly localized clusters, reflecting the functional specialization of different brain areas as described above. A fundamental open question in systems neuroscience is how these local clusters interact at the system scale to generate an integrated whole response without losing local independence, a problem known as the ‘binding problem’. Current paradigms in network theory leave this fundamental question unanswered.
Small-world and scale-free networks have been proposed to solve this basic conundrum: the brain needs to form modules which ought to be sufficiently independent to guarantee functional specialization and sufficiently connected to bind multiple processors for efficient information transfer. However, the small-world structure presents an intrinsic tension between shortcuts generating small-worlds and the persistence of modularity, a global property unrelated to local clustering as we have shown in our recent studies.
In a recent study published in PNAS 2012, we present a possible solution to this puzzle. We first show that critical percolation theory unambiguously defines a set of modules made of strong links in functional brain networks. Contrary to the common view, these modules are ‘large-world’ fractal structures and, therefore, are very far from being small-world. This means that information transfer in and out the modules is very inefficient; all distances are too far. However, incorporating the weak ties to the network below a critical percolation threshold converts it into a small-world preserving an underlying backbone of well-defined modules. Remarkably, weak ties are precisely organized as predicted by theory maximizing information transfer with minimal wiring costs. This trade-off architecture is reminiscent of the ‘strength of weak ties’ crucial concept of social networks. Such a design provides a natural solution to the paradox of efficient information flow in the highly modular structure of the brain.
In a paper published in Nature Physics in Oct 2014 (see cover below) we propose a departure from current models, replacing the concept of small-world by that of hierarchical network of networks (NoN) that describes the brain as a set of hierarchical modules made of strong links interconnected via a sea of weakly correlated links. Our group and collaborators have developed the theory of NoN and applied this new network paradigm to explain network brain activity in resting state and dual-tasking paradigm in humans and rats, see figure. Interestingly, the brain represents a paradigmatic case of a natural NoN and therefore we hypothesize that the NoN theory will capture the functional architecture of brain-wide neuronal networks. The hypothesis predicts that long-range correlation structure can be drastically altered by affecting link strength and activating or deactivating ‘core’ nodes of the structural network.
1. B. Min, A. Moreno, F. Morone, U. Pérez-Ramírez, L. Pérez-Cervera, L. C. Parra, A. Holodny, S. Canals, H. A. Makse. Finding essential nodes for integration in the brain using network optimization theory. Nature, submitted (2016).
2. F. Morone, K. Roth, B. Min, H. E. Stanley, H. A. Makse. A model of brain activation predicts the neural collective influence map of the brain. Proc. Nat. Acad. Sci., to appear (2017).
3. F. Morone, H. Makse. Influence maximization in complex networks through optimal percolation. Nature 524, 65 (2015).
4. S. D. S. Reis, Y. Hu, A. Babino, J. S. Andrade Jr., S. Canals, M. Sigman, H. A. Makse. Avoiding catastrophic failure in correlated Networks of Networks. Nat. Phys. 10, 762-767 (2014).
5. L. K. Gallos, H. A. Makse, M. Sigman. A small world of weak ties provides optimal global integration of self-similar modules in functional brain networks. Proc. Nat. Acad. Sci. 109, 2825-2830 (2012).
6. L. K. Gallos, H. A. Makse, M. Sigman. The conundrum of functional brain networks: small-world eﬃciency or fractal modularity. Front. Physiol. 3, 123 (2012).
7. F. Morone, H. A. Makse, The k-core structural collapse of dynamical complex systems, Nat. Phys., submitted (2016).
8. M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. Eugene Stanley, H. A. Makse. Identification of influential spreaders in complex networks. Nat. Phys. 6, 888-893 (2010). Cover of November 2010 issue.
9. C. Song, S. Havlin, H. A. Makse. Self-similarity of complex networks. Nature 433, 392-395 (2005).
10. C. Song, S. Havlin, H. A. Makse. Origins of fractality in the growth of complex networks. Nat. Phys. 2, 275 (2006).
11. L. Gallos, C. Song, S. Havlin, H. A. Makse. Scaling theory of transport in biological complex networks. Proc. Nat. Acad. Sci. 104, 7746 (2007).
12. H. D. Rozenfeld, C. Song and H. A. Makse. The small world-fractal transition in complex networks: a renormalization group approach. Phys. Rev. Lett. 104, 025701 (2010).
13. V. Galvao, J. G. V. Miranda, R. F. S. Andrade, J. S. Andrade Jr., L. K. Gallos, H. A. Makse. Modularity map of the network of human cell diﬀerentiation. Proc. Nat. Acad. Sci. 107, 5750-5755 (2010).
14. A. Bovet, F. Morone, H. A. Makse, Validation of Twitter opinion trends with national polling aggregates: Hillary Clinton vs Donald Trump, under review Nat. Commun. (2016).
15. S. Luo, F. Morone, C. Sarraute, H. A. Makse, Inferring personal financial status from social network location, under review Nat. Commun. (2016).
16. D. Rybski, S. Buldyrev, S. Havlin, F. Liljeros, H. A. Makse. Scaling laws of human interaction activity. Proc. Nat. Acad. Sci. 106, 12640-12645 (2009).
17. L. K. Gallos, S. Havlin, F. Liljeros, H. A. Makse. How people interact in evolving online aﬃliation networks. Phys. Rev. X 2, 031014 (2012).
18. Y. Hu, S. Havlin, H. A. Makse. Conditions for viral influence spreading through correlated multiplex networks. Phys. Rev. X 4, 021031 (2014).
19. H. A. Makse, S. Havlin, H. E. Stanley. Modelling urban growth patterns. Nature 377, 608-612 (1995).
20. H. D. Rozenfeld, D. Rybski, J. S. Andrade Jr., M. Batty, H. E. Stanley, H. A. Makse. Laws of population growth. Proc. Nat. Acad. Sci. 105, 18702-18707 (2008).
21. H. D. Rozenfeld, D. Rybski, X. Gabaix, H. A. Makse. The area and population of cities: New insights from a diﬀerent perspective on cities. Amer. Econ. Rev. 101, 560-580 (2011).
22. A. Baule, F. Morone, H. J. Herrmann, H. A. Makse. Edwards statistical mechanics for jammed granular matter. Rev. Mod. Phys., to appear (2017).
23. A. Baule, R. Mari, L. Bo, L. Portal, H. A. Makse. Mean-field theory of random close packings of axisymmetric particles. Nat. Commun. 4, 2194 (2013).
24. C. Song, P. Wang, H. A. Makse. Phase diagram of jammed matter. Nature 453, 629-632 (2008).
25. P. Wang, C. Song, H. A. Makse. Dynamic particle tracking reveals the aging temperature of a colloidal glass. Nat. Phys. 2, 526-531 (2006).
26. C. Song, P. Wang, H. A. Makse. Experimental measurement of an eﬀective temperature for jammed granular materials. Proc. Nat. Acad. Sci. 102, 2299-2304 (2005).
27. H. A. Makse, J. Kurchan. Testing the thermodynamic approach to granular matter with a numerical model of a decisive experiment. Nature 415, 614-617 (2002).
28. H. Makse, S. Havlin, P. King, H. Stanley. Spontaneous stratification in granular mixtures. Nature 386, 379 (1997).