Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Equilibrium and Dynamics on Complex Networkds
KTH, Skolan för datavetenskap och kommunikation (CSC), Beräkningsvetenskap och beräkningsteknik (CST).ORCID-id: 0000-0002-1252-2899
2016 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Complex networks are an important class of models used to describe the behaviour of a very broad category of systems which appear in different fields of science ranging from physics, biology and statistics to computer science and other disciplines. This set of models includes spin systems on a graph, neural networks, decision networks, spreading disease, financial trade, social networks and all systems which can be represented as interacting agents on some sort of graph architecture.

In this thesis, by using the theoretical framework of statistical mechanics, the equilibrium and the dynamical behaviour of such systems is studied.

For the equilibrium case, after presenting the region graph free energy approximation, the Survey Propagation method, previously used to investi- gate the low temperature phase of complex systems on tree-like topologies, is extended to the case of loopy graph architectures.

For time-dependent behaviour, both discrete-time and continuous-time dynamics are considered. It is shown how to extend the cavity method ap- proach from a tool used to study equilibrium properties of complex systems to the discrete-time dynamical scenario. A closure scheme of the dynamic message-passing equation based on a Markovian approximations is presented. This allows to estimate non-equilibrium marginals of spin models on a graph with reversible dynamics. As an alternative to this approach, an extension of region graph variational free energy approximations to the non-equilibrium case is also presented. Non-equilibrium functionals that, when minimized with constraints, lead to approximate equations for out-of-equilibrium marginals of general spin models are introduced and discussed.

For the continuous-time dynamics a novel approach that extends the cav- ity method also to this case is discussed. The main result of this part is a Cavity Master Equation which, together with an approximate version of the Master Equation, constitutes a closure scheme to estimate non-equilibrium marginals of continuous-time spin models. The investigation of dynamics of spin systems is concluded by applying a quasi-equilibrium approach to a sim- ple case. A way to test self-consistently the assumptions of the method as well as its limits is discussed.

In the final part of the thesis, analogies and differences between the graph- ical model approaches discussed in the manuscript and causal analysis in statistics are presented.

Ort, förlag, år, upplaga, sidor
Stockholm: KTH Royal Institute of Technology, 2016. , s. 189
Serie
TRITA-CSC-A, ISSN 1653-5723 ; 2016:17
Nyckelord [en]
Statistical mechanics, complex networks, spin systems, non equilibrium dynamics, generalized belief propagation, message passing, cavity method, variational approaches
Nationell ämneskategori
Annan fysik Fysik
Forskningsämne
Fysik
Identifikatorer
URN: urn:nbn:se:kth:diva-191991ISBN: 978-91-7729-058-2 (tryckt)OAI: oai:DiVA.org:kth-191991DiVA, id: diva2:957675
Disputation
2016-09-09, Kollegiesalen, Brinellvägen 8, plan 4, Stockholm, 10:00 (Engelska)
Opponent
Handledare
Anmärkning

QC 20160904

Tillgänglig från: 2016-09-04 Skapad: 2016-09-03 Senast uppdaterad: 2016-09-05Bibliografiskt granskad
Delarbeten
1. Cavity Method: Message Passing from a Physics perspective
Öppna denna publikation i ny flik eller fönster >>Cavity Method: Message Passing from a Physics perspective
2016 (Engelska)Ingår i: Statistical Physics, Optimization, Inference, and Message-Passing Algorithms: Lecture Notes of the Les Houches School of Physics - Special Issue October 2013 / [ed] F. Krzakala et al., Oxford University Press, 2016Kapitel i bok, del av antologi (Övrigt vetenskapligt)
Abstract [en]

In this three-sections lecture cavity method is introduced as heuristic framework from a Physics perspective to solve probabilistic graphical models and it is presented both at the replica symmetric (RS) and 1-step replica symmetry breaking (1RSB) level. This technique has been applied with success on a wide range of models and problems such as spin glasses, random constrain satisfaction problems (rCSP), error correcting codes etc. Firstly, the RS cavity solution for Sherrington-Kirkpatrick model---a fully connected spin glass model---is derived and its equivalence to the RS solution obtained using replicas is discussed. Then, the general cavity method for diluted graphs is illustrated both at RS and 1RSB level. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as example of an actual problem, K-SAT is investigated using belief and survey propagation.

Ort, förlag, år, upplaga, sidor
Oxford University Press, 2016
Nyckelord
cavity method, message passing, survey propagation, tree-like graphs
Nationell ämneskategori
Fysik
Forskningsämne
Fysik
Identifikatorer
urn:nbn:se:kth:diva-192102 (URN)
Externt samarbete:
Anmärkning

QC 20160905

