<p>The way you formulate your question makes it sound like you care about dynamics, but since what you are looking for seems to be a steady state solution, ground states seem like a much more productive route to go down.</p>

<p>Since you want to go beyond pairwise approximation, the most natural candidate technique seems to be <a href="http://www.quantiki.org/wiki/Matrix_product_states" rel="nofollow">matrix product states</a>, which is a pretty hot topic at the moment for dealing with quantum ground states. The way this approach works is basically by introducing maximally entangled pairs between nodes, and at each node introducing a projector. By adding higher dimensional systems you'll capture more features of the graph. I know your problem probably isn't quantum, but I don't see why this technique still shouldn't work. You should be able to simply replace the entangled states with $\frac{1}{2}(|00\rangle \langle 00| + |11\rangle \langle 11|).$</p>

<p>Also, I'm not sure if this is the kind of thing you are looking for or not, but there are some recent results on realizibility of scale-free networks, showing that they exhibit two phase transitions which seems to have just been accepted to PRL. A preprint entitled "All scale-free networks are sparse" can be found as <a href="http://arxiv.org/abs/1106.5150" rel="nofollow">arXiv:1106:5150</a>.</p>

CC BY-SA 3.0
2011-09-18T18:05:01.800Z
2011-09-18T18:35:30.080Z
Joe Fitzsimons
<p>Two things you might want to look at:</p>

<p><a href="http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf">Algorithmic Game Theory Ch. 7 : Graphical Games</a></p>

<p><a href="http://www.santafe.edu/media/workingpapers/11-03-010.pdf">Fluctuations in Evolutionary Games</a></p>

<p>The first goes over how to find equilibria in games or spin systems like you described. Certain meta-strategies for strategy adoption (specifically the one identical to Gibbs Sampling that leads to a correlated equilibria) allow very general, tractable analyses.</p>

<p>The second attempts to predict large fluctuations or change in "norms" in an evolutionary game theory model using large deviations theory. The examples tackled are small-scale, but the author attempts to make the mathematical machinery he uses as general and powerful as possible, so it may be applicable to your case.</p>

CC BY-SA 3.0
2011-10-05T07:42:29.223Z
2011-10-05T07:42:29.223Z
Elliot JJ
<p>In general, you may be interested in spectral methods in graph theory, as they are a powerful tool. You can analyze the eigenvalues of adjacency matrix of the graph (or of the <a href="http://en.wikipedia.org/wiki/Laplacian_matrix">Laplacian matrix of the graph</a>).  </p>

<p>Such methods not only take into account local properties of the graph (e.g. degree distribution) but also global (e.g. connectivity, presence or absence of shortcuts). In particular, the spectrum is directly related to number of pairs, triangles and to the shortest path (see the second reference).</p>

<p>As a reference (I only skimmed through them, but they look useful):</p>

