Network Theory & Science
Selected papers, videos, books and resources.

Center for Complex Network Research

1. Human disease classification in the postgenomic era:
   A complex systems approach to human pathobiology
   J. Loscalzo, I. Kohane, A.-L. Barabási
   Molecular Systems Biology 3 (124), 1-11 (2007)
   Contemporary classification of human disease derives from observational correlation between pathological analysis and clinical syndromes. Characterizing disease in this way established a nosology that has served clinicians well to the current time, and depends on observational skills and simple laboratory tools to define the syndromic phenotype. Yet, this time-honored diagnostic strategy has significant shortcomings that reflect both a lack of sensitivity in identifying preclinical disease, and a lack of specificity in defining disease unequivocally. In this paper, we focus on the latter limitation, viewing it as a reflection both of the different clinical presentations of many diseases (variable phenotypic expression), and of the excessive reliance on Cartesian reductionism in establishing diagnoses. The purpose of this perspective is to provide a logical basis for a new approach to classifying human disease that uses
   
2. The human disease network
   K.-I. Goh, M. E. Cusick, D. Valle, B. Childs, M. Vidal, A.-L. Barabási
   Proceedings of the National Academy of Sciences 104 (21), 8685 (2007)
   [ Supplementary Materials 1 , 2 , 3 , 4 , 5 ] [ Fig(s). 1 , 2 , 3 , 4 ] [Website] [Poster]
   A network of disorders and disease genes linked by known disorder–gene associations offers a platform to explore in a single graphtheoretic framework all known phenotype and disease gene associations, indicating the common genetic origin of many diseases. Genes associated with similar disorders show both higher likelihood of physical interactions between their products and higher expression profiling similarity for their transcripts, supporting the existence of distinct disease-specific functional modules. We find that essential human genes are likely to encode hub proteins and are expressed widely in most tissues. This suggests that disease genes also would play a central role in the human interactome. In contrast, we find that the vast majority of disease genes are nonessential and show no tendency to encode hub proteins, and their expression pattern indicates that they are localized in the functional periphery of the network. A selection-based model explains the observed difference between essential and disease genes and also suggests that diseases caused by somatic mutations should not be peripheral, a prediction we confirm for cancer genes.
   
   
   Mapping the Human ‘Diseasome’
   Researchers created a map linking different diseases, represented by circles, to the genes they have in common, represented by squares.
   Redefining Disease, Genes and All. Andrew Pollack, NY Times, 6 May 2008
   
   
3. Network Medicine — From Obesity to the “Diseasome”
   A.L. Barabási New England Journal of Medicine 357, 404-407 (2007)
   
4. Drug-target network
   M. A. Yildirim, K.-L. Goh, M.E. Cusick, A.-L. Barabási, M. Vidal
   Nature Biotechnology 25:10, 1119-1126 (2007)
   
5. Predicting synthetic rescues in metabolic networks
   A. Motter, N. Gulbahce, E. Almaas, A.-L. Barabási
   Molecular Systems Biology 4:168, 1-10 (2008)
   [ PDF ] [ Supplementary Materials 1 ] [ Tables 1 , 2 , 3 , 4 ]
   An important goal of medical research is to develop methods to recover the loss of cellular function due to mutations and other defects. Many approaches based on gene therapy aim to repair the defective gene or to insert genes with compensatory function. Here, we propose an alternative, network-based strategy that aims to restore biological function by forcing the cell to either bypass the functions affected by the defective gene, or to compensate for the lost function. Focusing on the metabolism of single-cell organisms, we computationally study mutants that lack an essential enzyme, and thus are unable to grow or have a significantly reduced growth rate. We show that several of these mutants can be turned into viable organisms through additional gene deletions that restore their growth rate. In a rather counterintuitive fashion, this is achieved via additional damage to the metabolic network. Using flux balance-based approaches, we identify a number of synthetically viable gene pairs, in which the removal of one enzyme-encoding gene results in a non-viable phenotype, while the deletion of a second enzyme-encoding gene rescues the organism. The systematic network-based identification of compensatory rescue effects may open new avenues for genetic interventions.
   
