Computational complexity arising from degree correlations in networks
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPublished 7 February 2003Open access
Alexei Vázquez, Martin Weigt
Citations58
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 Bethe-Peierls approach is applied to statistical-mechanics models defined on random networks of arbitrary degree distribution and arbitrary correlations between the degrees of neighboring vertices, showing that such correlations may lead to a qualitatively different solution structure as compared to uncorrelated networks.
Abstract
We apply a Bethe-Peierls approach to statistical-mechanics models defined on random networks of arbitrary degree distribution and arbitrary correlations between the degrees of neighboring vertices. Using the nondeterministic polynomial time hard optimization problem of finding minimal vertex covers on these graphs, we show that such correlations may lead to a qualitatively different solution structure as compared to uncorrelated networks. This results in a higher complexity of the network in a computational sense: Simple heuristic algorithms fail to find a minimal vertex cover in the highly correlated case, whereas uncorrelated networks seem to be simple from the point of view of combinatorial optimization.
Keywords
Computer SciencePhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
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.
NatureError and attack tolerance of complex networks
7,218 Citations2000Réka Albert, Hawoong Jeong +1 more
It is found that scale-free networks, which include the World-Wide Web, the Internet, social networks and cells, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates.
Physical Review LettersEpidemic Spreading in Scale-Free Networks
5,770 Citations2001Romualdo Pastor‐Satorras, Alessandro Vespignani
A dynamical model for the spreading of infections on scale-free networks is defined, finding the absence of an epidemic threshold and its associated critical behavior and this new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.
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 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.
Physical Review LettersDynamical and Correlation Properties of the Internet
1,452 Citations2001Romualdo Pastor‐Satorras, Alexei Vázquez +1 more
It is found that the Internet is characterized by non-trivial correlations among nodes and different dynamical regimes, and the importance of node hierarchy and aging in the Internet structure and growth is pointed out.
Physical Review LettersBreakdown of the Internet under Intentional Attack
1,423 Citations2001Reuven Cohen, Keren Erez +2 more
It is argued that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, M, as square root of [M], rather than as log (k)M, as expected for random networks away from criticality.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsImmunization of complex networks
1,270 Citations2002Romualdo Pastor‐Satorras, Alessandro Vespignani
It is shown that the random uniform immunization of individuals does not lead to the eradication of infections in all complex networks, and networks with scale-free properties do not acquire global immunity from major epidemic outbreaks even in the presence of unrealistically high densities of randomly immunized individuals.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSearch in power-law networks
1,207 Citations2001Lada A. Adamic, Rajan M. Lukose +2 more
A number of local search strategies that utilize high degree nodes in power-law graphs and that have costs scaling sublinearly with the size of the graph are introduced and demonstrated on the GNUTELLA peer-to-peer network.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsOrganization of growing random networks
894 Citations2001P. L. Krapivsky, S. Redner
The organizational development of growing random networks is investigated, and the combined age and degree distribution of nodes shows that old nodes typically have a large degree.
The European Physical Journal BThe Bethe lattice spin glass revisited
822 Citations2001Marc Mézard, Giorgio Parisi
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsLarge-scale topological and dynamical properties of the Internet
691 Citations2002Alexei Vázquez, Romualdo Pastor‐Satorras +1 more
It is found that the connectivity structure of the Internet presents statistical distributions settled in a well-defined stationary state and the large-scale properties are characterized by a scale-free topology consistent with previous observations.
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 LettersNumber of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random Graphs
212 Citations2000Martin Weigt, Alexander K. Hartmann
The replica symmetric phase diagram is in excellent agreement with numerical findings up to average connectivity e, where replica symmetry becomes locally unstable.
Physical Review LettersCorrelated Random Networks
169 Citations2002Johannes Berg, Michael Lässig
More general interactions H(c) are studied which lead to correlations, for example, between the connectivities of adjacent vertices which are argued to be a crucial signature of evolutionary design in biological networks.
The European Physical Journal BCore percolation in random graphs: a critical phenomena analysis
120 Citations2001Michel Bauer, O. Golinelli
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsMinimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture
76 Citations2001Martin Weigt, Alexander K. Hartmann
A detailed description of the replica-symmetric phase, including the size and entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c approximately 1.43.
The European Physical Journal BDynamics of heuristic optimization algorithms on random graphs
19 Citations2002Martin Weigt
The dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed, and approximation schemes for more complicated cases are developed.