• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

143 submissions , 120 unreviewed
3,899 questions , 1,377 unanswered
4,835 answers , 20,496 comments
1,470 users with positive rep
495 active unimported users
More ...

  Refinements of pair approximation for network analysis

+ 9 like - 0 dislike

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, or specific average shortest-path distance (for more, see Albert & Barabasi 2001). 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 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) 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.

If the game-theoretic example is too non-physicsy, then replace the agents by spins and the call the payoff matrix an interaction Hamiltonian, then cool your system while performing periodic random measurements, and you will get another example.


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.

This post has been migrated from (A51.SE)
asked Sep 18, 2011 in Theoretical Physics by Artem Kaznatcheev (45 points) [ no revision ]
retagged Apr 19, 2014 by dimension10
Most voted comments show all comments
Could you clarify what you need the approximation for? I.e. in which properties of the network are you interested?

This post has been migrated from (A51.SE)
@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).

This post has been migrated from (A51.SE)
@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.

This post has been migrated from (A51.SE)
@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.

This post has been migrated from (A51.SE)
@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.

This post has been migrated from (A51.SE)
Most recent comments show all comments
@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.

This post has been migrated from (A51.SE)
@Artem: Don't be afraid to give an explicit example, even if it is outside of physics.

This post has been migrated from (A51.SE)

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
To avoid this verification in future, please log in or register.

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights