# which areas in physics overlap with those of social network theory for the analysis of the graphs?

I am studying social networks in terms of graph theory and linear algebra. I know that physicists have published and worked alot in this field. This causes me to assume that there are sub-fields in physics which overlap in the essence of their problems with those of small world networks. Which natural phenomenon exhibit these kind of features similar to small world networks?

I would like to know so maybe I can look at those problems to get inspiration that can be taken to social network theory.

Best,

-
I think about the field of neural networks, which in physics builds further on more complicated versions of Ising models and spin glass models. Also, in the study of the spread of diseases many results and models from physics are used. In general, I would say statistical mechanics. – Raskolnikov Dec 12 '10 at 22:22
Have you had a look at the Barabasi-Albert paper in Review of Modern Physics, titled Statistical mechanics of complex networks? This is one of the canonical references in this field. If you're working on social networks this is a must read. It has over 7000 citations. – user346 Dec 12 '10 at 22:56
II think you should rewrite the question so as to remove most of your references to social network theory or change the title. It seems that what you really want to know is "why are physicists inteested in graph theory and linear algebra? what physical problems do they solve?" So your plan is to tranpsort physics problems to social network theory? – Sean Tilson Dec 13 '10 at 5:25
Spectral graph theory is highly relevant to both of these fields. – Noldorin Dec 13 '10 at 21:37

If there is a subfield in physics that studying network, the closest one must be the statistical mechanics, and the second should be the soft condensed matter physics. In my opinion, there are three main branches of network study.

## Part 1: Study of interaction in network

For this area of study, the focus is the equilibrium state and the statistical mechanics properties. Strong correlation between elements can often give rise to emergent behaviors that do not appear in the underlying system. If there are no interaction, these phenomena cannot occurs because the resulting system is only the sum of individual part. Therefore, the network of interacting elements is important, and indeed, the precise structure of the network can determine whether the emergence phenomenon exist or not.

For a given problem in statistical physics, we can write down the Hamiltonian of the system, say, Ising model

$\mathcal{H}=-\sum_{i,j} A_{ij} J_{ij}\sigma_{i}\sigma_{j}-h\sum_{i}\sigma_{i}$

where the $\sigma_{i}$ represents state (spin here) of a node and the $A_{ij}$ is the adjacency matrix of the network. Note that $A_{ij}$ can have the topology of simple square lattice, or a complex network with non-local linkage. Using this Hamiltonian, we can write down the corresponding partition function $Z = \sum_i {exp(-\beta \mathcal{E_i})}$, which allows us to find the set of standard macroscopic properties. In statistical mechanics, this model is interesting because it is the first model showing the phase transition and the critical phenomenon. This model also show different behaviour when the topology is a complex network.

Within all properties, the most important one is the ground state and its energy because their roles in physics and they are always defined for all system. Furthermore, there is another reason for non-physics problem: the relationship with the optimization problem.

It is obvious that finding the ground state is an optimization problem because we need to find a state that has minimum energy. Hence, it is related to, say, the minimizing of overall error in supervised learning or maximizing the some type of cost function in financial market. An example of optimization problem is the community detection of network, which classify each state as one community by minimizing the Hamiltonian.

In particular, most NP-complete problem also define an optimization problem. And some of them can be mapped (polynomial time reduction) directly to problems in the statistical mechanics, such as the problem of finding ground state of antiferromagnetic Ising model and MAXCUT problem in graph theory. (see review Critical phenomena in complex networks)

Returning to the question of why the network topology can significantly change the problem, here is an example: An antiferromagnetic Ising model on a square lattice (a bipartite network) has a simple unique ground state such that all nodes has spin opposite to its neighbor. However, if we consider the model defined on a triangular lattice, the ground state is nondegenerate and the state can change easily because of the frustration of the neighboring spin. For this type of topology or other complex network, the finding of ground state a highly non-trivial task.

Idea in statistical mechanics can also be apply to other problems. The idea of entropy (complexity) can possibly explain why a problem is hard to solve sometimes, but easy in other case when network topology is changed. The idea of temperature in statistical mechanics also benefit the study of randomized algorithm for optimization problems. The most obvious one is the Monte Carlo algorithm for finding ground state. In real world, if the truly optimized solution cannot be found, suboptimal solution is usually acceptable. The energy landscape of the problem can usually give an insight of the problem itself and an estimate of true ground state and the accessibility of the ground state.

Under construction...

-
 Hm, this answer talks about lots of random stuff from statistical physics at the same time and I fail to see any important connections; especially the part about entropy and temperature looks really contrived. But if the answer is improved, I am willing to give +1. – Marek Dec 14 '10 at 12:29 I will improve the presentation later when i have time. – hwlau Dec 14 '10 at 12:36