6. The implications of human metabolic network topology for disease comorbidity
   D.-S. Lee, J. Park, K. A. Kay, N. A. Christakis, Z. N. Oltvai, A.-L. Barabási
   Proceedings of the National Academy of Sciences 105, 9880-9885 (2008)
   [ Supplementary Materials 1 , 2 , 3 ] [ Tables 1 , 2 , 3 , 4 , 5 ] [ Fig(s). 1 , 2 , 3 ] [Cover]
   Most diseases are the consequence of the breakdown of cellular processes, but the relationships among genetic/epigenetic defects, the molecular interaction networks underlying them, and the disease phenotypes remain poorly understood. To gain insights into such relationships, here we constructed a bipartite human disease association network in which nodes are diseases and two diseases are linked if mutated enzymes associated with them catalyze adjacent metabolic reactions. We find that connected disease pairs display higher correlated reaction flux rate, corresponding enzyme-encoding gene coexpression, and higher comorbidity than those that have no metabolic link between them. Furthermore, the more connected a disease is to other diseases, the higher is its prevalence and associated mortality rate. The network topology-based approach also helps to...
   

1. The product space conditions the development of nations
   C.A. Hidalgo, R. B. Klinger, A.-L. Barabási, R. Hausmann
   Science 317, 482 (2007)
   [Website] [Cover]
   Economies grow by upgrading the products they produce and export. The technology, capital, institutions, and skills needed to make newer products are more easily adapted from some products than from others. Here, we study this network of relatedness between products, or “product space,” finding that more-sophisticated products are located in a densely connected core whereas lesssophisticated products occupy a less-connected periphery. Empirically, countries move through the product space by developing goods close to those they currently produce. Most countries can reach the core only by traversing empirically infrequent distances, which may help explain why poor countries have trouble developing more competitive exports and fail to converge to the income levels of rich countries.
   

1. Evolution of the social network of scientific collaborations
   A.L. Barabási, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, T. Vicsek
   Physica A 311, 590-614 (2002)
   The co-authorship network of scientists represents a prototype of complex evolving networks. In addition, it o8ers one of the most extensive database to date on social networks. By mapping the electronic database containing all relevant journals in mathematics and neuro-science for an 8-year period (1991–98), we infer the dynamic and the structural mechanisms that govern the evolution and topology of this complex system. Three complementary approaches allow us to obtain a detailed characterization. First, empirical measurements allow us to uncover the topological measures that characterize the network at a given moment, as well as the time evolution of these quantities. The results indicate that the network is scale-free, and that the network evolution is governed by preferential attachment, a8ecting both internal and external links. However, in contrast with most model predictions the average degree increases in time, and the node separation decreases. Second, we propose a simple model that captures the network’s time evolution. In some limits the model can be solved analytically, predicting a two-regime scaling in agreement with the measurements. Third, numerical simulations are used to uncover the behavior of quantities that could not be predicted analytically. The combined numerical and analytical results underline the important role internal links play in determining the observed scaling behavior and network topology. The results and methodologies developed in the context of the co-authorship network could be useful for a systematic study of other complex evolving networks as well, such as the world wide web, Internet, or other social networks.
   
2. Measuring preferential attachment in evolving networks
   H. Jeong, Z. Neda, A.-L. Barabási
   Europhysics Letters 61, 567-572 (2003)
   A key ingredient of many current models proposed to capture the topological evolution of complex networks is the hypothesis that highly connected nodes increase their connectivity faster than their less connected peers, a phenomenon called preferential attachment. Measurements on four networks, namely the science citation network, Internet, actor collaboration and science coauthorship network indicate that the rate at which nodes acquire links depends on the node’s degree, offering direct quantitative support for the presence of preferential attachment. We find that for the first two systems the attachment rate depends linearly on the node degree, while for the last two the dependence follows a sublinear power law.
   
3. Quantifying social group evolution
   G. Palla, A.-L. Barabási, T. Vicsek
   Nature 446:7136, 664-667 (2007)
   [ Supplementary Materials 1 ]
   Our focus is on networks capturing the collaboration between scientists and the calls between mobile phone users. We find that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability. The behaviour of small groups displays the opposite tendency—the condition for stability is that their composition remains unchanged. We also show that knowledge of the time commitment of members to a given community can be used for estimating the community’s lifetime. These findings offer insight into the fundamental differences between the dynamics of small groups and large institutions.
   
