Search Results

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.

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.

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.

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.

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.

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.