Sergey N. Dorogovtsev
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780199548927
- eISBN:
- 9780191720574
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199548927.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter considers the organization of connected components in uncorrelated networks, in particular, the structure and size of a giant connected component. These properties are closely related to ...
More
This chapter considers the organization of connected components in uncorrelated networks, in particular, the structure and size of a giant connected component. These properties are closely related to the percolation properties of these networks. The value of the percolation threshold for various degree distributions is estimated, and the resilience of scale-free networks against random failures is described. The hierarchical organization of k-cores in these networks is discussed. A few basic epidemic models on complex networks are introduced, and the evolution of diseases in networks is described.Less
This chapter considers the organization of connected components in uncorrelated networks, in particular, the structure and size of a giant connected component. These properties are closely related to the percolation properties of these networks. The value of the percolation threshold for various degree distributions is estimated, and the resilience of scale-free networks against random failures is described. The hierarchical organization of k-cores in these networks is discussed. A few basic epidemic models on complex networks are introduced, and the evolution of diseases in networks is described.
Cristopher Moore and Stephan Mertens
- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0014
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a ...
More
Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a critical threshold. This transition is comparable to the freezing of water and also occurs in many other NP-complete problems such as graph coloring and integer partitioning. This chapter first considers some experimental results on random 3-SAT and assumes that a phase transition exists. It then explores some simple phase transitions in random graphs and shows how to compute the size of k-cores, along with the degrees at which they first appear. It also looks at random k-SAT formulas and demonstrates how to prove upper and lower bounds on the critical density of clauses. Furthermore, it describes simple search algorithms as flows through state space before concluding with a discussion of recent advances inspired by techniques in statistical physics.Less
Certain formulas, such as the 3-SAT formula, undergo a phase transition from almost certain satisfiability to almost certain unsatisfiability when the number of constraints per variable reaches a critical threshold. This transition is comparable to the freezing of water and also occurs in many other NP-complete problems such as graph coloring and integer partitioning. This chapter first considers some experimental results on random 3-SAT and assumes that a phase transition exists. It then explores some simple phase transitions in random graphs and shows how to compute the size of k-cores, along with the degrees at which they first appear. It also looks at random k-SAT formulas and demonstrates how to prove upper and lower bounds on the critical density of clauses. Furthermore, it describes simple search algorithms as flows through state space before concluding with a discussion of recent advances inspired by techniques in statistical physics.
