Generalized percolation in random directed networks
Physical Review EPublished 7 July 2005Open access
Marián Boguñá, M. Ángeles Serrano
Citations167
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A general theory for percolation in directed random networks with arbitrary two-point correlations and bidirectional edges--that is, edges pointing in both directions simultaneously--is developed.
Abstract
We develop a general theory for percolation in directed random networks with arbitrary two-point correlations and bidirectional edges--that is, edges pointing in both directions simultaneously. These two ingredients alter the previously known scenario and open new views and perspectives on percolation phenomena. Equations for the percolation threshold and the sizes of the giant components are derived in the most general case. We also present simulation results for a particular example of uncorrelated network with bidirectional edges confirming the theoretical predictions.
Keywords
MathematicsPhysics and Astronomy
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
Physical Review LettersAssortative Mixing in Networks
4,980 Citations2002M. E. J. Newman
This work proposes a model of an assortatively mixed network and finds that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsRandom graphs with arbitrary degree distributions and their applications
3,644 Citations2001M. E. J. Newman, Steven H. Strogatz +1 more
It is demonstrated that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsMixing patterns in networks
3,076 Citations2003M. E. J. Newman
This work proposes a number of measures of assortative mixing appropriate to the various mixing types, and applies them to a variety of real-world networks, showing that assortsative mixing is a pervasive phenomenon found in many networks.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
Journal of Computational BiologyModeling and Simulation of Genetic Regulatory Systems: A Literature Review
2,661 Citations2002Hidde de Jong
This paper reviews formalisms that have been employed in mathematical biology and bioinformatics to describe genetic regulatory systems, in particular directed graphs, Bayesian networks, Boolean networks and their generalizations, ordinary and partial differential equations, qualitative differential equation, stochastic equations, and rule-based formalisms.
Physical Review LettersNetwork Robustness and Fragility: Percolation on Random Graphs
2,422 Citations2000Duncan S. Callaway, M. E. J. Newman +2 more
This paper studies percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolators, bond percolations, and models in which occupation probabilities depend on vertex degree.
Random Structures and AlgorithmsA critical point for random graphs with a given degree sequence
2,401 Citations1995Michael Molloy, Bruce Reed
It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.
RePEc: Research Papers in EconomicsEvolution of networks from biological nets to the Internet and WWW
2,053 Citations2003S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The aim of the text is to understand networks and the basic principles of their structural organization and evolution, so even students without a deep knowledge of mathematics and statistical physics will be able to rely on this as a reference.
Oxford University Press eBooksEvolution of Networks
1,528 Citations2003S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The European Physical Journal BHow popular is your paper? An empirical study of the citation distribution
1,508 Citations1998S. Redner
Cambridge University Press eBooksEvolution and Structure of the Internet
1,335 Citations2004Romualdo Pastor‐Satorras, Alessandro Vespignani
Viewed in this analysis from a statistical physics perspective, the Internet is perceived as a developing system that evolves through the addition and removal of nodes and links, allowing the authors to outline the dynamical theory that can appropriately describe the Internet's macroscopic evolution.
Journal of Combinatorial Theory Series AThe asymptotic number of labeled graphs with given degree sequences
996 Citations1978Edward A. Bender, E. Rodney Canfield
Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: each row sum is specified and bounded, and a specified “sparse” set of entries must be zero.
Combinatorics Probability ComputingThe Size of the Giant Component of a Random Graph with a Given Degree Sequence
828 Citations1998Michael Molloy, Bruce Reed
The size of the giant component in the former case, and the structure of the graph formed by deleting that component is analyzed, which is basically that of a random graph with n′=n−∣C∣ vertices, and with λ′in′ of them of degree i.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsEmail networks and the spread of computer viruses
796 Citations2002M. E. J. Newman, Stephanie Forrest +1 more
Empirically the structure of this network of connections between individuals over which the virus spreads is investigated using data drawn from a large computer installation, and the implications for the understanding and prevention of computer virus epidemics are discussed.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsEpidemic spreading in correlated complex networks
552 Citations2002Marián Boguñá, Romualdo Pastor‐Satorras
A dynamical model of epidemic spreading on complex networks in which there are explicit correlations among the node's connectivities finds an epidemic threshold inversely proportional to the largest eigenvalue of the connectivity matrix that gives the average number of links.
Physical Review LettersPatterns of Link Reciprocity in Directed Networks
465 Citations2004Diego Garlaschelli, Maria I. Loffredo
It is found that real networks are always either correlated or anticorrelated, and that networks of the same type display similar values of the reciprocity.
Journal of DocumentationEvolution and Structure of the Internet: A Statistical Physics Approach
417 Citations2005David Bawden, Vespignani, Alessandro
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsGiant strongly connected component of directed networks
293 Citations2001S. N. Dorogovt︠s︡ev, J. F. F. Mendes +1 more
It is explained that the giant strongly connected component may be less resilient to random damage than the giant weakly connected one and that the World Wide Web is a directed network.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsResilience to damage of graphs with degree correlations
268 Citations2003Alexei Vázquez, Yamir Moreno
This work investigates the problems of site and bond percolation on graphs with degree correlations and their connection with spreading phenomena and obtains some general expressions that allow the computation of the transition thresholds or their bounds.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPercolation in directed scale-free networks
222 Citations2002Nehemia Schwartz, Reuven Cohen +3 more
The percolation properties of directed scale-free networks with correlated in and out degree distributions are studied, derived from a phase diagram that indicates the existence of three regimes, determined by the values of the degree exponents.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsAnomalous percolation properties of growing networks
133 Citations2001S. N. Dorogovt︠s︡ev, J. F. F. Mendes +1 more
The anomalous phase transition of the emergence of the giant connected component in scale-free networks growing under mechanism of preferential linking is described and exact results for the size and the distribution of vertices among connected components are obtained.
Physica A Statistical Mechanics and its ApplicationsUniversal properties of growing networks
31 Citations2004P. L. Krapivsky, Bernard Derrida
Networks growing according to the rule that every new node has a probability pk of being attached to k preexisting nodes, have a universal phase diagram and exhibit power-law decays of the distribution of cluster sizes in the non-percolating phase.