M. Posfai, J. Gao, S. P. Cornelius, A.-L. Barabasi, R. D'Souza
Controllability of multiplex, multi-time-scale networks
Physical Review E 94: 3, 032316 (2016)
Read the abstract
The paradigm of layered networks is used to describe many real-world systems, from biological networks to social organizations and transportation systems. While recently there has been much progress in understanding the general properties of multilayer networks, our understanding of how to control such systems remains limited. One fundamental aspect that makes this endeavor challenging is that each layer can operate at a different time scale; thus, we cannot directly apply standard ideas from structural control theory of individual networks. Here we address the problem of controlling multilayer and multi-time-scale networks focusing on two-layer multiplex networks with one-to-one interlayer coupling. We investigate the practically relevant case when the control signal is applied to the nodes of one layer. We develop a theory based on disjoint path covers to determine the minimum number of inputs (Ni) necessary for full control. We show that if both layers operate on the same time scale, then the network structure of both layers equally affect controllability. In the presence of time-scale separation, controllability is enhanced if the controller interacts with the faster layer: Ni decreases as the time-scale difference increases up to a critical time-scale difference, above which Ni remains constant and is completely determined by the faster layer. We show that the critical time-scale difference is large if layer I is easy and layer II is hard to control in isolation. In contrast, control becomes increasingly difficult if the controller interacts with the layer operating on the slower time scale and increasing time-scale separation leads to increased Ni, again up to a critical value, above which Ni still depends on the structure of both layers. This critical value is largely determined by the longest path in the faster layer that does not involve cycles. By identifying the underlying mechanisms that connect time-scale difference and controllability for a simplified model, we provide crucial insight into disentangling how our ability to control real interacting complex systems is affected by a variety of sources of complexity.
J. Gao, B. Barzel, A.-L. Barabási
Universal resilience patterns in complex networks
Nature 530, 307-312 (2016)
Read the abstract
Resilience, a system’s ability to adjust its activity to retain its basic functionality when errors, failures and environmental changes occur, is a defining property of many complex systems. Despite widespread consequences for human health, the economy and the environment, events leading to loss of resilience—from cascading failures in technological systems to mass extinctions in ecological networks—are rarely predictable and are often irreversible. These limitations are rooted in a theoretical gap: the current analytical framework of resilience is designed to treat low-dimensional models with a few interacting components, and is unsuitable for multi-dimensional systems consisting of a large number of components that interact through a complex network. Here we bridge this theoretical gap by developing a set of
analytical tools with which to identify the natural control and state parameters of a multi-dimensional complex system, helping us derive effective one-dimensional dynamics that accurately predict the system’s resilience. The proposed analytical framework allows us systematically to separate the roles of the system’s dynamics and topology, collapsing the behaviour of different networks onto a single universal resilience function. The analytical results unveil the network characteristics that can enhance or diminish resilience, offering ways to prevent the collapse of ecological, biological or economic systems, and guiding the design of
technological systems resilient to both internal failures and environmental changes.
R. Sinatra, P. Deville, M. Szell, D. Wang, A.-L. Barabási
A century of physics
Nature Physics 11, 791-796 (2015)
Read the abstract
An analysis of Web of Science data spanning more than 100 years reveals the rapid growth andincreasing multidisciplinary of physics — as well its internal map of sub-disciplines.
L. Pappalardo, F. Simini, S. Rinzivillo, D. Pedreschi, F. Giannotti, A.-L. Barabási
Returners and explorers dichotomy in human mobility
Nature Communications 6:8166, 1-8 (2015)
Read the abstract
The availability of massive digital traces of human whereabouts has offered a series of novel insights on the quantitative patterns characterizing human mobility. In particular, numerous recent studies have lead to an unexpected consensus: the considerable variability in the characteristic travelled distance of individuals coexists with a high degree of predictability of their future locations. Here we shed light on this surprising coexistence by systematically investigating the impact of recurrent mobility on the characteristic distance travelled by individuals. Using both mobile phone and GPS data, we discover the existence of two distinct classes of individuals: returners and explorers. As existing models of human mobility cannot explain the existence of these two classes, we develop more realistic models able to capture the empirical findings. Finally, we show that returners and explorers play a distinct quantifiable role in spreading phenomena and that a correlation exists between their mobility patterns and social interactions.
I. A. Kovács, A.-L. Barabási
Destruction perfected
Nature (News & Views) 524, 38-39 (2015)
Read the abstract
Pinpointing the nodes whose removal most effectively disrupts a network has become a lot easier with the development of an efficient algorithm. Potential applications might include cybersecurity and disease control. See Letter p.65, by F. Morone and H. A. Makse (Supplementary 1).
B. Barzel, Y.-Y. Liu, A.-L. Barabási
Constructing minimal models for complex system dynamics
Nature Communications 6:7186, 1-8 (2015)
Read the abstract
One of the strengths of statistical physics is the ability to reduce macroscopic observations into microscopic models, offering a mechanistic description of a system’s dynamics. This paradigm, rooted in Boltzmann’s gas theory, has found applications from magnetic phenomena to subcellular processes and epidemic spreading. Yet, each of these advances were the result of decades of meticulous model building and validation, which are impossible to replicate in most complex biological, social or technological systems that lack accurate microscopic models. Here we develop a method to infer the microscopic dynamics of a complex system from observations of its response to external perturbations, allowing us to construct the most general class of nonlinear pairwise dynamics that are guaranteed to recover the observed behavior. The result, which we test against both numerical and empirical data, is an effective dynamic model that can predict the system’s behavior and provide crucial insights into its inner workings.
J. Menche, A. Sharma, M. Kitsak, D. Ghiassian, M. Vidal, J. Loscazlo, A.-L. Barabasi
Uncovering disease-disease relationships through the incomplete interactome
Science 347:6224, 1257601-1 (2015)
Read the abstract
According to the disease module hypothesis, the cellular components associated with a disease segregate in the same neighborhood of the human interactome, the map of biologically relevant molecular interactions. Yet, given the incompleteness of the interactome and the limited knowledge of disease-associated genes, it is not obvious if the available data have sufficient coverage to map out modules associated with each disease. Here we derive mathematical conditions for the identifiability of disease modules and show that the network-based location of each disease module determines its pathobiological relationship to other diseases. For example, diseases with overlapping network modules show significant coexpression patterns, symptom similarity, and comorbidity, whereas diseases residing in separated network neighborhoods are phenotypically distinct. These tools represent an interactome-based platform to predict molecular commonalities between phenotypically related diseases, even if they do not share primary disease genes.
Jianxi Gao, Y.-Y.Liu, R. M. D'Souza, A.-L. Barabási
Target control of complex networks
Nature Communications 5:5415, 1-7 (2014)
Read the abstract
Controlling large natural and technological networks is an outstanding challenge. It is typically neither feasible nor necessary to control the entire network, prompting us to explore target control: the efficient control of a preselected subset of nodes. We show that the structural controllability approach used for full control overestimates the minimum number of driver nodes needed for target control. Here we develop an alternate ‘k-walk’ theory for directed tree networks, and we rigorously prove that one node can control a set of target nodes if the path length to each target node is unique. For more general cases, we develop a greedy algorithm to approximate the minimum set of driver nodes sufficient for target control. We find that degree heterogeneous networks are target controllable with higher efficiency than homogeneous networks and that the structure of many real-world networks are suitable for efficient target control.
L. Gao, C. Song, Z. Gao, A.-L. Barabasi, J. P. Bagrow, D. Wang
Quantifying information flow during emergencies
Scientific Reports 4, 1-6 (2014)
Read the abstract
Recent advances on human dynamics have focused on the normal patterns of human activities, with the quantitative understanding of human behavior under extreme events remaining a crucial missing chapter. This has a wide array of potential applications, ranging from emergency response and detection to traffic control and management. Previous studies have shown that human communications are both temporally and spatially localized following the onset of emergencies, indicating that social propagation is a primary means to propagate situational awareness. We study real anomalous events using country-wide mobile phone data, finding that information flow during emergencies is dominated by repeated communications. We further demonstrate that the observed communication patterns cannot be explained by inherent reciprocity in social networks, and are universal across different demographics.
G. Ghoshal, L. Chi, A.-L. Barabási
Uncovering the role of elementary processes in network evolution
Scientifc Reports 3, 1-8 (2013)
Read the abstract
The growth and evolution of networks has elicited considerable interest from the scientific community and a number of mechanistic models have been proposed to explain their observed degree distributions. Various microscopic processes have been incorporated in these models, among them, node and edge addition, vertex fitness and the deletion of nodes and edges. The existing models, however, focus on specific combinations of these processes and parameterize them in a way that makes it difficult to elucidate the role of the individual elementary mechanisms. We therefore formulated and solved a model that incorporates the minimal processes governing network evolution. Some contribute to growth such as the formation of connections between existing pair of vertices, while others capture deletion; the removal of a node with its corresponding edges, or the removal of an edge between a pair of vertices. We distinguish between these elementary mechanisms, identifying their specific role on network evolution.
D. Wang, C. Song, A.-L. Barabási
Quantifying Long-Term Scientific Impact
Science 342, 127-131 (2013)
Read the abstract
The lack of predictability of citation-based measures frequently used to gauge impact, from impact factors to short-term citations, raises a fundamental question: Is there long-term predictability in citation patterns? Here, we derive a mechanistic model for the citation dynamics of individual papers, allowing us to collapse the citation histories of papers from different journals and disciplines into a single curve, indicating that all papers tend to follow the same universal temporal pattern. The observed patterns not only help us uncover basic mechanisms that govern scientific impact but also offer reliable measures of influence that may have potential policy implications.
B. Barzel, A.-L. Barabási
Universality in network dynamics
Nature Physics 9, 673-681 (2013)
Read the abstract
Despite significant advances in characterizing the structural properties of complex networks, a mathematical framework that uncovers the universal properties of the interplay between the topology and the dynamics of complex systems continues to elude us. Here we develop a self-consistent theory of dynamical perturbations in complex systems, allowing us to systematically separate the contribution of the network topology and dynamics. The formalism covers a broad range of steady-state dynamical processes and offers testable predictions regarding the system’s response to perturbations and the development of correlations. It predicts several distinct universality classes whose characteristics can be derived directly from the continuum equation governing the system’s dynamics and which are validated on several canonical network-based dynamical systems, from biochemical dynamics to epidemic spreading. Finally, we collect experimental data pertaining to social and biological systems, demonstrating that we can accurately uncover their universality class even in the absence of an appropriate continuum theory that governs the system’s dynamics.
T. Jia, A.-L. Barabási
Control capacity and a random sampling method in exploring controllability of complex networks
Scientific Reports 3:2354, 1-6 (2013)
Read the abstract
Controlling complex systems is a fundamental challenge of network science. Recent advances indicate that control over the system can be achieved through a minimum driver node set (MDS). The existence of multiple MDS's suggests that nodes do not participate in control equally, prompting us to quantify their participations. Here we introduce control capacity quantifying the likelihood that a node is a driver node. To efficiently measure this quantity, we develop a random sampling algorithm. This algorithm not only provides a statistical estimate of the control capacity, but also bridges the gap between multiple microscopic control configurations and macroscopic properties of the network under control. We demonstrate that the possibility of being a driver node decreases with a node's in-degree and is independent of its out-degree. Given the inherent multiplicity of MDS's, our findings offer tools to explore control in various complex systems.
B. Barzel, A.-L. Barabási
Network link prediction by global silencing of indirect correlations
Nature Biotechnology 31: Num 8, 1-8 (2013)
Read the abstract
Predictions of physical and functional links between cellular components are often based on correlations between experimental measurements, such as gene expression. However, correlations are affected by both direct and indirect paths, confounding our ability to identify true pairwise interactions. Here we exploit the fundamental properties of dynamical correlations in networks to develop a method to silence indirect effects. The method receives as input the observed correlations between node pairs and uses a matrix transformation to turn the correlation matrix into a highly discriminative silenced matrix, which enhances only the terms associated with direct causal links. Against empirical data for Escherichia coli regulatory interactions, the method enhanced the discriminative power of the correlations by twofold, yielding >50% predictive improvement over traditional correlation measures and 6% over mutual information. Overall this silencing method will help translate the abundant correlation data into insights about a system's interactions, with applications ranging from link prediction to inferring the dynamical mechanisms governing biological networks.
N. Blumm, G. Ghoshal, Z. Forro, M. Schich, G. Bianconi, J.-P. Bouchard, A.-L. Barabasi
Dynamics of ranking processes in complex systems
Physical Review Letters 109, 128701:1-5 (2012)
Read the abstract
The world is addicted to ranking: everything, from the reputation of scientists, journals, and universities to purchasing decisions is driven by measured or perceived differences between them. Here, we analyze empirical data capturing real time ranking in a number of systems, helping to identify the universal characteristics of ranking dynamics. We develop a continuum theory that not only predicts the stability of the ranking process, but shows that a noise-induced phase transition is at the heart of the observed differences in ranking regimes. The key parameters of the continuum theory can be explicitly measured from data, allowing us to predict and experimentally document the existence of three phases that govern ranking stability.
F. Simini, M. González, A. Maritan, A.-L. Barabási
A universal model for mobility and migration patterns
Nature 484, 96-100 (2012)
Read the abstract
Introduced in its contemporary form in 1946, but with roots that go back to the eighteenth century, the gravity law is the prevailing framework with which to predict population movement, cargo shipping volume and inter-city phone calls, as well as bilateral trade flows between nations. Despite its widespread use, it relies on adjustable parameters that vary from region to region and suffers from known analytic inconsistencies. Here we introduce a stochastic process capturing local mobility decisions that helps us analytically derive commuting and mobility fluxes that require as input only information on the population distribution. The resulting radiation model predicts mobility patterns in good agreement with mobility and transport patterns observed in a wide range of phenomena, from long-term migration patterns to communication volume between different regions. Given its parameter-free nature, the model can be applied in areas where we lack previous mobility measurements, significantly improving the predictive accuracy of most of the phenomena affected by mobility and transport processes.
Albert-László Barabási
The network takeover
Nature Physics 8, 14-16 (2012)
Read the abstract
Reductionism, as a paradigm, is expired, and complexity, as a field, is tired. Data-based mathematical models of complex systems are offering a fresh perspective, rapidly developing into a new discipline: network science.
G. Ghoshal, A.-L. Barabási
Ranking stability and super-stable nodes in complex networks
Nature Communications 2, 1-7 (2011)
Read the abstract
Pagerank, a network-based diffusion algorithm, has emerged as the leading method to rank web content, ecological species and even scientists. Despite its wide use, it remains unknown how the structure of the network on which it operates affects its performance. Here we show that for random networks the ranking provided by pagerank is sensitive to perturbations in the network topology, making it unreliable for incomplete or noisy systems. In contrast, in scale-free networks we predict analytically the emergence of super-stable nodes whose ranking is exceptionally stable to perturbations. We calculate the dependence of the number of super-stable nodes on network characteristics and demonstrate their presence in real networks, in agreement with the analytical predictions. These results not only deepen our understanding of the interplay between network topology and dynamical processes but also have implications in all areas where ranking has a role, from science to marketing.
Y.-Y. Liu, J.-J. Slotine, A.-L. Barabási
Few inputs can reprogram biological networks (reply by Liu et al.)
Nature 473, 167-173 (2011)
Read the abstract
Reply to Franz-Josef Muller and Andreas Schuppert (Nature 478, Pg. E4, Oct. 2011)
Y.-Y. Liu, J.-J. Slotine, A.-L. Barabási
Controllability of complex networks
Nature 473, 167-173 (2011)
Read the abstract
The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. Although control theory offers mathematical tools for steering engineered and natural systems towards a desired state, a framework to control complex self-organized systems is lacking. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes with time-dependent control that can guide the system’s entire dynamics. We apply these tools to several real networks, finding that the number of driver nodes is determined mainly by the network’s degree distribution. We show that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control, but that dense and homogeneous networks can be controlled using a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the high-degree nodes.
J. P. Bagrow, D. Wang, A.-L. Barabasi
Collective response of human populations to large-scale emergencies
PLoS One 6:3, 1-8 (2011)
Read the abstract
Despite recent advances in uncovering the quantitative features of stationary human activity patterns, many applications,from pandemic prediction to emergency response, require an understanding of how these patterns change when thepopulation encounters unfamiliar conditions. To explore societal response to external perturbations we identified real-timechanges in communication and mobility patterns in the vicinity of eight emergencies, such as bomb attacks andearthquakes, comparing these with eight non-emergencies, like concerts and sporting events. We find that communicationspikes accompanying emergencies are both spatially and temporally localized, but information about emergencies spreadsglobally, resulting in communication avalanches that engage in a significant manner the social network of eyewitnesses.These results offer a quantitative view of behavioral changes in human activity under extreme conditions, with potentiallong-term impact on emergency detection and response.
M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A.-L. Barabási, J. Saramäki
Small but slow world: How network topology and burstiness slow down spreading
Physical Review E 83, 1-4 (2011)
Read the abstract
While communication networks show the small-world property of short paths, the spreading dynamics in them turns out slow. Here, the time evolution of information propagation is followed through communication networks by using empirical data on contact sequences and the susceptible-infected model. Introducing null models where event sequences are appropriately shuffled, we are able to distinguish between the contributions of different impeding effects. The slowing down of spreading is found to be caused mainly by weight-topology correlations and the bursty activity patterns of individuals.
D. Wang, Z. Wen, H. Tong, C.-Y. Lin, C. Song, A.-L. Barabási
Information Spreading in Context
Proceeding for the 20th International World Wide Web Conference, 2011 , 1-10 (2011)
Read the abstract
Information spreading processes are central to human interactions. Despite recent studies in online domains, little is known about factors that could affect the dissemination of a single piece of information. In this paper, we address this challenge by combining two related but distinct datasets, collected from a large scale privacy-preserving distributed social sensor system. We find that the social and organizational context significantly impacts to whom and how fast people forward information. Yet the structures within spreading processes can be well captured by a simple stochastic branching model, indicating surprising independence of context. Our results build the foundation of future predictive models of information flow and provide significant insights towards design of communication platforms.
C. Song, T. Koren, P. Wang, A.-L. Barabási
Modelling the scaling properties of human mobility
Nature Physics 7, 713- (2010)
Read the abstract
Individual human trajectories are characterized by fat-tailed distributions of jump sizes and waiting times, suggesting the relevance of continuous-time random-walk (CTRW) models for human mobility. However, human traces are barely random. Given the importance of human mobility, from epidemic modelling to traffic prediction and urban planning, we need quantitative models that can account for the statistical characteristics of individual human trajectories. Here we use empirical data on human mobility, captured by mobile-phone traces, to show that the predictions of the CTRW models are in systematic conflict with the empirical results. We introduce two principles that govern human trajectories, allowing us to build a statistically self-consistent microscopic model for individual human mobility. The model accounts for the empirically observed scaling laws, but also allows us to analytically predict most of the pertinent scaling exponents.
C. Song, Z. Qu, N. Blumm, A.-L. Barabási
Limits of Predictability in Human Mobility
Science 327, 1018-1021 (2010)
Read the abstract
A range of applications, from predicting the spread of human and electronic viruses to city planning and resource management in mobile communications, depend on our ability to foresee the whereabouts and mobility of individuals, raising a fundamental question: To what degree is human behavior predictable? Here we explore the limits of predictability in human dynamics by studying the mobility patterns of anonymized mobile phone users. By measuring the entropy of each individual’s trajectory, we find a 93% potential predictability in user mobility across the whole user base. Despite the significant differences in the travel patterns, we find a remarkable lack of variability in predictability, which is largely independent of the distance users cover on a regular basis.
A.-L. Barabási
Scale-Free Networks: A Decade and Beyond
Science 325, 412-413 (2009)
Read the abstract
For decades, we tacitly assumed that the components of such complex systems as the cell, the society, or the Internet are randomly wired together. In the past decade, an avalanche of research has shown that many real networks, independent of their age, function, and scope, converge to similar architectures, a universality that allowed researchers from different disciplines to embrace network theory as a common paradigm. The decade-old discovery of scale-free networks was one of those events that had helped catalyze the emergence of network science, a new research field with its distinct set of challenges and accomplishments.
D.-S. Lee, H. Burd, J. Liu, E. Almass, O. Weist, A.-L. Barabási, Z. N. Oltvai, V. Kapatra
Comparative Genome-Scale Metabolic Reconstruction and Flux Balance Analysis of Multiple Staphylococcus aureus Genomes Identify Novel Antimicrobial Drug Targets
Journal of Bacteriology 191:12, 4015–4024 (2009)
Read the abstract
Mortality due to multidrug-resistant Staphylococcus aureus infection is predicted to surpass that of human immunodeficiency virus/AIDS in the United States. Despite the various treatment options for S. aureus infections, it remains a major hospital- and community-acquired opportunistic pathogen. With the emergence of multidrug-resistant S. aureus strains, there is an urgent need for the discovery of new antimicrobial drug targets in the organism. To this end, we reconstructed the metabolic networks of multidrug-resistant S. aureus strains using genome annotation, functional-pathway analysis, and comparative genomic approaches, followed by flux balance analysis-based in silico single and double gene deletion experiments. We identified 70 single enzymes and 54 pairs of enzymes whose corresponding metabolic reactions are predicted to be unconditionally essential for growth. Of these, 44 single enzymes and 10 enzyme pairs proved to be common to all 13 S. aureus strains, including many that had not been previously identified as being essential for growth by gene deletion experiments in S. aureus. We thus conclude that metabolic reconstruction and in silico analyses of multiple strains of the same bacterial species provide a novel approach for potential antibiotic target identification.
P. Wang, M. Gonzalez, C. A. Hidalgo, A.-L. Barabási
Understanding the spreading patterns of mobile phone viruses
Science 324, 1071-1076 (2009)
Read the abstract
We modeled the mobility of mobile phone users in order to study the fundamental spreading patterns that characterize a mobile virus outbreak. We find that although Bluetooth viruses can reach all susceptible handsets with time, they spread slowly because of human mobility, offering ample opportunities to deploy antiviral software. In contrast, viruses using multimedia messaging services could infect all users in hours, but currently a phase transition on the underlying call graph limits them to only a small fraction of the susceptible users. These results explain the lack of a major mobile virus breakout so far and predict that once a mobile operating system’s market share reaches the phase transition point, viruses will pose a serious threat to mobile communications.
C. A. Hidalgo, N. Blumm, A.-L. Barabási, N. A. Christakis
A dynamic network approach for the study of human phenotypes
PLoS Computational Biology 5:4, 1-11 (2009)
Read the abstract
The use of networks to integrate different genetic, proteomic, and metabolic datasets has been proposed as a viable path toward elucidating the origins of specific diseases. Here we introduce a new phenotypic database summarizing correlations obtained from the disease history of more than 30 million patients in a Phenotypic Disease Network (PDN). We present evidence that the structure of the PDN is relevant to the understanding of illness progression by showing that (1) patients develop diseases close in the network to those they already have; (2) the progression of disease along the links of the network is different for patients of different genders and ethnicities; (3) patients diagnosed with diseases which are more highly connected in the PDN tend to die sooner than those affected by less connected diseases; and (4) diseases that tend to be preceded by others in the PDN tend to be more connected than diseases that precede other illnesses, and are associated with higher degrees of mortality. Our findings show that disease progression can be represented and studied using network methods, offering the potential to enhance our understanding of the origin and evolution of human diseases. The dataset introduced here, released concurrently with this publication, represents the largest relational phenotypic resource publicly available to the research community.
J. Park, D. S. Lee, N. A. Christakis, A.-L. Barabási
The impact of cellular networks on disease comorbidity
Molecular Systems Biology 5:262, 1-7 (2009)
Read the abstract
The impact of disease-causing defects is often not limited to the products of a mutated gene but, thanks to interactions between the molecular components, may also affect other cellular functions, resulting in potential comorbidity effects. By combining information on cellular interactions, disease--gene associations, and population-level disease patterns extracted from Medicare data, we find statistically significant correlations between the underlying structure of cellular networks and disease comorbidity patterns in the human population. Our results indicate that such a combination of population-level data and cellular network information could help build novel hypotheses about disease mechanisms.
M. C. González, C. A. Hidalgo, A.-L. Barabási
Understanding individual human mobility patterns
Nature 453, 779-782 (2008)
Read the abstract
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.
J. Candia, M. C. Gonzalez, P. Wang, T. Schoenharl, G. Madey, A.-L. Barabási
Uncovering individual and collective human dynamics from mobile phone records
Journal of Physics A: Mathematical and Theoretical 41, 1-11 (2008)
Read the abstract
Novel aspects of human dynamics and social interactions are investigated by means of mobile phone data. Using extensive phone records resolved in both time and space, we study the mean collective behavior at large scales and focus on the occurrence of anomalous events. We discuss how these spatiotemporal anomalies can be described using standard percolation theory tools. We also investigate patterns of calling activity at the individual level and show that the interevent time of consecutive calls is heavy-tailed. This finding, which has implications for dynamics of spreading phenomena in social networks, agrees with results previously reported on other human activities.
C.A. Hidalgo, R. B. Klinger, A.-L. Barabási, R. Hausmann
The product space conditions the development of nations
Science 317, 482 (2007)
Read the abstract
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.
J. G. Oliveira, A.-L. Barabási
Correspondence patterns - mechanisms and models of human dynamics - Reply
Nature 441, E5-E6 (2006)
Read the abstract
Kentsis notes that the response time to an email or a letter depends on the semantic content of the correspondence, as well as the social context in which the communication arises1. We would add that it also depends on deadlines, the time dependence of priorities and the dropping of past-deadline messages2, making human response dynamics sufficiently complicated that no simple model could fully account for it3–6. However, the advantage of the proposed modelling framework is that most of these effects can be incorporated into it, and their impact on the queuing process can be systematically evaluated. Addressing some of these additional mechanisms, including those suggested by Kentsis, requires information that is beyond reach for most researchers at this point.
S. Wuchty, A.-L. Barabási, M.T. Ferdig
Stable evolutionary signal in a Yeast protein interaction network
BMC Evolutionary Biology 60, 8 (2006)
Read the abstract
Background: The recently emerged protein interaction network paradigm can provide novel and important insights into the innerworkings of a cell. Yet, the heavy burden of both false positive and false negative protein-protein interaction data casts doubt on the broader usefulness of these interaction sets. Approaches focusing on one-protein-at-a-time have been powerfully employed to demonstrate the high degree of conservation of proteins participating in numerous interactions; here, we expand his 'node' focused paradigm to investigate the relative persistence of 'link' based evolutionary signals in a protein interaction network of S. cerevisiae and point out the value of this relatively untapped source of information. Results: The trend for highly connected proteins to be preferably conserved in evolution is stable, even in the context of tremendous noise in the underlying protein interactions as well as in the assignment of orthology among five higher eukaryotes. We find that local clustering around interactions correlates with preferred evolutionary conservation of the participating proteins; furthermore the correlation between high local clustering and evolutionary conservation is accompanied by a stable elevated degree of coexpression of the interacting proteins. We use this conserved interaction data, combined with P. falciparum /Yeast orthologs, as proof-of-principle that high-order network topology can be used comparatively to deduce local network structure in nonmodel organisms. Conclusion: High local clustering is a criterion for the reliability of an interaction and coincides with preferred evolutionary conservation and significant coexpression. These strong and stable correlations indicate that evolutionary units go beyond a single protein to include the interactions among them. In particular, the stability of these signals in the face of extreme noise suggests that empirical protein interaction data can be integrated with orthologous clustering around these protein interactions to reliably infer local network structures in non-model organisms.
A.-L. Barabási
Taming complexity
Nature Physics 1, 68-70 (2005)
Read the abstract
The science of networks is experiencing a boom. But despite the necessary multidisciplinary approach to tackle the theory of complexity, scientists remain largely compartmentalized in their separate disciplines. Can they find a common voice?
P.J. Macdonald, E. Almaas, A.-L. Barabási
Minimum spanning trees of weighted scale-free networks
Europhysics Letters 72, 308-314 (2005)
Read the abstract
A complete characterization of real networks requires us to understand the consequences of the uneven interaction strengths between a system’s components. Here we use minimum spanning trees (MSTs) to explore the effect of correlations between link weights and network topology on scale-free networks. Solely by changing the nature of the correlations between weights and network topology, the structure of the MSTs can change from scale-free to exponential. Additionally, for some choices of weight correlations, the efficiency of the MSTs increases with increasing network size, a result with potential implications for the design and scalability of communication networks.
M. A. Makeev, I. Derenyi, A.-L. Barabási
Emergence of large-scale vorticity during diffusion in a random potential under an alternating bias
Physical Review E 71, 026112 (2005)
Read the abstract
Conventional wisdom indicates that the presence of an alternating driving force will not change the longterm behavior of a Brownian particle moving in a random potential. Although this is true in one dimension, here we offer direct evidence that the inevitable local symmetry breaking present in a two-dimensional random potential leads to the emergence of a local ratchet effect that generates large-scale vorticity patterns consisting of steady-state net diffusive currents. For small fields the spatial correlation function of the current follows a logarithmic distance dependence, while for large external fields both the vorticity and the correlations gradually disappear. We uncover the scaling laws characterizing this unique pattern formation process, and discuss their potential relevance to real systems.
A. Vazquez, J. G. Oliveira, A.-L. Barabási
Inhomogeneous evolution of subgraphs and cycles in complex networks
Physical Review E 71, 025103 (2005)
Read the abstract
Subgraphs and cycles are often used to characterize the local properties of complex networks. Here we show that the subgraph structure of real networks is highly time dependent: as the network grows, the density of some subgraphs remains unchanged, while the density of others increase at a rate that is determined by the network’s degree distribution and clustering properties. This inhomogeneous evolution process, supported by direct measurements on several real networks, leads to systematic shifts in the overall subgraph spectrum and to an inevitable overrepresentation of some subgraphs and cycles.
Z. Eisler, J. Kertesz, S.-H. Yook, A.-L. Barabási
Multiscaling and non-universality in fluctuations of driven complex systems
Europhysics Letters 69, 664-670 (2005)
Read the abstract
For many externally driven complex systems neither the noisy driving force, nor the internal dynamics are a priori known. Here we focus on systems for which the timedependent activity of a large number of components can be monitored, allowing us to separate each signal into a component attributed to the external driving force and one to the internal dynamics. We propose a formalism to capture the potential multiscaling in the fluctuations and apply it to the high-frequency trading records of the New York Stock Exchange. We find that on the time scale of minutes the dynamics is governed by internal processes, while on a daily or longer scale the external factors dominate. This transition from internal to external dynamics induces systematic changes in the scaling exponents, offering direct evidence of non-universality in the system.
A. Vazquez, R. Dobrin, D. Sergi, J.-P. Eckmann, Z. N. Oltvai, A.-L. Barabási
The topological relationship between the large-scale attributes and local interactions patterns of complex networks
Proceedings of the National Academy of Sciences 101, 17940-17945 (2004)
Read the abstract
Recent evidence indicates that the abundance of recurring elementary interaction patterns in complex networks, often called subgraphs or motifs, carry significant information about their function and overall organization. Yet, the underlying reasons for the variable quantity of different subgraph types, their propensity to form clusters, and their relationship with the networks’ global organization remain poorly understood. Here we show that a network’s large-scale topological organization and its local subgraph structure mutually define and predict each other, as confirmed by direct measurements in five well studied cellular networks. We also demonstrate the inherent existence of two distinct classes of subgraphs, and show that, in contrast to the low-density type II subgraphs, the highly abundant type I subgraphs cannot exist in isolation but must naturally aggregate into subgraph clusters. The identified topological framework may have important implications for our understanding of the origin and function of subgraphs in all complex networks.
G. Palla, I. Farkas, I. Derenyi, A.-L. Barabási, T. Vicsek
Reverse engineering of linking preferences from network restructuring
Physical Review E 70, 046115 (2004)
Read the abstract
We provide a method to deduce the preferences governing the restructuring dynamics of a network from the observed rewiring of the edges. Our approach is applicable for systems in which the preferences can be formulated in terms of a single-vertex energy function with fskd being the contribution of a node of degree k to the total energy, and the dynamics obeys the detailed balance. The method is first tested by Monte Carlo simulations of restructuring graphs with known energies; then it is used to study variations of real network systems ranging from the coauthorship network of scientific publications to the asset graphs of the New York Stock Exchange. The empirical energies obtained from the restructuring can be described by a universal function fskd,−k ln k, which is consistent with and justifies the validity of the preferential attachment rule proposed for growing networks.
M.A. Makeev, A.-L. Barabási
Effect of surface morphology on the sputtering yields: II. Ion sputtering from rippled surfaces
Nuclear Instruments & Methods In Physics Research Section B 222, 335-354 (2004)
Read the abstract
Off-normal ion bombardment of solid targets with energetic particles often leads to development of periodically modulated structures on the surfaces of eroded materials. Ion-induced surface roughening, in its turn, causes sputtering yield changes. We report on a comprehensive theoretical study of the effect of rippled surface morphology on the sputtering yields. The yield is computed as a function of the parameters characterizing the surface morphology and the incident ion beam, using the Sigmund’s theory of ion sputtering. We find that the surface morphology development may cause substantial variations in the sputter yields, depending on a complex interplay between the parameters characterizing the ripple structure and the incident ion beam. For certain realizations of the ripple structure, the surface morphology is found to induce enhanced, relative to the flat surface value, sputtering yields. On the other hand, there exist regimes in which the sputtering yield is suppressed by the surface roughness below the flat surface result. We confront the obtained theoretical results with available experimental data and find that our model provides an excellent qualitative and, in some cases, quantitative agreement with the results of experimental studies.
M. A. Makeev, A.-L. Barabási
Effect of surface morphology on the sputtering yields: I. Ion sputtering from self-affine surfaces
Nuclear Instruments & Methods In Physics Research Section B 222, 316-334 (2004)
Read the abstract
As extensive experimental studies have shown, under certain conditions, ion bombardment of solid targets induces a random (self-affine) morphology on the ion-eroded surfaces. The rough morphology development is known to cause substantial variations in the sputtering yields. In this article, we present a theoretical model describing the sputter yields from random, self-affine surfaces subject to energetic ion bombardment. We employ the Sigmund’s theory of ion sputtering, modified for the case of self-affine surfaces, to compute the sputter yields. We find that the changes in the sputtering yield, associated with the non-planar surface morphology, are strongly dependent on the parameters characterizing the surface roughness (such as the saturation width and the correlation length) and the incident ion beam (such as the incident ion energy and the deposited energy widths). It is shown that, for certain ranges of the parameters variations, surface roughness leads to substantial enhancements in the yield, with magnitude of the effect being more than 100%, as compared to the flat surface value. Furthermore, we find that, depending on the interplay between these parameters, the surface roughness can both enhance and suppress the sputter yields.
A.-L. Barabási, R. Albert
Emergence of scaling in random networks
Science 286, 509–512 (1999)
Read the abstract
Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
M. A. de Menezes, A.-L. Barabási
Fluctuations in network dynamics
Physical Review Letters 92, 28701 (2004)
Read the abstract
Most complex networks serve as conduits for various dynamical processes, ranging from mass transfer by chemical reactions in the cell to packet transfer on the Internet.We collected data on the time dependent activity of five natural and technological networks, finding that for each the coupling of the flux fluctuations with the total flux on individual nodes obeys a unique scaling law. We show that the observed scaling can explain the competition between the system’s internal collective dynamics and changes in the external environment, allowing us to predict the relevant scaling exponents.
I. Yang, H. Jeong, B. Kahng, A.-L. Barabási
Emerging behavior in electronic bidding
Physical Review E 68, 016102 (2003)
Read the abstract
We characterize the statistical properties of a large number of agents on two major online auction sites. The measurements indicate that the total number of bids placed in a single category and the number of distinct auctions frequented by a given agent follow power-law distributions, implying that a few agents are responsible for a significant fraction of the total bidding activity on the online market. We find that these agents exert an unproportional influence on the final price of the auctioned items. This domination of online auctions by an unusually active minority may be a generic feature of all online mercantile processes.
M. Makeev, R. Cuerno, A.-L. Barabási
Morphology of ion-sputtered surfaces
Nuclear Instruments & Methods In Physics Research Section B 197, 185-227 (2002)
Read the abstract
We derive a stochastic nonlinear continuum equation to describe the morphological evolution of amorphous surfaces eroded by ion bombardment. Starting from Sigmunds theory of sputter erosion, we calculate the coefficients appearing in the continuum equation in terms of the physical parameters characterizing the sputtering process. We analyze the morphological features predicted by the continuum theory, comparing them with the experimentally reported morphologies. We show that for short time scales, where the effect of nonlinear terms is negligible, the continuum theory predicts ripple formation. We demonstrate that in addition to relaxation by thermal surface diffusion, the sputtering process can also contribute to the smoothing mechanisms shaping the surface morphology. We explicitly calculate an effective surface diffusion constant characterizing this smoothing effect and show that it is responsible for the low temperature ripple formation observed in various experiments. At long time scales the nonlinear terms dominate the evolution of the surface morphology. The nonlinear terms lead to the stabilization of the ripple wavelength and we show that, depending on the experimental parameters, such as angle of incidence and ion energy, different morphologies can be observed: asymptotically, sputter eroded surfaces could undergo kinetic roughening, or can display novel ordered structures with rotated ripples. Finally, we discuss in detail the existing experimental support for the proposed theory and uncover novel features of the surface morphology and evolution, that could be directly tested experimentally.
J. Kim, B. Kahng, A.-L. Barabási
Nanoscale wire formation on sputter eroded surface
Applied Physics Letters 81, 3654-3656 (2002)
Read the abstract
Rotated ripple structures (RRS) on sputter-eroded surfaces are potential candidates for nanoscale wire fabrication. We show that the RRS can form when the width of the collision cascade in the longitudinal direction is larger than that in the transverse direction and the incident angle of ion beam is chosen in a specific window. By calculating the structure factor for the RRS, we find that they are more regular and their amplitude is more enhanced compared to the much studied ripple structure forming in the linear regime of sputter erosion.
I. Farkas, I. Derenyi, H. Jeong, Z. Neda, Z. N. Oltvai, E. Ravasz, A. Schubert, A.-L. Barabási, T. Vicsek
Networks in life: scaling properties and eigenvalue spectra
Physica A 314, 25-34 (2002)
Read the abstract
We analyze growing networks ranging from collaboration graphs of scientists to the network ofsimilarities de9ned among the various transcriptional pro9les ofliving cells. For the explicit demonstration ofthe scale-free nature and hierarchical organization ofthese graphs, a deterministic construction is also used. We demonstrate the use ofdetermining the eigenvalue spectra of sparse random graph models for the categorization of small measured networks.
R. Albert, A.-L. Barabási
Statistical mechanics of complex networks
Reviews of Modern Physics 74, 47-97 (2002)
Read the abstract
Complex networks describe a wide range of systems in nature and society. Frequently cited examples include the cell, a network of chemicals linked by chemical reactions, and the Internet, a network of routers and computers connected by physical links. While traditionally these systems have been modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks are governed by robust organizing principles. This article reviews the recent advances in the field of complex networks, focusing on the statistical mechanics of network topology and dynamics. After reviewing the empirical data that motivated the recent interest in networks, the authors discuss the main models and analytical tools, covering random graphs, small-world and scale-free networks, the emerging theory of evolving networks, and the interplay between topology and the network’s robustness against failures and attacks.
N. Schwartz, R. Cohen, D. ben-Avraham, A.-L. Barabási, S. Havlin
Percolation in directed scale-free networks
Physical Review E 66, 015104 (2002)
Read the abstract
Many complex networks in nature have directed links, a property that affects the network’s navigability and large-scale topology. Here we study the percolation properties of such directed scale-free networks with correlated in and out degree distributions. We derive a phase diagram that indicates the existence of three regimes, determined by the values of the degree exponents. In the first regime we regain the known directed percolation mean field exponents. In contrast, the second and third regimes are characterized by anomalous exponents, which we calculate analytically. In the third regime the network is resilient to random dilution, i.e., the percolation threshold is pe-->1.
Z. Dezso, A.-L. Barabási
Halting viruses in scale-free networks
Physical Review E 65, 055103 (2002)
Read the abstract
The vanishing epidemic threshold for viruses spreading on scale-free networks indicate that traditional methods, aiming to decrease a virus’ spreading rate cannot succeed in eradicating an epidemic. We demonstrate that policies that discriminate between the nodes, curing mostly the highly connected nodes, can restore a finite epidemic threshold and potentially eradicate a virus. We find that the more biased a policy is towards the hubs, the more chance it has to bring the epidemic threshold above the virus’ spreading rate. Furthermore, such biased policies are more cost effective, requiring less cures to eradicate the virus.
H. Jeong, B. Kahng, S. Lee, C.Y. Kwak, A.-L. Barabási, J.K. Furdyna
Monte Carlo simulation of sinusoidally modulated superlattice growth
Physical Review E 65, 031602 (2002)
Read the abstract
The fabrication of ZnSe/ZnTe superlattices grown by the process of rotating the substrate in the presence of an inhomogeneous flux distribution instead of the successively closing and opening of source shutters is studied via Monte Carlo simulations. It is found that the concentration of each compound is sinusoidally modulated along the growth direction, caused by the uneven arrival of Se and Te atoms at a given point of the sample, and by the variation of the Te/Se ratio at that point due to the rotation of the substrate. In this way we obtain a ZnSe12xTex alloy in which the composition x varies sinusoidally along the growth direction. The period of the modulation is directly controlled by the rate of the substrate rotation. The amplitude of the compositional modulation is monotonic for small angular velocities of the substrate rotation, but is itself modulated for large angular velocities. The average amplitude of the modulation pattern decreases as the angular velocity of substrate rotation increases and the measurement position approaches the center of rotation. The simulation results are in good agreement with previously published experimental measurements on superlattices fabricated in this manner.
I. Albert, J.G. Sample, A.J. Morss, S. Rajagopalan, A.-L. Barabási, P. Schiffer
Granular drag on a discrete object: shape effects on jamming
Physical Review E 64, 061303 (2001)
Read the abstract
We study the drag force on discrete objects with circular cross section moving slowly through a spherical granular medium. Variations in the geometry of the dragged object change the drag force only by a small fraction relative to shape effects in fluid drag. The drag force depends quadratically on the object’s diameter as expected. We do observe, however, a deviation above the expected linear depth dependence, and the magnitude of the deviation is apparently controlled by geometrical factors.
B. Kahng, I. Albert, P. Schiffer, A.-L. Barabási
Modeling relaxation and jamming in granular media
Physical Review E 64, 051303 (2001)
Read the abstract
We introduce a stochastic microscopic model to investigate the jamming and reorganization of grains induced by an object moving through a granular medium. The model reproduces the experimentally observed periodic sawtooth fluctuations in the jamming force and predicts the period and the power spectrum in terms of the controllable physical parameters. It also predicts that the avalanche sizes, defined as the number of displaced grains during a single advance of the object, follow a power law P(s);s2t , where the exponent is independent of the physical parameters.
A.-L. Barabási, E. Ravasz, T. Vicsek
Deterministic scale-free networks
Physica A 299, 559–564 (2001)
Read the abstract
Scale-free networks are abundant in nature and society, describing such diverse systems as the world wide web, the web of human sexual contacts, or the chemical network of a cell. All models used to generate a scale-free topology are stochastic, that is they create networks in which the nodes appear to be randomly connected to each other. Here we propose a simple model that generates scale-free networks in a deterministic fashion. We solve exactly the model, showing that the tail of the degree distribution follows a power law.
I. Albert, P. Tegzes, R. Albert, J. G. Sample, A.-L. Barabási, T. Vicsek, B. Kahng, P. Schiffer
Stick-slip fluctuations in granular drag
Physical Review E 64, 031307 (2001)
Read the abstract
We study fluctuations in the drag force experienced by an object moving through a granular medium. The successive formation and collapse of jammed states give a stick-slip nature to the fluctuations which are periodic at small depths but become ‘‘stepped’’ at large depths, a transition that we interpret as a consequence of the long-range nature of the force chains and the finite size of our experiment. Another important finding is that the mean force and the fluctuations appear to be independent of the properties of the contact surface between the grains and the dragged object. These results imply that the drag force originates in the bulk properties of the granular sample.
B. Kahng, H. Jeong, A.-L. Barabási
Nanoscale structure formation on sputter eroded surface
Journal of the Korean Physical Society 39, 421-424 (2001)
Read the abstract
We investigate the morphological features of sputter eroded surfaces, demonstrating that while at short times ripple formation is described by the linear theory, after a characteristic time, the nonlinear terms determine the surface morphology, by monitoring the surface width and the erosion velocity. Furthermore, we show that sputtering under normal incidence leads to the formation of spatially ordered uniform nanoscale islands or holes. We nd that while the size of these nanostructures is independent of flux and temperature, it can be controlled by ion beam energy.
A.-L. Barabási, V. W. Freeh, H. Jeong, J. Brockman
Parasitic computing
Nature 412, 894-897 (2001)
Read the abstract
Reliable communication on the Internet is guaranteed by a standard set of protocols, used by all computers. Here we show that these protocols can be exploited to compute with the communication infrastructure, transforming the Internet into a distributed computer in which servers unwittingly perform computation on behalf of a remote node. In this model, which we call `parasitic computing, one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication. Consequently, the target computers are unaware that they have performed computation for the bene®t of a commanding node. As experimental evidence of the principle of parasitic computing, we harness the power of several web servers across the globe, which known to them work together to solve an NP complete problem.
I. J. Farkas, I. Derenyi, A.-L. Barabási, T. Vicsek
Spectra of “real-world” graphs: beyond the semicircle law
Physical Review E Physical Review, 026704 (2001)
Read the abstract
Many natural and social systems develop complex networks that are usually modeled as random graphs. The eigenvalue spectrum of these graphs provides information about their structural properties. While the semicircle law is known to describe the spectral densities of uncorrelated random graphs, much less is known about the spectra of real-world graphs, describing such complex systems as the Internet, metabolic pathways, networks of power stations, scientific collaborations, or movie actors, which are inherently correlated and usually very sparse. An important limitation in addressing the spectra of these systems is that the numerical determination of the spectra for systems with more than a few thousand nodes is prohibitively time and memory consuming. Making use of recent advances in algorithms for spectral characterization, here we develop methods to determine the eigenvalues of networks comparable in size to real systems, obtaining several surprising results on the spectra of adjacency matrices corresponding to models of real-world graphs. We find that when the number of links grows as the number of nodes, the spectral density of uncorrelated random matrices does not converge to the semicircle law. Furthermore, the spectra of real-world graphs have specific features, depending on the details of the corresponding models. In particular, scale-free graphs develop a trianglelike spectral density with a power-law tail, while small-world graphs have a complex spectral density consisting of several sharp peaks. These and further results indicate that the spectra of correlated graphs represent a practical tool for graph classification and can provide useful insight into the relevant structural properties of real networks.
S. H. Yook, H. Jeong, A.-L. Barabási, Y. Tu
Weighted evolving networks
Physical Review Letters 86, 5835-5838 (2001)
Read the abstract
Many biological, ecological, and economic systems are best described by weighted networks, as the nodes interact with each other with varying strength. However, most evolving network models studied so far are binary, the link strength being either 0 or 1. In this paper we introduce and investigate the scaling properties of a class of models which assign weights to the links as the network evolves. The combined numerical and analytical approach indicates that asymptotically the total weight distribution converges to the scaling behavior of the connectivity distribution, but this convergence is hampered by strong logarithmic corrections.
G. Bianconi, A.-L. Barabási
Bose-Einstein condensation in complex networks
Physical Review Letters 86, 5632–5635 (2001)
Read the abstract
The evolution of many complex systems, including the World Wide Web, business, and citation networks, is encoded in the dynamic web describing the interactions between the system’s constituents. Despite their irreversible and nonequilibrium nature these networks follow Bose statistics and can undergo Bose-Einstein condensation. Addressing the dynamical properties of these nonequilibrium systems within the framework of equilibrium quantum gases predicts that the “first-mover-advantage,” “fit-get-rich,” and “winner-takes-all” phenomena observed in competitive systems are thermodynamically distinct phases of the underlying evolving networks.
G. Bianconi, A.-L. Barabási
Competition and multiscaling in evolving networks
Europhysics Letters 54, 436-442 (2001)
Read the abstract
The rate at which nodes in a network increase their connectivity depends on their fitness to compete for links. For example, in social networks some individuals acquire more social links than others, or on the www some webpages attract considerably more links than others. We find that this competition for links translates into multiscaling, i.e. a fitnessdependent dynamic exponent, allowing fitter nodes to overcome the more connected but less fit ones. Uncovering this fitter-gets-richer phenomenon can help us understand in quantitative terms the evolution of many competitive systems in nature and society.
R. Albert, H. Jeong, A.-L. Barabási
Error and attack tolerance of complex networks
Nature 406, 378–482 (2000)
Read the abstract
Here we demonstrate that error tolerance is not shared by all redundant systems: it is displayed only by a class of inhomogeneouslywired networks,called scale-free networks, which include theWorld-WideWeb, the Internet, social networks and cells. We find that such networks display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates.However, error tolerance comes at a high price in that these networks are extremely vulnerable to attacks (that is, to the selection and removal of a few nodes that play a vital role in maintaining the network’s connectivity). Such error tolerance and attack vulnerability are generic properties of communication networks.
B. Kahng, H. Jeong, A.-L. Barabási
Spatial ordering of stacked quantum dots
Applied Physics Letters 78, 805–807 (2001)
Read the abstract
We investigate the growth conditions necessary to form an ordered quantum dot crystal by capping spatially ordered quantum dots and growing a new layer of dots on top of the capping layer. Performing Monte Carlo simulations and developing analytic arguments based on the stress energy function, we demonstrate the existence of an optimal capping layer thickness, external flux, and temperature for the formation of quantum dot crystals.
B. Kahng, H. Jeong, A.-L. Barabási
Quantum dot and hole formation in sputter erosion
Applied Physics Letters 78, 805–807 (2001)
Read the abstract
Recently, it was experimentally demonstrated that sputtering under normal incidence leads to the formation of spatially ordered uniform nanoscale islands or holes. Here, we show that these nanostructures have inherently nonlinear origin, first appearing when the nonlinear terms start to dominate the surface dynamics. Depending on the sign of the nonlinear terms, determined by the shape of the collision cascade, the surface can develop regular islands or holes with identical dynamical features, and while the size of these nanostructures is independent of flux and temperature, it can be modified by tuning the ion energy.
R. Albert, H. Jeong, A.-L. Barabási
Diameter of the world wide web
Nature 401, 130-131 (1999)
Read the abstract
Despite its increasing role in communication, the World-Wide Web remains uncontrolled: any individual or institution can create a website with any number of documents and links. This unregulated growth leads to a huge and complex web, which becomes a large directed graph whose vertices are documents and whose edges are links (URLs) that point from one document to another. The topology of this graph determines the web’s connectivity and consequently how effectively we can locate information on it.
R. Albert, A.-L. Barabási
Dynamics of complex systems: scaling laws for the period of boolean networks
Physical Review Letters 84, 5660-5663 (2000)
Read the abstract
Boolean networks serve as models for complex systems, such as social or genetic networks, where each vertex, based on inputs received from selected vertices, makes its own decision about its state. Despite their simplicity, little is known about the dynamical properties of these systems. Here we propose a method to calculate the period of a finite Boolean system, by identifying the mechanisms determining its value. The proposed method can be applied to systems of arbitrary topology, and can serve as a roadmap for understanding the dynamics of large interacting systems in general.
Z. Neda, E. Ravasz, T. Vicsek, Y. Brechet, A.-L. Barabási
Physics of the rhythmic applause
Physical Review E 61, 6987-6992 (2000)
Read the abstract
We report on a series of measurements aimed to characterize the development and the dynamics of the rhythmic applause in concert halls. Our results demonstrate that while this process shares many characteristics of other systems that are known to synchronize, it also has features that are unexpected and unaccounted for in many other systems. In particular, we find that the mechanism lying at the heart of the synchronization process is the period doubling of the clapping rhythm. The characteristic interplay between synchronized and unsynchronized regimes during the applause is the result of a frustration in the system. All results are understandable in the framework of the Kuramoto model.
I. Albert, P. Tegzes, B. Kahng, R. Albert, J.G. Sample, M.A. Pfeifer, A.-L. Barabási, T. Vicsek, P. Schiffer
Jamming and fluctuations in granular drag
Physical Review Letters 84, 5122–5125 (2000)
Read the abstract
We investigate the dynamic evolution of jamming in granular media through fluctuations in the granular drag force. The successive collapse and formation of jammed states give a stick-slip nature to the fluctuations which is independent of the contact surface between the grains and the dragged object, thus implying that the stress-induced collapse is nucleated in the bulk of the granular sample. We also find that while the fluctuations are periodic at small depths, they become “stepped” at large depths, a transition which we interpret as a consequence of the long-range nature of the force chains.
A.-L. Barabási, R. Albert, H. Jeong, G. Bianconi
Power-law distribution of the world wide web
Science 287, 2115 (2000)
Read the abstract
Barabasi and Albert propose an improved version of the Erdos-Renyi theory of random networks to account for the scaling properties of a number of systems, including the link structure of the World Wide Web (WWW). The theory they present, however, is inconsistent with empirically observed properties of the Web link structure.
A.-L. Barabási
Thermodynamic and kinetic mechanisms in self-assembled quantum dot formation
Materials Science and Engineering B 67, 23–30 (1999)
Read the abstract
Heteroepitaxial growth of highly strained structures offers the possibility to fabricate islands with very narrow size distribution, coined self-assembling quantum dots (SAQD). In spite of the high experimental interest, the mechanism of SAQD formation is not well understood. We will show that equilibrium theories can successfully predict the island sizes and densities, the nature and the magnitude of the critical thickness needed to be deposited for SAQD formation, as well as the onset of ripening. Furthermore, the flux and temperature dependence of the SAQDs is described using kinetic Monte Carlo simulations.
P. Tegzes, R. Albert, M. Paskvan, A.-L. Barabási, T. Vicsek, P. Schiffer
Liquid-induced transitions in granular media
Physical Review E 60, 5823–5826 (1999)
Read the abstract
We investigate the effect of interstitial liquid on the physical properties of granular media by measuring the angle of repose as a function of the liquid content. The resultant adhesive forces lead to three distinct regimes in the observed behavior as the liquid content is increased: a granular regime in which the grains move individually, acorrelated regime in which the grains move in correlated clusters, and a plastic regime in which the grains flow coherently. We discuss these regimes in terms of two proposed theories describing the effects of liquid on the physical properties of granular media.
S. Park, B. Kahng, H. Jeong, A.-L. Barabási
Dynamics of ripple formation in sputter erosion: nonlinear phenomena
Physical Review Letters 83, 3486–3489 (1999)
Read the abstract
Many morphological features of sputter eroded surfaces are determined by the balance between ion-induced linear instability and surface diffusion. However, the impact of the nonlinear terms on the morphology is less understood. We demonstrate that, while at short times ripple formation is described by the linear theory, after a characteristic time the nonlinear terms determine the surface morphology by either destroying the ripples or generating a new rotated ripple structure. We show that the morphological transitions induced by the nonlinear effects can be detected by monitoring the surface width and the erosion velocity.
A.-L. Barabási, R. Albert, H. Jeong
Mean-field theory for scale-free random networks
Physica A 272, 173–187 (1999)
Read the abstract
Random networks with complex topology are common in Nature, describing systems as diverse as the world wide web or social and business networks. Recently, it has been demonstrated that most large networks for which topological information is available display scale-free features. Here we study the scaling properties of the recently introduced scale-free model, that can account for the observed power-law distribution of the connectivities. We develop a mean-feld method to predict the growth dynamics of the individual vertices, and use this to calculate analytically the connectivity distribution and the scaling exponents. The mean-feld method can be used to address the properties of two variants of the scale-free model, that do not display power-law scaling.
R. Albert, A.-L. Barabási
Topology of evolving networks: local events and universality
Physical Review Letters 85, 5234-5237 (2000)
Read the abstract
Networks grow and evolve by local events, such as the addition of new nodes and links, or rewiring of links from one node to another. We show that depending on the frequency of these processes two topologically different networks can emerge, the connectivity distribution following either a generalized power law or an exponential. We propose a continuum theory that predicts these two regimes as well as the scaling function and the exponents, in good agreement with numerical results. Finally, we use the obtained predictions to fit the connectivity distribution of the network describing the professional links between movie actors.
C.-S. Lee, B. Janko, I. Derenyi, A.-L. Barabási
Reducing vortex density in superconductors using the ratchet effect
Nature 400, 337-340 (1999)
Read the abstract
A serious obstacle impeding the application of low- and hightemperature superconductor devices is the presence of trapped magnetic flux1,2: flux lines or vortices can be induced by fields as small as the Earth’s magnetic field. Once present, vortices dissipate energy and generate internal noise, limiting the operation of numerous superconducting devices2,3. Methods used to overcome this difficulty include the pinning of vortices by the incorporation of impurities and defects4, the construction of flux ‘dams’5, slots and holes6, and magnetic shields2,3 which block the penetration of new flux lines in the bulk of the superconductor or reduce themagnetic field in the immediate vicinity of the superconducting device. The most desirable method would be to remove the vortices from the bulk of the superconductor, but there was hitherto no known phenomenon that could form the basis for such a process. Here we show that the application of an alternating current to a superconductor patterned with an asymmetric pinning potential can induce vortex motion whose direction is determined only by the asymmetry of the pattern. The mechanism responsible for this phenomenon is the so-called ‘ratchet effect’7–10, and its working principle applies to both low- and high-temperature superconductors. We demonstrate theoretically that, with an appropriate choice of pinning potential, the ratchet effect can be used to remove vortices from low-temperature superconductors in the parameter range required for various applications.
I. Daruka, A.-L. Barabási, S. J. Zhou, T. C. Germann, P. S. Lomdahl, A. R. Bishop
Molecular-dynamics investigation of the surface stress distribution in a GeSi quantum dot superlattice
Physical Review B 60, R2150-R2153 (1999)
Read the abstract
The surface stress distribution in an ordered quantum dot superlattice is investigated using classical molecular dynamics simulations. We find that the surface stress field induced by various numbers ~from 1 to 9! of Ge islands embedded in a Si~001! substrate is in good agreement with analytical expressions based on pointlike embedded force dipoles, explaining the tendency of layered arrays to form vertically aligned columns. The short-ranged nature of this stress field implies that only the uppermost layers affect the surface growth and that their influence decreases rapidly with layer depth.
S. Lee, I. Daruka, C.S. Kim, A.-L. Barabási, J.K. Furdyna, J.L. Merz
Lee et al. reply to Dynamics of ripening of self-assembled II-VI semiconductor quantum dots
Physical Review Letters 83, 240 (1999)
Read the abstract
Despite extensive investigation, little is still known about the physical mechanisms responsible for quantum dot (QD) formation in II-VI semiconductor systems, especially when compared to their group-IV or III-V counterparts. However, the distinct chemical and microscopic features characteristic of the various materials make these diverse systems rather exciting to study and compare. We therefore welcome the Comment by Kratzert et al. [1] that sheds new light on the CdSe island formation on ZnSe. The method used by them—in situ ultrahigh vacuum atomic force microscopy (AFM)—provides valuable information that was not accessible before: it allows one to probe the dynamics of QD formation without external influences (such as the influence of the atmosphere), and it offers minimum delay between QD formations and their characterization. Specifically, and in contrast with our findings [2], these new results do not manifest room temperature ripening of CdSe islands. These new observations, combined with a number of other results recently reported (see below), suggest the existence of three distinct island types:
A.-L. Barabási, R. Albert, P. Schiffer
The physics of sandcastles: maximum angle of stability in wet and dry granular media
Physica A 266, 366-371 (1999)
Read the abstract
We demonstrate that stability criteria can be used to calculate the maximum angle of stability, m, of a granular medium composed of spherical particles in three dimensions and circular discs in two dimensions. We apply the results to wet granular material by calculating the dependence of m on the liquid content of the material. The results are in good agreement with our experimental data.
I. Daruka, J. Tersoff, A.-L. Barabási
Shape transition in growth of strained islands
Physical Review Letters 82, 2753–2756 (1999)
Read the abstract
Strained islands formed in heteroepitaxy sometimes change shape during growth. Here we show that there is typically a first-order shape transition with island size, with the discontinuous introduction of steeper facets at the island edge. We present a phase diagram for island shape as a function of volume and surface energy, showing how surface energy controls the sequence of island shapes with increasing volume. The discontinuous chemical potential at the shape transition drastically affects island coarsening and size distributions.
R. Albert, M.A. Pfeifer, P. Schiffer, A.-L. Barabási
Slow drag in a granular medium
Physical Review Letters 82, 205–208 (1999)
Read the abstract
We have studied the drag force acting on an object moving with low velocity through a granular medium. Although the drag force is a dynamic quantity, its behavior in this regime is dominated by the inhomogeneous distribution of stress in static granular media. We find experimentally that the drag force on a vertical cylinder is linearly dependent on the cylinder diameter, quadratically dependent on the depth of insertion, and independent of velocity. An accompanying analytical calculation based on the static distribution of forces arrives at the same result, demonstrating that the local theory of stress propagation in static granular media can be used to predict this bulk dynamic property.
A. Czirok, A.-L. Barabási, T. Vicsek
Collective motion of self-propelled particles: kinetic phase transition in one dimension
Physical Review Letters 82, 209–212 (1999)
Read the abstract
We demonstrate that a system of self-propelled particles exhibits spontaneous symmetry breaking and self-organization in one dimension, in contrast with previous analytical predictions. To explain this surprising result we derive a new continuum theory that can account for the development of the symmetry broken state and belongs to the same universality class as the discrete self-propelled particle model.
C. Lee, A.-L. Barabási
Spatial ordering of islands grown on patterned surfaces
Applied Physics Letters 73, 2651-2653 (1998)
Read the abstract
We demonstrate that growth on a sample patterned with an ordered defect array can lead to islands with rather narrow size distribution. However, improvement in the size distribution is achieved only if the growth conditions ~flux and temperature! have optimal values, determined by the patterning length scale. Since the scanning tunelling and the atomic force microscopes are capable of inducing surface perturbations that act as potential preferential nucleation sites, our work demonstrates that nanoscale surface patterning can improve the ordering of platelets and self-assembled quantum dots.
S. Lee, I. Daruka, C.S. Kim, A.-L. Barabási, J.L. Merz, J.K. Furdyna
Dynamics of ripening of self-assembled II-VI semiconductor quantum dots
Physical Review Letters 81, 3479-3482 (1998)
Read the abstract
We report the systematic investigation of ripening of CdSe self-assembled quantum dots (QDs) on ZnSe. We investigate the size and density of the QDs as a function of time after deposition of CdSe has stopped. The dynamics of the ripening process is interpreted in terms of the theory of Ostwald ripening. Furthermore, the experimental results allow us to identify the growth mode of the QD formation process.
R. Albert, A.-L. Barabási, N Carle, A. Dougherty
Driven interfaces in disordered media: determination of universality classes from experimental data
Physical Review Letters 81, 2926-2929 (1998)
Read the abstract
While there have been important theoretical advances in understanding the universality classes of interfaces moving in porous media, the developed tools cannot be directly applied to experiments. Here we introduce a method that can distinguish the isotropic and directed percolation universality classes from snapshots of the interface profile. We test the method on discrete models whose universality class is well known, and use it to identify the universality class of interfaces obtained in experiments on fluid flow in porous media.
M. A. Makeev, A.-L. Barabási
Effect of surface roughness on the secondary ion yield in ion sputtering
Applied Physics Letters 73, 1445–1447 (1998)
Read the abstract
There is extensive experimental evidence that, at low temperatures, surface erosion by ion bombardment roughens the sputtered substrate, leading to a self-affine surface. These changes in the surface morphology also modify the secondary ion yield. Here, we calculate analytically the secondary ion yield in terms of parameters characterizing the sputtering process and the interface roughness.
I. Daruka, A.-L. Barabási
Equilibrium phase diagrams for dislocation free self-assembled quantum dots
Applied Physics Letters 72, 2102–2104 (1998)
Read the abstract
The equilibrium theory of self-assembled quantum dot ~SAQD! formation can account for many of the experimentally observed growth modes. Here, we show that despite the large number of material constants entering the free energy of strained islands, there are only four topologically different phase diagrams describing the SAQD formation process. We derive each of these phase diagrams and discuss the physical properties of the predicted growth modes.
M. A. Makeev, A.-L. Barabási
Secondary ion yield changes on rippled interfaces
Applied Physics Letters 72, 906–908 (1998)
Read the abstract
Sputter erosion often leads to the development of surface ripples. Here we investigate the effect of the ripples on the secondary ion yield, by calculating the yield as a function of the microscopic parameters characterizing the ion cascade ~such as penetration depth, widths of the deposited energy distribution! and the ripples ~ripple amplitude, wavelength!. We find that ripples can trongly enhance the yield, with the magnitude of the effect depending on the interplay between the ion and ripple characteristics. Furthermore, we compare our predictions with existing experimental results.
I. Derenyi, C.-S. Lee, A.-L. Barabási
Ratchet effect in surface electromigration: smoothing surfaces by an ac field
Physical Review Letters 80, 1473–1476 (1998)
Read the abstract
We demonstrate that for surfaces that have a nonzero Schwoebel barrier the application of an ac field parallel to the surface induces a net electromigration current that points in the descending step direction. The magnitude of the current is calculated analytically and compared with Monte Carlo simulations. Since a downhill current smoothes the surface, our results imply that the application of ac fields can aid the smoothing process during annealing and can slow or eliminate the Schwoebel-barrier-induced mound formation during growth.
R. Albert, I. Albert, D. Hornbaker, P. Schiffer, A.-L. Barabási
Maximum angle of stability in wet and dry spherical granular media
Physical Review E 56, R6271–R6274 (1997)
Read the abstract
We demonstrate that stability criteria can be used to calculate the maximum angle of stability u m of a granular medium composed of spherical particles in three dimensions and circular disks in two dimensions. The predicted angles are in good agreement with the experimental results. Furthermore, we determine the dependence of u m on cohesive forces, applying the results to wet granular material by calculating the dependence of u m on the liquid content of the material. We have also studied wet granular media experimentally and find good agreement between the theory and our experimental results.
M. A. Makeev, A.-L. Barabási
Ion-induced surface diffusion in ion sputtering
Applied Physics Letters 71, 2800–2802 (1997)
Read the abstract
Ion bombardment is known to enhance surface diffusion and affect the surface morphology. Here we demonstrate that preferential erosion during ion sputtering can lead to a physical phenomenon reminiscent of surface diffusion, what we call effective surface diffusion ~ESD!, that does not imply mass transport along the surface and is independent of the temperature. We calculate the ion-induced ESD constant and its dependence on the ion energy, flux and angle of incidence, showing that sputtering can both enhance and suppress surface diffusion. The influence of ion-induced ESD on ripple formation and roughening of ion-sputtered surfaces is discussed and summarized in a morphological phase diagram.
I. Daruka, A.-L. Barabási
Dislocation free island formation in heteroepitaxial growth: a study at equilibrium
Physical Review Letters 79, 3708–3711 (1997)
Read the abstract
We investigate the equilibrium properties of strained heteroepitaxial systems, incorporating the formation and the growth of a wetting film, dislocation-free island formation, and ripening. The derived phase diagram provides a detailed characterization of the possible growth modes in terms of the island density, equilibrium island size, and wetting layer thickness. Comparing our predictions with experimental results we discuss the growth conditions that can lead to stable islands as well as ripening.
D. J. Hornbaker, R. Albert, I. Albert, A.-L. Barabási, P. Schiffer
What keeps sandcastles standing?
Nature 387, 765 (1997)
Read the abstract
Any child playing on the beach knows that the physical properties of wet and dry sand are very different. Wet sand can be used to build sharp-featured sandcastles that would be unstable in dry sand. We have now quantified the effect of adding small quantities of liquid to a granular medium. Nanometre-scale layers of liquid on millimetre-scale grains dramatically increase the repose angle (the steepest stable slope that the substance can form) and allow the development of long-range correlations, or clumps.
A.-L. Barabási
Self-assembled island formation in heteroepitaxial growth
Applied Physics Letters 70, 2565-2567 (1997)
Read the abstract
We investigate island formation during heteroepitaxial growth using an atomistic model that incorporates deposition, activated diffusion, and stress relaxation. For high misfit the system naturally evolves into a state characterized by a narrow island size distribution. The simulations indicate the existence of a strain assisted kinetic mechanism responsible for the self-assembling process, involving enhanced detachment of atoms from the edge of large islands and biased adatom diffusion.
I. Daruka, A.-L. Barabási
Island formation and critical thickness in heteroepitaxy
Physical Review Letters 78, 3027 (1997)
Read the abstract
In a recent Letter Chen and Washburn [1] proposed a mechanism for island nucleation in large-mismatch heteroepitaxy. The predicted coverage sQd dependence of the 3D island density ri sQd reproduces the fast increase in the island density near the critical coverage Qc ø 1.6 ML [2]. Here we show that the critical coverage predicted by Ref. [1] depends strongly on the growth rate, thus contradicting, among others, the experimental results of Refs. [2,3].
A.-L. Barabási
Self-organized superlattice formation in II-VI and III-V semiconductors
Applied Physics Letters 70, 764–767 (1997)
Read the abstract
There is extensive recent experimental evidence of spontaneous superlattice ~SL! formation in various II–VI and III–V semiconductors. Here we propose an atomistic mechanism responsible for SL formation, and derive a relation predicting the temperature, flux, and miscut dependence of the SL layer thickness. Moreover, the model explains the existence of a critical miscut angle below which no SL is formed, in agreement with results on ZnSeTe, and predicts the formation of a platelet structure for deposition onto high symmetry surfaces, similar to that observed in InAsSb.
A.-L. Barabási, E. Kaxiras
Dynamic scaling in conserved systems with coupled fields: application to surfactant-mediated growth
Europhysics Letters 36, 129-134 (1996)
Read the abstract
We present an analytical study of the interaction of two nonequilibrium conservative fields. Due to the conservative character of the relaxation mechanism, the scaling exponents can be obtained exactly using dynamic renormalization group. We apply our results to surfactant-mediated growth of semiconductors. We find that the coupling between the surfactant thickness and the interface height cannot account for the experimentally observed layered growth, implying that reduced diffusion of the embedded atoms is a key mechanism in surfactant-mediated growth.
P. Jensen, A.-L. Barabási, H. Larralde, S. Havlin, H.E. Stanley
A fractal model for the first stages of thin film growth
Fractals 4, 321–329 (1996)
Read the abstract
In this paper, we briefly review a model that describes the diffusion-controlled aggregation exhibited by particles as they are deposited on a surface. This model allows us to understand many experiments of thin film deposition. In the Sec. 1, we describe the model, which incorporates deposition, particle and cluster diffusion, and aggregation. In Sec. 2, we study the dynamical evolution of the model. Finally, we analyze the effects of small cluster mobility and show that the introduction of cluster diffusion dramatically affects the dynamics of film growth. Some of these effects can be tested experimaentally.
S. V. Buldyrev, L.A.N. Amaral, A.-L. Barabási, S.T. Harrington, S. Havlin, R. Sadr-Lahijani, H.E. Stanley
Avalanches in the directed percolation depinning and self-organized depinning models of interface roughening
Fractals 4, 307–319 (1996)
Read the abstract
We review the recently introduced Directed Percolation Depinning (DPD) and Self-Organized Depinning (SOD) models for interface roughening with quenched disorder. The difference in the dynamics of the invasion process in these two models are discussed and different avalanche definitions are presented. The scaling properties of the avalanche size distribution and the properties of active cells are discussed.
A.-L. Barabási
Roughening of growing surfaces: kinetic models and continuum theories
Computational Materials Science 6, 127-134 (1996)
Read the abstract
The use of scaling concepts in understanding growth by molecular beam epitaxy (MBE) is increasingly important these days. Here we present a critical discussion on the advantages and disadvantages of kinetic theories and continuum models, two main methods frequently used to study the roughening and scaling of surfaces grown by MBE. Finally, some open problems faced by these approaches are also discussed.
P. Molinas-Mata, M.A. Munoz, D.O. Martinez, A.-L. Barabási
Ballistic random walker
Physical Review E 54, 968–971 (1996)
Read the abstract
We introduce and investigate the scaling properties of a random walker that moves allistically on a two-dimensional square lattice. The walker is scattered ~changes direction randomly! every time it reaches a previously unvisited site, and follows ballistic trajectories between two scattering events. The asymptotic properties of the density of unvisited sites and the diffusion exponent can be calculated using a mean-field theory. The obtained predictions are in good agreement with the results of extensive numerical simulations. In particular, we show that this random walk is subdiffusive.
H. A. Makse, A.-L. Barabási, H.E. Stanley
Elastic string in a random medium
Physical Review E 53, 6573–6576 (1996)
Read the abstract
We consider a one-dimensional elastic string as a set of massless beads interacting through springs characterized by anisotropic elastic constants. The string, driven by an external force, moves in a medium with quenched disorder. We find that longitudinal fluctuations lead to nonlinear behavior in the equation of motion that is kinematically generated by the motion of the string. The strength of the nonlinear effects depends on the anisotropy of the medium and the distance from the depinning transition. On the other hand, the consideration of restricted solid-on-solid conditions imposed on the string leads to a nonlinear term with a diverging coefficient at the depinning transition.
A.-L. Barabási
Invasion percolation and global optimization
Physical Review Letters 76, 3750–3753 (1996)
Read the abstract
Invasion bond percolation (IBP) is mapped exactly into Prim’s algorithm for finding the shortest spanning tree of a weighted random graph. Exploring this mapping, which is valid for arbitrary dimensions and lattices, we introduce a new IBP model that belongs to the same universality class as IBP and generates the minimal energy tree spanning the IBP cluster.
A.-L. Barabási, G. Grinstein, M.A. Munoz
Directed surfaces in disordered media
Physical Review Letters 76, 1481–1484 (1996)
L.A.N. Amaral, A.-L. Barabási, H.A. Makse, H.E. Stanley
Scaling properties of driven interfaces in disordered media
Physical Review E 52, 4087–5005 (1995)
R. Cuerno, A.-L. Barabási
Dynamic scaling of ion-sputtered surfaces
Physical Review Letters 74, 4746–4749 (1995)
Read the abstract
We derive a stochastic nonlinear equation to describe the evolution and scaling properties of surfaces eroded by ion bombardment. The coefficients appearing in the equation can be calculated explicitly in terms of the physical parameters characterizing the sputtering process. We find that transitions may take place between various scaling behaviors when experimental parameters, such as the angle of incidence of the incoming ions or their average penetration depth, are varied.
L.A.N. Amaral, A.-L. Barabási, S.V. Buldyrev, S.T. Harrington, S. Havlin, R. Sadr-Lahijani, H.E. Stanley
Avalanches and the directed percolation depinning model: experiments, simulations and theory
Physical Review E 51, 4655–4673 (1995)
P. Jensen, A.-L. Barabási, H. Larralde, S. Havlin, H.E. Stanley
Growth and percolation of thin films: a model incorporating deposition, diffusion and aggregation
Chaos, Solitons and Fractals 6, 227–232 (1995)
Read the abstract
We propose a model for describing diffusion-controlled aggregation of particles that are continually deposited on a surface. The model, which incorporates deposition, diffusion and aggregation, is motivated by recent thin film deposition experiments. We find, that the diffusion and aggregation of randomly deposited particles “builds” a wide variety of fractal structures, all characterized by a common length scale L1. This length LI scales as the ratio of the diffusion constant over the particle flux to the power l/4. We compare our msults with several recent experiments on two-dimensional nanostructures formed by diffusion-controlled aggregation on surfaces.
P. Jensen, A.-L. Barabási, H. Larralde, S. Havlin, H.E. Stanley
Deposition, diffusion and aggregation of atoms on surfaces: a model for nanostructure growth
Physical Review B 50, 15316–15329 (1994)
Read the abstract
We propose a model that describes the diffusion-controlled aggregation exhibited by particles as they deposited on a surface.The model, which incorporates deposition, particle and cluster diffusion, and aggregation, is inspired by recent thin-film-deposition experiments. We find that as randomly deposited particles diffuse and aggregate they configure themselves into a wide variety of fractal structures characterized by a length scale L1. We introduce an exponent y that tunes the way the diffusion coefficient changes with cluster size: if the values of y are very large, only single particles can move, if they are smaller, all clusters can move. The introduction of cluster diffusion dramatically affects the dynamics of film growth. We compare our results with those of several recent experiments on two-dimensional nanostructures formed by diffusion-controlled aggregation on surfaces, and we propose several experimental tests of the model. We also investigate the spanning properties of this model and find another characteristic length scale L2 (L>>L1) above which the system behaves as a bond percolation network of the fractal structures each of length scale L1. Below L2, the system shows similarities with diffusion-limited aggregation. we find that L1 scales as the ratio of the diffusion constant over the particle flux to the power 1/4, whereas L2 scales with another exponent close to 0.9.
L.A.N. Amaral, A.-L. Barabási, H.E. Stanley
Universality classes for interface growth with quenched disorder
Physical Review Letters 73, 62–65 (1994)
P. Jensen, A.-L. Barabási, H. Larralde, S. Havlin, H.E. Stanley
Model incorporating deposition, diffusion and aggregation in submonolayer nanostructures
Physical Review E 50, 618–621 (1994)
Read the abstract
We propose a model for describing diffusion-controlled aggregation of particles that are continually depostied on a surface. The model incorporates deposition, diffusion, and aggregation. We find that the diffusion and aggregation of randomly deposited particles
P. Jensen, A.-L. Barabási, H. Larralde, S. Havlin, H.E. Stanley
Connectivity of diffusing particles continually deposited on a surface: relation to LECBD experiments
Physica A 207, 219–227 (1994)
Read the abstract
We generalize the conventional model of two-dimensional site percolation by including both (1) continuous deposition of particles on a two-dimensional substrate, and (2) diffusion of these particles in two-dimensions. This new model is motivated by recent thin film deposition experiments using the low-energy cluster beam deposition (LECBD) technique. Depending on various parameters such as deposition flux, diffusion constant, and system size, we find a rich range of fractal morphologies including diffusion limited aggregation (DLA), cluster-cluster aggregation (CCA), and percolation.
P. Jensen, A.-L. Barabási, H. Larralde, S. Havlin, H.E. Stanley
Controlling nanostructures
Nature 368, 22 (1994)
Read the abstract
Roder et al. report nanometrescales structures built by deposition of diffusing particles that aggregate on surfaces. We have developed a microscopic model that mimics the same process, and produces morphologies that remarkable resemble the experimental structures.
L.A.N. Amaral, A.-L. Barabási, S.V. Buldyrev, S. Havlin, H.E. Stanley
New exponent characterizing the effect of evaporation on imbibition experiments
Physical Review Letters 72, 641–644 (1994)
Read the abstract
We report imbibition experiments investigating the effect of evaporation on the interface roughness and mean interface height. We observe a new exponent characterizing the scaling of the saturated surface width. Further, we argue that evaporation can be usefully modeled by introducing a gradient in the strength of the disorder, in analogy with the gradient percolation model of Sapoval et al. By incorporating this gradient we predict a new critical exponent and a novel scaling relation for the interface width. Both the exponent value and the form of the scaling agree with the experimental results.
L.A.N. Amaral, A.-L. Barabási, S.V. Buldyrev, S. Havlin, H.E. Stanley
Anomalous interface roughening: the role of a gradient in the density of pinning sites
Fractals 1, 818–826 (1993)
A.-L. Barabási
Surfactant-mediated surface growth: nonequilibrium theory
Fractals 1, 846–859 (1993)
Read the abstract
A number of recent experiments have shown that surfactants can modifiy the growth mode of an epitaxial film, suppressing islanding and promoting lyer-by-layer growth. hee, a set of coupled equations are introduced to describe the coupling between a growing interface and a thin surfactant layer deposited on the top of the nonequilibrium surface. The equations are derived using the main experimentally backed characteristics of the system and basic symmetry principles. The system is studied using dynamic-normalization-group scheme, which provides scaling relations between the roughness exponents. It is found that the surfactant may drive the system nto a novel phase, in which the surface roughness is negative, corresponding to a flat surface.
A.-L. Barabási
Surfactant-mediated growth of nonequilibrium interfaces
Physical Review Letters 70, 4102–4105 (1993)
Read the abstract
A number of recent experiments have shown that surfactants can modify the growth mode of an epitaxial film, suppressing islanding and promoting layer-by-layer growth. Here I introduce a set of coupled equations to describe the nonequilibrium roughening of an interface covered with a thin surfactant layer. The surfactant may drive the system into a novel phase, in which the surface roughness is negative, corresponding to a flat surface.
A.-L. Barabási
Dynamic scaling of coupled nonequilibrium interfaces
Physical Review A 46, R2977– R2980 (1992)
Read the abstract
We propose a simple discrete model to study the nonequilibrium fluctuations of two locally coupled (1+1)-dimensional systems (interfaces). Measuring numerically the tilt-dependent velocity we construct a set of stochastic continuum equations describing the fluctuations in the model. The scaling predicted by the equations is studied analitically using dynamic-renormalization-group theory and compared with simulation results.
A.-L. Barabási, M. Araujo, H.E. Stanley
Three-dimensional Toom model: connection to the Anisotropic Kardar-Parisi-Zhang Equation
Physical Review Letters 68, 3729–3732 (1992)
Read the abstract
A three-dimensional Toom model is defined and the properties of the interface separeting the two stable phases are investigated. Using symmetry arguments we show that in the zero-noise limit the model has only nonequilibrium fluctuations and that the scaling is decribed by the anisotropic Kardar-Parisi-Zhang equation. The scaling exponents are determined numerically and good agreement with the theoretical predictions is found.
S.V. Buldyrev, A.-L. Barabási, F. Caserta, S. Havlin, H.E. Stanley, T. Vicsek
Anomalous interface roughening in porous media: experiment and model
Physical Review A 45, R8313–R8316 (1992)
Read the abstract
We report measurements of the interface formed when a wet front propogates in paper by imbibition and we find anomalous roughening with exponent α=0.63±0.04. We also formulate an imbibition model that agrees with the experimental morphology. The main ingredient of the model is the propogation and pinning of a self-affine interface in the presence of quenched disorder, with erosion of overhangs. By relating our model to directed percolation, we find α~0.63.
A.-L. Barabási, R. Bourbonnais, M. Jensen, J. Kertesz, T. Vicsek, Y.-C. Zhang
Multifractality of growing surfaces
Physical Review A 45, R6951–R6954 (1992)
Read the abstract
We have carried out large-scale computer stimulation of experimentally motivated (1+1)- dimensional modes of kinetic surface roughening with power-law-distributed amplitudes of uncorrelated noise. The appropriately normalized qth-order correlation function of the height differences Cq(x)=<|h(x+x')-h(x')|q> shows strong multifractal scaling behavior up to a crossover length depending on the system size, i.e. Cq(x)~xqHq, where Hq is a continuously changing nontrivial function. Beyond the crossover length conventional scaling is found.
A.-L. Barabási, P. Szepfalusy, T. Vicsek
Multifractal spectra of multi-affine functions
Physica A 178, 17–28 (1991)
Read the abstract
Self-affine fiunctions F(x) with multiscaling height correlations Cq(x)~XqHq are described in terrms of the standard multifractal formalism with a modified assumption for the partition. The corresponding quantities and expressions are shown to exhibit some characteristic differences from the standard ones. According to our calculations the f(a) type spectra are not uniquely determined by the Hq spectrum, but, depend on the particular which is made for the dependence of N on x, where N is the number of points over which the average is taken. Our results are expected to be relevant in the analysis of signal type data obtained in experiments on systems which an underlying multiplicative process.
A.-L. Barabási
A model for the temporal fluctuations of the surface width: a stochastic one-dimensional map
Journal of Physics A 24, 17-28 (1991)
Read the abstract
A stochastic one-dimensional map is introduced to model the steady-state fluctuations of the surface width in far-from-equilibrium surface roughening. The dynamics of the map and the correlations in the time sequence are investigated. In particular, for power law distributed noise a non-trivial multi-affine behaviour is observed.
A.-L. Barabási, T. Vicsek
Multifractality of self-affine fractals
Physical Review A 44, 2730–2733 (1991)
Read the abstract
The concept of multifractality is extended to self-affine fractals in order to provide a more complete description of fractal surfaces. We show that for a class of iteratively constructed self-affine functions there exists an infinite hierarchy of exponents Hq describing the scaling of the qth order height-height correlationfunction Cq(x)~xqhq. Possible applications to random walks and turbulent flows are discussed. It is demonstratedon on the example of random walks along a chain that for stochastic lattice models leading to self-affine fractals Hq exhibits phase-transition-like behavior.
A.-L. Barabási, T. Vicsek
Tracing a diffusion-limited-aggregate: self-affine versus self-similar scaling
Physical Review A 41, 6881–6883 (1990)
Read the abstract
The geometry of diffusion-limited aggregation clusters is mapped into single-valued functions by tracing the surface of the aggregate and recording the X (or Y) coordinate of the position of a walker moving along perimeter of the cluster as a function of the arc length. Our numerical results and scaling arguments show that the related plots can be considered as self-affine functions whose scaling behavior is determined by the exponent H=1/D, where D is fractal dimension of the aggregates.
A.-L. Barabási, L. Nitsch, I. A. Dorobantu
On crises and supertracks: an attempt of a unified theory
Revue Roumanie de Physique 34, 353-357 (1989)
Read the abstract
An attempt is presented to study from a unified point of view crises and supertracks. The concept of n-th order crises is introduced and used to establish a general frame or describing the crises of one-dimensional maps.
A.-L. Barabási, L. Nitsch, I.A. Dorobantu
Supertracks and nth order windows in the chaotic regime
Physics Letters A 139, 53-56 (1989)
Read the abstract
The purpose of this paper is to generalize the concept of supertrack functions (STF), to sketch the main lines of a renormalization theory of STF and to obtain a scaling relation yielding nth order windows in the chaotic domain for the large calss of one-dimensional maps.