Friends and enemies in the Middle East. Who is connected to whom? - interactive | News | The Guardian
https://www.theguardian.com/news/datablog/ng-interactive/2014/sep/24/friends-and-enemies-in-the-middle-east-who-is-connected-to-who-interactive
https://www.theguardian.com/news/datablog/ng-interactive/2014/sep/24/friends-and-enemies-in-the-middle-east-who-is-connected-to-who-interactive
the Guardian
Friends and enemies in the Middle East. Who is connected to whom? - interactive
As the US and UK are set to again commit to military involvement in the Middle East, this interactive visualises the intricate, complex and sometimes hidden relationships and alliances across the region
🔥 Gall's Law: "A complex system that works is invariably found to have evolved from a simple system that worked."
– John Gall (1975)
– John Gall (1975)
Tutorials are short, self-paced “mini-courses” designed to introduce students to important techniques and to provide illustrations of their application in complex systems.
https://www.complexityexplorer.org/tutorials
https://www.complexityexplorer.org/tutorials
On some deep connections between computer science, statistical physics and information theory:
http://lptms.u-psud.fr/membres/mezard/edwards.pdf
http://lptms.u-psud.fr/membres/mezard/edwards.pdf
📄 Kindermann, Ross; Snell, J. Laurie (1980).
🔹 Markov Random Fields and Their Applications 🔹
(PDF): http://www.cmap.polytechnique.fr/~rama/ehess/mrfbook.pdf
🔹 Markov Random Fields and Their Applications 🔹
(PDF): http://www.cmap.polytechnique.fr/~rama/ehess/mrfbook.pdf
🗞 Review:
"Statistical physics of inference: Thresholds and algorithms"
Lenka Zdeborová, Florent Krzakala
(Submitted on 8 Nov 2015 (v1), last revised 28 Jul 2016 (this version, v4))
🔗 https://arxiv.org/pdf/1511.02476
Many questions of fundamental interest in todays science can be formulated as inference problems: Some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. Connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which formulated as an inference problem we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.
"Statistical physics of inference: Thresholds and algorithms"
Lenka Zdeborová, Florent Krzakala
(Submitted on 8 Nov 2015 (v1), last revised 28 Jul 2016 (this version, v4))
🔗 https://arxiv.org/pdf/1511.02476
Many questions of fundamental interest in todays science can be formulated as inference problems: Some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. Connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which formulated as an inference problem we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.
🗞 Review:
"Statistical Physics of Hard Optimization Problems"
Lenka Zdeborová - PhD thesis
(Submitted on 25 Jun 2008)
🔗 https://arxiv.org/pdf/0806.4112
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named "locked" constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.
"Statistical Physics of Hard Optimization Problems"
Lenka Zdeborová - PhD thesis
(Submitted on 25 Jun 2008)
🔗 https://arxiv.org/pdf/0806.4112
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named "locked" constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.
🌀 What physics can tell us about inference ?
Cristopher Moore, Santa Fe Institute
🎞 http://www.savoirs.ens.fr/expose.php?id=2696
This colloquium is organized around data sciences in a broad sense, with the goal of bringing together researchers with diverse backgrounds (including mathematics, computer science, physics, chemistry and neuroscience) but a common interest in dealing with large scale or high dimensional data.
There is a deep analogy between statistical inference and statistical physics; I will give a friendly introduction to both of these fields. I will then discuss phase transitions in two problems of interest to a broad range of data sciences: community detection in social and biological networks, and clustering of sparse high-dimensional data. In both cases, if our data becomes too sparse or too noisy, it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Physics both helps us locate these phase transiitons, and design optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.
Cristopher Moore, Santa Fe Institute
🎞 http://www.savoirs.ens.fr/expose.php?id=2696
This colloquium is organized around data sciences in a broad sense, with the goal of bringing together researchers with diverse backgrounds (including mathematics, computer science, physics, chemistry and neuroscience) but a common interest in dealing with large scale or high dimensional data.
There is a deep analogy between statistical inference and statistical physics; I will give a friendly introduction to both of these fields. I will then discuss phase transitions in two problems of interest to a broad range of data sciences: community detection in social and biological networks, and clustering of sparse high-dimensional data. In both cases, if our data becomes too sparse or too noisy, it suddenly becomes impossible to find the underlying pattern, or even tell if there is one. Physics both helps us locate these phase transiitons, and design optimal algorithms that succeed all the way up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.
www.savoirs.ens.fr
Savoirs ENS
Les derniers cours, séminaires, colloques et conférences enregistrées à l'Ecole Normale Supérieure (Paris)
🔘 One week summerschool at bachelor level
Mathematical Modelling, Nonlinear Dynamics,Stochastic and Complex Systems
August 27 - September 2, 2017
Rostock, Germany
http://www.math.uni-rostock.de/complexsystems/
Mathematical Modelling, Nonlinear Dynamics,Stochastic and Complex Systems
August 27 - September 2, 2017
Rostock, Germany
http://www.math.uni-rostock.de/complexsystems/