4. Structure and tie strengths in mobile communication networks
   J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.-L. Barabási
   Proceedings of the National Academy of Sciences 104 (18), 7332-7336 (2007)
   [ PDF ] [ Supplementary Materials 1 , 2 , 3 , 4 ]
   Electronic databases, from phone to e-mails logs, currently provide detailed records of human communication patterns, offering novel avenues to map and explore the structure of social and communication networks. Here we examine the communication patterns of millions of mobile phone users, allowing us to simultaneously study the local and the global structure of a society-wide communication network. We observe a coupling between interaction strengths and the network's local structure, with the counterintuitive consequence that social networks are robust to the removal of the strong ties but fall apart after a phase transition if the weak ties are removed. We show that this coupling significantly slows the diffusion process, resulting in dynamic trapping of information in communities and find that, when it comes to information diffusion, weak and strong ties are both simultaneously ineffective.
   
5. Analysis of a large-scale weighted network of one-to-one human communication
   J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, M A. de Menezes, K. Kaski, A.-L. Barabási, J. Kertész
   New Journal of Physics 9, 1-27 (2007)
   We construct a connected network of 3.9 million nodes from mobile phone call records, which can be regarded as a proxy for the underlying human communication network at the societal level. We assign two weights on each edge to reflect the strength of social interaction, which are the aggregate call duration and the cumulative number of calls placed between the individuals over a period of 18 weeks. We present a detailed analysis of this weighted network by examining its degree, strength, and weight distributions, as well as its topological assortativity and weighted assortativity, clustering and weighted clustering, together with correlations between these quantities. We give an account of motif intensity and coherence distributions and compare them to a randomized reference system. We also use the concept of link overlap to measure the number of common neighbours any two adjacent nodes have, which serves as a useful local measure for identifying the interconnectedness of communities. We report a positive correlation between the overlap and weight of a link, thus providing strong quantitative evidence for the weak ties hypothesis, a central concept in social network analysis. The percolation properties of the network are found to depend on the type and order of removed links, and they can help understand how the local structure of the network manifests itself at the global level.We hope that our results will contribute to modelling weighted large-scale social networks, and believe that the systematic approach followed here can be adopted to study other weighted networks.
   
6. The dynamics of a mobile phone network
   C. A. Hidalgo, C. Rodriguez-Sickert
   Physica A 387:12, 3017-3024 (2008)
   
7. Uncovering individual and collective human dynamics from mobile phone records
   J. Candia, M. C. Gonzalez, P. Wang, T. Schoenharl, G. Madey, A.-L. Barabási
   Journal of Physics A: Mathematical and Theoretical 41, 1-11 (2008) [Cover]
   
8. Understanding individual human mobility patterns
   M. C. González, C. A. Hidalgo, A.-L. Barabási
   Nature 453, 779-782 (2008)
   [ Supplementary Materials 1 , 2 , 3 ] [Website] [Cover]
   Despite their importance for urban planning, traffic forecasting and the spread of biological and mobile viruses, our understanding of the basic laws governing human motion remains limited owing to the lack of tools to monitor the time-resolved location of individuals. Here we study the trajectory of 100,000 anonymized mobile phone users whose position is tracked for a six-month period. We find that, in contrast with the random trajectories predicted by the prevailing Levy flight and random walk models, human trajectories show a high degree of temporal and spatial regularity, each individual being characterized by a time independent characteristic travel distance and a significant probability to return to a few highly frequented locations. After correcting for differences in travel distances and the inherent anisotropy of each trajectory, the individual travel patterns collapse into a single spatial probability distribution, indicating that, despite the diversity of their travel history, humans follow simple reproducible patterns. This inherent similarity in travel patterns could impact all phenomena driven by human mobility, from epidemic prevention to emergency response, urban planning and agent-based modeling.
   
9. The art of community detection
   N. Gulbahce, S. Lehmann
   BioEssays 30:10, 934-938 (2008)
   Networks in nature possess a remarkable amount of structure. Via a series of data-driven discoveries, the cutting edge of network science has recently progressed from positing that the random graphs of mathematical graph theory might accurately describe real networks to the current viewpoint that networks in nature are highly complex and structured entities. The identification of high order structures in networks unveils insights into their functional organization. Recently, Clauset, Moore, and Newman, introduced a new algorithm that identifies such heterogeneities in complex networks by utilizing the hierarchy that necessarily organizes the many levels of structure. Here, we anchor their algorithm in a general community detection framework and discuss the future of community detection.