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.0014
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and ...
More
This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and describes existing approaches to the optimization-driven evolution of complex networks. In particular, the optimized trade-off model of a growing network is described, as well as models showing the explosive percolation phenomenon.Less
This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and describes existing approaches to the optimization-driven evolution of complex networks. In particular, the optimized trade-off model of a growing network is described, as well as models showing the explosive percolation phenomenon.
M. Mézard
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528531
- eISBN:
- 9780191713415
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528531.003.0017
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter is a non-technical, elementary introduction to the theory of glassy phases and their ubiquity. The aim is to provide a guide and some kind of coherent view to the various topics that ...
More
This chapter is a non-technical, elementary introduction to the theory of glassy phases and their ubiquity. The aim is to provide a guide and some kind of coherent view to the various topics that have been explored in recent years in this very diverse field, ranging from spin or structural glasses to protein folding, combinatorial optimization, neural networks, error correcting codes, and game theory.Less
This chapter is a non-technical, elementary introduction to the theory of glassy phases and their ubiquity. The aim is to provide a guide and some kind of coherent view to the various topics that have been explored in recent years in this very diverse field, ranging from spin or structural glasses to protein folding, combinatorial optimization, neural networks, error correcting codes, and game theory.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0013
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The mathematical structure highlighted in this chapter by the factor graph representation is the locality of probabilistic dependencies between variables. Locality also emerges in many problems of ...
More
The mathematical structure highlighted in this chapter by the factor graph representation is the locality of probabilistic dependencies between variables. Locality also emerges in many problems of probabilistic inference, which provides another unifying view of the field. This chapter describes coding theory, statistical physics, and combinatorial optimization as inference problems. It also explores one generic inference method, the use of Monte Carlo Markov chains (MCMC) in order to sample from complex probabilistic models. Many of the difficulties encountered in decoding, in constraint satisfaction problems, or in glassy phases, are connected to a dramatic slowing down of MCMC dynamics, which is explored through simple numerical experiments on some examples.Less
The mathematical structure highlighted in this chapter by the factor graph representation is the locality of probabilistic dependencies between variables. Locality also emerges in many problems of probabilistic inference, which provides another unifying view of the field. This chapter describes coding theory, statistical physics, and combinatorial optimization as inference problems. It also explores one generic inference method, the use of Monte Carlo Markov chains (MCMC) in order to sample from complex probabilistic models. Many of the difficulties encountered in decoding, in constraint satisfaction problems, or in glassy phases, are connected to a dramatic slowing down of MCMC dynamics, which is explored through simple numerical experiments on some examples.
Hidetoshi Nishimori
- Published in print:
- 2001
- Published Online:
- January 2010
- ISBN:
- 9780198509417
- eISBN:
- 9780191709081
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198509417.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics ...
More
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.Less
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.
Cristopher Moore and Stephan Mertens
- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. However, this beauty is often ...
More
Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. However, this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results such as interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear fashion, making them accessible to non-computer scientists and to computer scientists who finally want to appreciate their field from a new point of view. It starts with a lucid explanation of the P vs. NP problem, explaining why it is so fundamental, and so hard to resolve. It then leads the reader through the complexity of mazes and games; optimisation in theory and practice; randomised algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, it uses a minimum of formalism, providing explanations that are both deep and accessible.Less
Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. However, this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results such as interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear fashion, making them accessible to non-computer scientists and to computer scientists who finally want to appreciate their field from a new point of view. It starts with a lucid explanation of the P vs. NP problem, explaining why it is so fundamental, and so hard to resolve. It then leads the reader through the complexity of mazes and games; optimisation in theory and practice; randomised algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, it uses a minimum of formalism, providing explanations that are both deep and accessible.
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.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and ...
More
This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and only if we can tell whether a solution with a given quality exists. It then explores approximation algorithms for the traveling salesman problem and considers some large families of optimisation problems that can be solved in polynomial time, including linear programming and semidefinite programming. It demonstrates that the duality between MAX FLOW and MIN CUT is no accident — that linear programming problems come in pairs. In addition, the chapter looks at integer linear programming, which can be solved in polynomial time before concluding with a discussion of optimisation problems from a practical point of view.Less
This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and only if we can tell whether a solution with a given quality exists. It then explores approximation algorithms for the traveling salesman problem and considers some large families of optimisation problems that can be solved in polynomial time, including linear programming and semidefinite programming. It demonstrates that the duality between MAX FLOW and MIN CUT is no accident — that linear programming problems come in pairs. In addition, the chapter looks at integer linear programming, which can be solved in polynomial time before concluding with a discussion of optimisation problems from a practical point of view.
Mark Newman
- Published in print:
- 2018
- Published Online:
- October 2018
- ISBN:
- 9780198805090
- eISBN:
- 9780191843235
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198805090.003.0013
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter describes models of the growth or formation of networks, with a particular focus on preferential attachment models. It starts with a discussion of the classic preferential attachment ...
More
This chapter describes models of the growth or formation of networks, with a particular focus on preferential attachment models. It starts with a discussion of the classic preferential attachment model for citation networks introduced by Price, including a complete derivation of the degree distribution in the limit of large network size. Subsequent sections introduce the Barabasi-Albert model and various generalized preferential attachment models, including models with addition or removal of extra nodes or edges and models with nonlinear preferential attachment. Also discussed are node copying models and models in which networks are formed by optimization processes, such as delivery networks or airline networks.Less
This chapter describes models of the growth or formation of networks, with a particular focus on preferential attachment models. It starts with a discussion of the classic preferential attachment model for citation networks introduced by Price, including a complete derivation of the degree distribution in the limit of large network size. Subsequent sections introduce the Barabasi-Albert model and various generalized preferential attachment models, including models with addition or removal of extra nodes or edges and models with nonlinear preferential attachment. Also discussed are node copying models and models in which networks are formed by optimization processes, such as delivery networks or airline networks.