<ul>
<li>S. Boccaletti et al. (Phys Rep 2006), <a href="http://dx.doi.org/10.1016/j.physrep.2005.10.009">Complex networks: Structure and dynamics</a> (or <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.7590&amp;rep=rep1&amp;type=pdf">here</a>)</li>
<li>K.-I. Goh et at. (PRE 2001), Spectra and eigenvectors of scale-free networks, <a href="http://arxiv.org/abs/cond-mat/0103337">arXiv:cond-mat/0103337</a></li>
</ul>

CC BY-SA 3.0
2011-09-19T08:47:58.320Z
2011-09-19T09:13:49.850Z
Piotr Migdal
<p>When considering interactions on networks, it is usually very hard to calculate the dynamics <strong>analytically</strong>, and approximations are employed. Mean-field approximations usually end up ignoring the network structure completely, and so are seldom a good approximation. A popular approximation is the pair approximation, which considers the correlations inherent between adjacent nodes (intuitively we can think of it as a type of mean-field approximation on edges).</p>
<p>The approximation is exact if we are considering Cayley graphs, and very good if we are looking at <span class="math-container">$k$</span>-regular random graphs. In practice it also provides good approximations for cases when we have a random graph with average degree <span class="math-container">$k$</span> and a tight distribution of degree around <span class="math-container">$k$</span>. Unfortunately, a lot of the networks and interactions that are of interest, are not well modeled by these sort of graphs. They are usually well-modeled by graphs with very different degree distributions (like scale-free networks, for instance), with specific (and high) <a href="http://en.wikipedia.org/wiki/Clustering_coefficient" rel="nofollow noreferrer">clustering coefficients</a>, or specific average shortest-path distance (for more, see <a href="http://arxiv.org/abs/cond-mat/0106096" rel="nofollow noreferrer">Albert &amp; Barabasi 2001</a>).</p>
<p><strong>Are there refinements of pair approximation that work well for these types of networks? Or are there other analytic approximations available?</strong></p>
<hr />
<h3>An example of interactions on networks</h3>
<p>I thought I would give an example of what I mean by interactions on networks. I will include a relatively general example from evolutionary game theory.</p>
<p>You can think of each node as an agent (usually represented just by a strategy), that plays some fixed game pairwise with each other agent it has an edge to. Thus, a given network with a some assignment of strategy to each node produces a payoff for each node. We then use these payoffs and the network structure to determine the distribution of strategies among the nodes for the next iteration (A common example might be for each agent to copy the neighbor with the highest payoff, or some probabilistic variant of this). The questions we are usually interested in corresponding to knowing the numbers of agents of each strategy and how that changes overtime. Often we have stable distribution (which we then want to know, or approximate) or sometimes limit-cycles or even more exotic beasts.</p>
<p>If we do mean-field approximation on this sort of model, we use get the <a href="http://en.wikipedia.org/wiki/Replicator_equation" rel="nofollow noreferrer">replicator equation</a> as our dynamic, which blatantly ignores the network structure and is only accurate for complete graphs. If we use pair approximation (as <a href="http://www.sciencedirect.com/science/article/pii/S0022519306002426" rel="nofollow noreferrer">Ohtsuki &amp; Nowak 2006</a>) we will get slightly different dynamics (it will actually be replicator dynamics with a modified payoff matrix, where the modification depends on the degree of the graph, and the specifics of the update step) which matches simulation well for random graphs, but not for other networks of interest.</p>
<p>For a more physics like example: replace the agents by spins and the call the payoff matrix an interaction Hamiltonian, then cool your system while performing periodic random measurements.</p>
<h3>Notes and related questions</h3>
<ul>
<li><p>Straightforward generalizations of pair approximation of the sort that consider a type of mean-field approximation on triples, or quadruples of nodes) are unwieldy and still don't take into account very different degree distributions or average shortest-path distance.</p>
</li>
<li><p><a href="https://cstheory.stackexchange.com/q/7286/1037">Sources for Algorithmic Evolutionary Game Theory</a></p>
</li>
</ul>

CC BY-SA 3.0
2011-09-18T16:08:29.630Z
Could you clarify what you need the approximation for? I.e. in which properties of the network are you interested?
Piotr Migdal
CC BY-SA 3.0
2011-09-18T16:13:58.250Z
@Piotr I am interested in tools that can be used for graphs with various degree distributions (but at least scale-free) and where the analysis explicitly takes into account clustering coefficient and average shortest-path distance between nodes. In particular, it is desired for the tool to depend on those parameters (most pair approximation only depends on average degree, and sometimes standard error of the degree-spread for tight distributions).
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-18T16:29:37.303Z
@Artem: One method is to calculate graph spectrum (i.e. [spectrum of its Laplace matrix](http://mathworld.wolfram.com/GraphSpectrum.html)). The spectrum is related to the degree distribution, but also depends on clustering and (I guess)  average shortest-path distance between nodes.
Piotr Migdal
CC BY-SA 3.0
2011-09-18T16:30:28.530Z
@Artem: I'm not entirely clear on what you want to be able to calculate/approximate. Obviously any approximation will fail to accurately represent all aspects of the graph, so it is important to know what functions of the graph you care about. There are lots of CMP methods that can be brought to bare, but you can always construct a property for which they will fail.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-18T16:33:39.827Z
@JoeFitzsimons I see where I am missing the mark. I have taken for granted that people would guess what I mean by dynamics. I will make a quick note about the type of dynamics I am interested in.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-18T16:36:13.577Z
@Artem: Do you mean something like the tight-binding model? The dynamics are only defined once you have a Hamiltonian or probabilistic transition for the system, and without defining what that means, its hard to see how you'll get a meaningful answer.
Joe Fitzsimons
CC BY-SA 3.0
2011-09-18T16:51:33.600Z
@JoeFitzsimons I gave an example. The goal isn't to solve a specific system, but to find out if there are better tools (than just pair approximation or mean-field sort of things) that would work in some cases. Unfortunately, the more I define the problem, the less physics-y it becomes, becomes my actual motivation comes from outside physics. However, most of the best approximation come directly from physics (such as pair approximation) so there is definitely theoretic methods that can be borrowed. Hopefully the example I gave will make the question easier to understand.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-18T16:53:26.533Z
@JoeFitzsimons I haven't had a chance to really immerse myself in TP.SE yet, so I might be a little off-keel on making my questions easy to understand. Any help is appreciated.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-18T17:16:01.100Z
@Artem: Don't be afraid to give an explicit example, even if it is outside of physics.
Piotr Migdal
CC BY-SA 3.0
2012-04-29T15:31:13.670Z
This question was migrated from TP.SE since that site is closing. Here is the [relevant meta discussion](http://meta.cstheory.stackexchange.com/q/1518/1037) about the scope of this question.
Artem Kaznatcheev
<graph-theory><gt.game-theory><evolutionary-game-theory>
Refinements of pair approximation for network analysis
Artem Kaznatcheev
# Refinements of pair approximation for network analysis

(Asked by: username_0 on 2011-09-18)

When considering interactions on networks, it is usually very hard to calculate the dynamics **analytically**, and approximations are employed. Mean-field approximations usually end up ignoring the network structure completely, and so are seldom a good approximation. A popular approximation is the pair approximation, which considers the correlations inherent between adjacent nodes (intuitively we can think of it as a type of mean-field approximation on edges).

The approximation is exact if we are considering Cayley graphs, and very good if we are looking at $k$-regular random graphs. In practice it also provides good approximations for cases when we have a random graph with average degree $k$ and a tight distribution of degree around $k$. Unfortunately, a lot of the networks and interactions that are of interest, are not well modeled by these sort of graphs. They are usually well-modeled by graphs with very different degree distributions (like scale-free networks, for instance), with specific (and high) [clustering coefficients](http://en.wikipedia.org/wiki/Clustering_coefficient), or specific average shortest-path distance (for more, see [Albert & Barabasi 2001](http://arxiv.org/abs/cond-mat/0106096)).

**Are there refinements of pair approximation that work well for these types of networks? Or are there other analytic approximations available?**

---

### An example of interactions on networks

I thought I would give an example of what I mean by interactions on networks. I will include a relatively general example from evolutionary game theory.

You can think of each node as an agent (usually represented just by a strategy), that plays some fixed game pairwise with each other agent it has an edge to. Thus, a given network with a some assignment of strategy to each node produces a payoff for each node. We then use these payoffs and the network structure to determine the distribution of strategies among the nodes for the next iteration (A common example might be for each agent to copy the neighbor with the highest payoff, or some probabilistic variant of this). The questions we are usually interested in corresponding to knowing the numbers of agents of each strategy and how that changes overtime. Often we have stable distribution (which we then want to know, or approximate) or sometimes limit-cycles or even more exotic beasts.

If we do mean-field approximation on this sort of model, we use get the [replicator equation](http://en.wikipedia.org/wiki/Replicator_equation) as our dynamic, which blatantly ignores the network structure and is only accurate for complete graphs. If we use pair approximation (as [Ohtsuki & Nowak 2006](http://www.sciencedirect.com/science/article/pii/S0022519306002426)) we will get slightly different dynamics (it will actually be replicator dynamics with a modified payoff matrix, where the modification depends on the degree of the graph, and the specifics of the update step) which matches simulation well for random graphs, but not for other networks of interest.

For a more physics like example: replace the agents by spins and the call the payoff matrix an interaction Hamiltonian, then cool your system while performing periodic random measurements.

### Notes and related questions

* Straightforward generalizations of pair approximation of the sort that consider a type of mean-field approximation on triples, or quadruples of nodes) are unwieldy and still don't take into account very different degree distributions or average shortest-path distance.
* [Sources for Algorithmic Evolutionary Game Theory](https://cstheory.stackexchange.com/q/7286/1037)

**Tags:** graph-theory, gt.game-theory, evolutionary-game-theory
> **Comments:**
> **username_1**: Could you clarify what you need the approximation for? I.e. in which properties of the network are you interested?  
> **username_0**: @Piotr I am interested in tools that can be used for graphs with various degree distributions (but at least scale-free) and where the analysis explicitly takes into account clustering coefficient and average shortest-path distance between nodes. In particular, it is desired for the tool to depend on those parameters (most pair approximation only depends on average degree, and sometimes standard error of the degree-spread for tight distributions).  
> **username_1**: @Artem: One method is to calculate graph spectrum (i.e. [spectrum of its Laplace matrix](http://mathworld.wolfram.com/GraphSpectrum.html)). The spectrum is related to the degree distribution, but also depends on clustering and (I guess)  average shortest-path distance between nodes.  
> **username_2**: @Artem: I'm not entirely clear on what you want to be able to calculate/approximate. Obviously any approximation will fail to accurately represent all aspects of the graph, so it is important to know what functions of the graph you care about. There are lots of CMP methods that can be brought to bare, but you can always construct a property for which they will fail.  
> **username_0**: @JoeFitzsimons I see where I am missing the mark. I have taken for granted that people would guess what I mean by dynamics. I will make a quick note about the type of dynamics I am interested in.  
> **username_2**: @Artem: Do you mean something like the tight-binding model? The dynamics are only defined once you have a Hamiltonian or probabilistic transition for the system, and without defining what that means, its hard to see how you'll get a meaningful answer.  
> **username_0**: @JoeFitzsimons I gave an example. The goal isn't to solve a specific system, but to find out if there are better tools (than just pair approximation or mean-field sort of things) that would work in some cases. Unfortunately, the more I define the problem, the less physics-y it becomes, becomes my actual motivation comes from outside physics. However, most of the best approximation come directly from physics (such as pair approximation) so there is definitely theoretic methods that can be borrowed. Hopefully the example I gave will make the question easier to understand.  
> **username_0**: @JoeFitzsimons I haven't had a chance to really immerse myself in TP.SE yet, so I might be a little off-keel on making my questions easy to understand. Any help is appreciated.  
> **username_1**: @Artem: Don't be afraid to give an explicit example, even if it is outside of physics.  
> **username_0**: This question was migrated from TP.SE since that site is closing. Here is the [relevant meta discussion](http://meta.cstheory.stackexchange.com/q/1518/1037) about the scope of this question.  

---

## 3 answers

### Answer by username_1 on 2011-09-19. Score: 7 | Accepted answer

In general, you may be interested in spectral methods in graph theory, as they are a powerful tool. You can analyze the eigenvalues of adjacency matrix of the graph (or of the [Laplacian matrix of the graph](http://en.wikipedia.org/wiki/Laplacian_matrix)).

Such methods not only take into account local properties of the graph (e.g. degree distribution) but also global (e.g. connectivity, presence or absence of shortcuts). In particular, the spectrum is directly related to number of pairs, triangles and to the shortest path (see the second reference).

As a reference (I only skimmed through them, but they look useful):

* S. Boccaletti et al. (Phys Rep 2006), [Complex networks: Structure and dynamics](http://dx.doi.org/10.1016/j.physrep.2005.10.009) (or [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.7590&rep=rep1&type=pdf))
* K.-I. Goh et at. (PRE 2001), Spectra and eigenvectors of scale-free networks, [arXiv:cond-mat/0103337](http://arxiv.org/abs/cond-mat/0103337)


---

### Answer by username_2 on 2011-09-18. Score: 8

The way you formulate your question makes it sound like you care about dynamics, but since what you are looking for seems to be a steady state solution, ground states seem like a much more productive route to go down.

Since you want to go beyond pairwise approximation, the most natural candidate technique seems to be [matrix product states](http://www.quantiki.org/wiki/Matrix_product_states), which is a pretty hot topic at the moment for dealing with quantum ground states. The way this approach works is basically by introducing maximally entangled pairs between nodes, and at each node introducing a projector. By adding higher dimensional systems you'll capture more features of the graph. I know your problem probably isn't quantum, but I don't see why this technique still shouldn't work. You should be able to simply replace the entangled states with $\frac{1}{2}(|00\rangle \langle 00| + |11\rangle \langle 11|).$

Also, I'm not sure if this is the kind of thing you are looking for or not, but there are some recent results on realizibility of scale-free networks, showing that they exhibit two phase transitions which seems to have just been accepted to PRL. A preprint entitled "All scale-free networks are sparse" can be found as [arXiv:1106:5150](http://arxiv.org/abs/1106.5150).


---

### Answer by username_3 on 2011-10-05. Score: 5

Two things you might want to look at:

[Algorithmic Game Theory Ch. 7 : Graphical Games](http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf)

[Fluctuations in Evolutionary Games](http://www.santafe.edu/media/workingpapers/11-03-010.pdf)

The first goes over how to find equilibria in games or spin systems like you described. Certain meta-strategies for strategy adoption (specifically the one identical to Gibbs Sampling that leads to a correlated equilibria) allow very general, tractable analyses.

The second attempts to predict large fluctuations or change in "norms" in an evolutionary game theory model using large deviations theory. The examples tackled are small-scale, but the author attempts to make the mathematical machinery he uses as general and powerful as possible, so it may be applicable to your case.


---