Tillgänglig från: 2016-09-05 Skapad: 2016-09-05 Senast uppdaterad: 2016-09-05Bibliografiskt granskad
2. On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
Öppna denna publikation i ny flik eller fönster >>On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
2016 (Engelska)Ingår i: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, artikel-id 073305Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider a one-step replica symmetry breaking description of the Edwards–Anderson spin glass model in 2D. The ingredients of this description are a Kikuchi approximation to the free energy and a second-level statistical model built on the extremal points of the Kikuchi approximation, which are also fixed points of a generalized belief propagation (GBP) scheme. We show that a generalized free energy can be constructed where these extremal points are exponentially weighted by their Kikuchi free energy and a Parisi parameter y, and that the Kikuchi approximation of this generalized free energy leads to second-level, one-step replica symmetry breaking (1RSB), GBP equations. We then proceed analogously to the Bethe approximation case for tree-like graphs, where it has been shown that 1RSB belief propagation equations admit a survey propagation solution. We discuss when and how the one-step-replica symmetry breaking GBP equations that we obtain also allow a simpler class of solutions which can be interpreted as a class of generalized survey propagation equations for the single instance graph case.

Ort, förlag, år, upplaga, sidor
Institute of Physics (IOP), 2016
Nyckelord
Region graph approximations, generalized belief propagation, survey propagation, generalized survey propagation, low temperature
Nationell ämneskategori
Naturvetenskap Fysik
Forskningsämne
Fysik
Identifikatorer
urn:nbn:se:kth:diva-192097 (URN)10.1088/1742-5468/2016/07/073305 (DOI)2-s2.0-85014438156 (Scopus ID)
Externt samarbete:
Anmärkning

QC 20160905

Tillgänglig från: 2016-09-05 Skapad: 2016-09-05 Senast uppdaterad: 2017-11-21Bibliografiskt granskad
3. Dynamic message-passing approach for kinetic spin models with reversible dynamics
Öppna denna publikation i ny flik eller fönster >>Dynamic message-passing approach for kinetic spin models with reversible dynamics
2015 (Engelska)Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 92, nr 1, artikel-id 010102Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A method to approximately close the dynamic cavity equations for synchronous reversible dynamics on a locally treelike topology is presented. The method builds on (a) a graph expansion to eliminate loops from the normalizations of each step in the dynamics and (b) an assumption that a set of auxilary probability distributions on histories of pairs of spins mainly have dependencies that are local in time. The closure is then effectuated by projecting these probability distributions on n-step Markov processes. The method is shown in detail on the level of ordinary Markov processes (n = 1) and outlined for higher-order approximations (n > 1). Numerical validations of the technique are provided for the reconstruction of the transient and equilibrium dynamics of the kinetic Ising model on a random graph with arbitrary connectivity symmetry.

Ort, förlag, år, upplaga, sidor
American physical society, 2015
Nationell ämneskategori
Fusion, plasma och rymdfysik
Identifikatorer
urn:nbn:se:kth:diva-172162 (URN)10.1103/PhysRevE.92.010102 (DOI)000358259400001 ()
Externt samarbete:
Anmärkning

QC 20150818

Tillgänglig från: 2015-08-18 Skapad: 2015-08-14 Senast uppdaterad: 2017-12-04Bibliografiskt granskad
4. A simple approach to the dynamics of Ising spin systems
Öppna denna publikation i ny flik eller fönster >>A simple approach to the dynamics of Ising spin systems
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Abstract [en]

We study a novel variational approach to solve the dynamics of Ising-like discrete spin systems. The equations are derived under mean-field approximations based on the cluster variational method. Comparison with the actual Glauber dynamics of models defined on Erdos-R\'enyi random graphs show that some of these approximations are extremely accurate, both at equilibrium and in the off-equilibrium regime, providing the same result of the Monte Carlo simulation in a much shorter time. The models studied are the ferromagnetic kinetic Ising model (both with symmetric and partially asymmetric interactions), the random field Ising model and the Viana-Bray model. Only for the latter model we find some small discrepancies in the very low temperature phase, probably due to the existence of a large number of metastable states.

Nyckelord
variational approximations, spin dynamics, Glauber dynamics, cluster variation method, path probability method
Nationell ämneskategori
Fysik
Forskningsämne
Fysik
Identifikatorer
urn:nbn:se:kth:diva-192098 (URN)
Externt samarbete:
Anmärkning

QC 20160905

Tillgänglig från: 2016-09-05 Skapad: 2016-09-05 Senast uppdaterad: 2016-09-05Bibliografiskt granskad
5. A Cavity Master Equation for the continuous time dynamics of discrete spins models
Öppna denna publikation i ny flik eller fönster >>A Cavity Master Equation for the continuous time dynamics of discrete spins models
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Abstract [en]

We present a new method to close the Master Equation representing the continuous time dynamics of Ising interacting spins. The method makes use of the the theory of Random Point Processes to derive a master equation for local conditional probabilities. We analytically test our solution studying two known cases, the dynamics of the mean field ferromagnet and the dynamics of the one dimensional Ising system. We then present numerical results comparing our predictions with Monte Carlo simulations in three different models on random graphs with finite connectivity: the Ising ferromagnet, the Random Field Ising model, and the Viana-Bray spin-glass model.

Nyckelord
continuous time dynamics, master equation, cavity method, cavity master equation, dynamic message passing, disordered models
Nationell ämneskategori
Fysik
Forskningsämne
Fysik
Identifikatorer
urn:nbn:se:kth:diva-192100 (URN)
Externt samarbete:
Anmärkning

QC 20160905

Tillgänglig från: 2016-09-05 Skapad: 2016-09-05 Senast uppdaterad: 2016-09-05Bibliografiskt granskad
6. Perturbative large deviation analysis of non-equilibrium dynamics
Öppna denna publikation i ny flik eller fönster >>Perturbative large deviation analysis of non-equilibrium dynamics
2014 (Engelska)Ingår i: Journal of the Physical Society of Japan, ISSN 0031-9015, E-ISSN 1347-4073, Vol. 83, nr 8Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Macroscopic fluctuation theory has shown that a wide class of non-equilibrium stochastic dynamical systems obey a large deviation principle, but except for a few one-dimensional examples these large deviation principles are in general not known in closed form. We consider the problem of constructing successive approximations to an (unknown) large deviation functional and show that the non-equilibrium probability distribution the takes a Gibbs-Boltzmann form with a set of auxiliary (non-physical) energy functions. The expectation values of these auxiliary energy functions and their conjugate quantities satisfy a closed system of equations which can imply a considerable reduction of dimensionality of the dynamics. We show that the accuracy of the approximations can be tested self-consistently without solving the full non- equilibrium equations. We test the general procedure on the simple model problem of a relaxing 1D Ising chain. 

Ort, förlag, år, upplaga, sidor
Physical society of Japan, 2014
Nyckelord
Macroscopic fluctuation theory, perturbative large deviation, dynamics Ising chain.
Nationell ämneskategori
Den kondenserade materiens fysik
Forskningsämne
Fysik
Identifikatorer
urn:nbn:se:kth:diva-165789 (URN)10.7566/JPSJ.83.084001 (DOI)000339806400012 ()2-s2.0-84924898390 (Scopus ID)
Projekt
NETADIS
Forskningsfinansiär
EU, FP7, Sjunde ramprogrammet
Anmärkning

QC 20150505

Tillgänglig från: 2015-04-29 Skapad: 2015-04-29 Senast uppdaterad: 2017-12-04
7. Causal analysis, Correlation-Response, and Dynamic cavity
Öppna denna publikation i ny flik eller fönster >>Causal analysis, Correlation-Response, and Dynamic cavity
2016 (Engelska)Ingår i: International Meeting on High-Dimensional Data-Driven Science (HD3-2015), Institute of Physics (IOP), 2016, artikel-id 012002Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

The purpose of this note is to point out analogies between causal analysis in statistics and the correlation-response theory in statistical physics. It is further shown that for some systems the dynamic cavity offers a way to compute the stationary state of a non-equilibrium process effectively, which could then be taken an alternative starting point of causal analysis.

Ort, förlag, år, upplaga, sidor
Institute of Physics (IOP), 2016
Serie
Journal of Physics Conference Series, ISSN 1742-6588 ; 699
Nationell ämneskategori
Sannolikhetsteori och statistik
Identifikatorer
urn:nbn:se:kth:diva-188463 (URN)10.1088/1742-6596/699/1/012002 (DOI)000376066400002 ()2-s2.0-84964835185 (Scopus ID)
Konferens
International Meeting on High-Dimensional Data-Driven Science (HD3), DEC 14-17, 2015, Kyoto, JAPAN
Anmärkning

QC 20160613

Tillgänglig från: 2016-06-13 Skapad: 2016-06-10 Senast uppdaterad: 2016-09-04Bibliografiskt granskad

Open Access i DiVA

fulltext(14064 kB)359 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 14064 kBChecksumma SHA-512
3c39959a2485c602a1516409c519b537f506cad6631b3b2ec7edd5fd53a67fb338ab7a10f827ff5c702f10e1be32fab4f2e90174112018048ac85af4cb04bc76
Typ fulltextMimetyp application/pdf

Personposter BETA

Del Ferraro, Gino

Sök vidare i DiVA

Av författaren/redaktören
Del Ferraro, Gino
Av organisationen
Beräkningsvetenskap och beräkningsteknik (CST)
Annan fysikFysik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 359 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 623 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf