Correlation-Function for Random Graph Ising Model - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:26:57Z http://mathoverflow.net/feeds/question/93765 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93765/correlation-function-for-random-graph-ising-model Correlation-Function for Random Graph Ising Model Simon Lentner 2012-04-11T13:12:05Z 2012-04-23T11:47:11Z <p><em>For non-Ising'ers: Given a graph, we study the probability-distribution on the set of colorings ("Spin-up" and "-down") generated by a given correlation ("force to equality") between adjacient nodes (Bolzmann-Term depending exponentially on a "Temperature Parameter"). The limit of high Temperature is no-correlation whatsoever, the limit of low Temerature is all colors coincide for sure (are "parallel").</em></p> <p>In <a href="http://www.win.tue.nl/~sdommers/files/ising_rev.pdf" rel="nofollow">this paper</a> (Dommers, Giardinà, van der Hofstad, 2010) the <strong>partition function of the Ising model on a sparse random graph</strong> was calculated (sparse = almost surely no triangle, quadrangle etc )...well, I must add "calculated" refers to a random-variable fixpoint equation - I've put some effort into deriving an explicit expression thereof, but did not suceed ... a different story and maybe later a different question ;-)</p> <p>The proof techniques very basically relay on the <strong>transfer matrix method for a local tree</strong> inside the random graph (which is defined by a given branching distribution, e.g. Poisson); this ultimately leads to a recursion formula for the up/down-random-variable of a single site and the authors proof the existence of a unique solution (the mentionen fix-point). Partition function etc. are derived as various expectation vals.</p> <p>For use in an own work I would like to get ahold of the <strong>correlators</strong>, i.e. the probability of two sites of given distance $a$ to coincide. Though I do not expect this to be easier than explicitely calculate the partition function, a similar fix-point equation as in the original work would totally suffice! I tried the trick one uses in 1D, but I didn't get through...although I would naively expect, that it's easier than 2D, as you have better control over the walks...?</p> <p>Moreover, it would be interesting to have <strong>multi-correlators</strong> in the sense of knowing the probability of given up-down configurations e.g. in an arbitrary $abc$-triangle depending on the edge-length's $a,b,c$. $\;\;$ I don't even recall such from classical (2D) Ising model....any sources or ideas? Is that in "physically-sound" language the n-point-functions in this case?</p> http://mathoverflow.net/questions/93765/correlation-function-for-random-graph-ising-model/94629#94629 Answer by Juan Bermejo Vega for Correlation-Function for Random Graph Ising Model Juan Bermejo Vega 2012-04-20T12:26:21Z 2012-04-23T11:47:11Z <p>There is a method to study these physical systems called <a href="http://en.wikipedia.org/wiki/Belief_propagation" rel="nofollow"><strong>belief propagation (BP)</strong></a>, which yields exact methods for interaction graphs that are trees, and empirically works pretty fine when you have physical systems with <em>loopy</em> interaction graphs that <strong>locally-look-like trees</strong>. Randomly-generated sparse interaction graphs are of this form (its explicitly mentioned in the paper), and you could apply Belief Propagation to your model to obtain good estimates of the following quantities.</p> <ul> <li>Marginal probabilities $\sigma_i$.</li> <li>Joint probabilities $p(\sigma_i, \sigma_j)$, in particular, the <strong>correlators</strong> you mention.</li> <li>Conditional probabilities $p(\sigma_i | \sigma_j)$</li> <li>Partition functions, energies, free energies, entropies.</li> </ul> <p>And, in addition, BP can be adapted to sample from the probability distribution $p(\sigma)$. In physics, systems like these are sometimes called 'diluted spin-glasses'.</p> <p>I summarise the mean features of Belief propagation below. <a href="http://www.stanford.edu/~montanar/RESEARCH/book.html" rel="nofollow">Mézard, Montanari's book</a> contains a very pedagogical exposition of the method, also rather up-to-date and complete; you can read the draft of the book <em>online</em> without buying it. I personally used this book to prepare a <a href="http://www.mpq.mpg.de/Theorygroup/CIRAC/wiki/index.php/Theory_Seminar.html" rel="nofollow">seminar</a> and I can recommend it. The connections between Belief Propagation and the <strong>ferromagnetic spin Isin chain</strong> are explained in Part D, section 14.1 of the online version.</p> <h2>Overview</h2> <p>Belief propagation is an iterative "message-passing" algorithm. For each site/spin/particle (vertexes of the graph) of your system, the belief propagation methods assigns incoming and leaving "messages" to its neighbouring edges (which represent interactions) in the interaction graph. These messages can be understood as "probability weights" that contribute to the <em>marginal probability</em> that the particle say on site $i$ is on a given local configuration $\sigma_i$, which I denote by $p(\sigma_i)$. The messages are updated through <em>local</em> computations (thus, not costly) for each particle, following a set of equations known as the <strong>belief-propagation update-rules</strong>. I will not write the update-rules here, for they are lengthy.</p> <p>What it is important is the following: if on site $i$, with neighbours indexed by $a$, we denote the leaving/incoming messages on time $t$ by $p_{i\rightarrow a}^{t}(\sigma_i)$ and $p_{a\rightarrow i}^{t}(\sigma_i)$, then BP method gives a way to <em>estimate</em> the marginal probability $p(\sigma_i)$ as follows: $$p(\sigma_i)\simeq p^{t}(\sigma_i)=\prod_{a\in\partial_i}p_{a\rightarrow i}^{t-1}(\sigma_i)$$</p> <p>For <strong>trees</strong>, this iteration converges to fix point in finite time $t_{*}$, and this bound has a known value. Moreover, the method <em>provably</em> computes the marginal probabilities <em>exactly</em>. In fact, for trees this method and <strong>transfer-matrix</strong> methods used e.g. for the classical Ising spin chain turn out to be equivalent.</p> <p>If your system it is <em>not a tree</em>, you do not get exact results and the message-update iteration is not promised to converge. However, the method has been used with wide <strong><a href="http://vision.ucsd.edu/~kbranson/research/bp_pres.pdf" rel="nofollow">experimental success</a></strong> on graphs that <strong>locally-look-like-trees</strong> (this seems to set an upper bound to the correlation-distance that you can have) to provide good estimations of these marginal probabilities.</p> <p>Finally, the method can be adapted to estimate all the other quantities I mentioned.</p> <h2>Drawbacks</h2> <p>The main disadvantage of this method is that it is rather complicated to find analytical bounds for errors or analytical conditions that guarantee convergence; both are fields of current research. For a recent study regarding convergence you can check <a href="http://jmlr.csail.mit.edu/papers/v6/ihler05a.html" rel="nofollow">[1]</a>; regarding errors, I found this ones <a href="http://uai.sis.pitt.edu/displayArticleDetails.jsp?mmnu=1&amp;smnu=2&amp;proceeding_id=23&amp;article_id=1689" rel="nofollow">[2]</a>.</p> <p>And, of course, another disadvantage is that if you add a lot of random interactions to your graph, at some point your interaction-graph stops being tree-like and the method would behave poorly. In fact, there is a threshold were a gigantic connected component appears in the interaction graph <a href="http://www.stanford.edu/~montanar/RESEARCH/book.html" rel="nofollow">[3]</a>.</p>