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 networksI 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.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 questionsStraightforward 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
Refinements of pair approximation for network analysis
graph theory;gt.game theory;evolutionary game theory
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).  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 (or here)K.-I. Goh et at. (PRE 2001), Spectra and eigenvectors of scale-free networks, arXiv:cond-mat/0103337