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 a lot 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 phenomena exhibit these kind of features similar to small world networks?

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

-
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
Related: physics.stackexchange.com/q/1876 –  hwlau Feb 15 at 5:21

1 Answer

The concept of network is very general and can be applied to many physical, biological, neuronal, technological and social phenomenon. Any system with distinguishable individual parts interacting with each other can be described by a type of network. With its applicability to many real world problem, a whole individual research field called network science has appeared recently. Therefore, it is not surprising that social network theory is related to theory of some physics system. Though most people's understanding of network is in the context of the Internet and social network, the quantitative description of network is originated from Mathematics and Physics, which are eventually exported to other research area.

The research field in physics involving extensive use of network is statistical mechanics. One of the reason is that networks can be described by the tools of statistical mechanics and some networks can be formulated as a problem in statistical mechanics. Another reason is that the network structure can change dramatically the physical properties of the system, thereby, affect the observable, the critical phenomena and the phase transition. The relation between network and physics will be discussed after the introduction of the network type and research. Examples will also be given below including few non-trivial example with quantum system and laser.

Type of networks and its use in physics

Formally, a network $G$ is defined as a pair $G = (V,E)$ in which $V$ is a set of $N$ nodes, and $E = \{(u,v): u,v\in V\}$ is a set of $M$ edges connecting node. The connection can also be described by adjacency matrix $A$, where $A_ij = 1$ if $(i,j)\in V$ and $0$ otherwise. There are various type of networks that are often studied:

1. Lattice: Each node is connected to all its local nearest neighbor. It can be defined in dimension $d=1,2,3,...$, and it can have different lattice topology such as triangular, square, hexagonal and diamond like. Typical solid in physics can be modelled by this type of network.

2. Tree: A tree is a network in which there are no loops. When one of the node is removed, the tree will be split into two tree. In particular, the Bethe lattice is an infinite tree, and effective $d=\infty$ lattice, in which each node have degree $k$. Since all nodes in Bethe lattice are equivalent, the solution can usually be obtained in a self-consistent way. It is often study in physics because above the upper critical dimension, the model can be effectively described by mean-field and loopless graph.

3. Classical random graph: The commonly studied network is called Erdős–Rényi (ER) model $G_{nm}$, in which there are $n$ nodes and $m$ edges that connect any two nodes randomly Each link between each pair has a given probability $p$ to connect with each other. It is one of the earliest graph theory describing the global connection between nodes. Analysis one this network is relatively easy compared with other since nodes can be considered uncorrelated.

4. Small world network: This type of network is characterized by the scaling of average node separation $L\sim log(N)$ in compared with $L\sim N^{-d}$ for lattice. The standard model is Watts and Strogatz (WS) model. With the underlying lattice structure, random non-local connection is added with a given probability $p$. Compared with random graph, this mechanism guarantee the resulting network is connected even $p$ is very small.

5. Scale free network: In most real world network, the degree distribution follow a power law $P(k)\sim k^{-a}$ (i.e. scale free in $k$). Barabási–Albert (BA) model is a simple model to explain this phenomenon with preferential attachment. It is constructed by adding nodes one by one, with $m$ new links connected to existing node probability proportional $k_i/(\sum_k k_j)$ to the existing degree.

6. Fractal: It is the structure exhibiting self-similarity in different length scale. In the context of network embedded in $d$-dimension, it can be defined by the scaling $N\sim r^{d_f}$ where $d_f$ is called Fractal dimension. In physics, it is usually studied in the situation with some types of porous, deflect or disordered media.

The studied for the last three type of networks is relatively recently since the use of computer make the analysis of large random networks possible. There are also other less studied type of networks, such as constructing network from a given real degree distribution function, regular random network with all node with same degree, and lattice neither local nor complete global connection.

Research focus of networks

There are some different research focus while people talking about the study of networks:

1. Network structure and properties: It focuses on different (statistical) methods to quantity a given network, including the local properties such as size $N$, average degree $\langle k \rangle$, clustering coefficient $c$ and diameter, also, the structural properties such as size of largest component, number of components and eigenvalues. New properties are constantly being proposed. These properties can be used to classify different networks, or studied how resilience of the networks under attack, etc. There are already hundreds of different real world networks studied range from metabolic, epidemic to citation to WWW.

2. Mechanism of constructing networks: The focus is to find out the underlying mechanism, and to construct networks with particular properties such as degree distribution. It is usually purely theoretically network study, but the mechanism can originate from physical processes.

3. Evolving network: The network $G(t)=(V(t),E(t))$ itself can be evolving over time $t$, so the properties can depends on time $\langle k(t) \rangle$. Examples include growing network, or networks with edges rewiring, addition or deletion.

4. Interactions on network: The interaction and the dynamics between individual system are largely affected by structure $A$ of system in a non-trivial way. This is the one that is mostly related to physics, since physics problem are defined on the networks. See below.

5. Non standard network: For example, an edge of a network can be attached to 1 node or more nodes, rather than 2 nodes. Recently, there is some studies of Interdependent network (network of network, the nodes in different network are governed by different rules). leads to first order phase transition.

Note that few research focus can be studied at the same time, such as studying some dynamics on a evolving network. The standard review paper [1] has many details on the first three focuses, while [2] are discussing more on the physics side such as the phase transition.

[1] Albert and Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 47–97 (2002) [arxiv:0106096.pdf]

[2] Dorogovtsev, Goltsev and Mendes, Critical phenomena in complex networks, Rev. Mod. Phys. 80, 1275–1335 (2008) [arxiv:0705.0010]

Use of network in statistical mechanics

For a physics problem, the exact local topology of the lattice is not important. It is because the physics of critical phenomenon near phase transition is the same, as explained by the renormalization group theory.

This, however, can be changed with different network structure, say the phase transition from second order to infinite order. Therefore, it is interesting to understand what exactly underlying mechanism changes the physics.

The control parameters, say $p$ of WS network, of a network can be used the same way as thermodynamic variables, such as $P,V,T$. In case of randomness involved, we can define the ensemble of network $\mathcal{G}$ that includes all possible realization with $p$. When we calculate the observable or the order parameter, such as the cluster size or the magnetization, the quantity is calculated by the weighted average of all these networks ensemble in $\mathcal{G}$.

For the above definition to be useful, the observable itself must be related to the control parameters, or the network properties, and it does in most situation. All model in lattice can be re-studied in general networks and the physical phenomenon is usually changed depending on the type of networks which signify the importance of the structure of the networks.

Specific problem and relation to physics

There are already various use of network in physics to represent physical concepts and technique such as Feynman diagram and various expansion, but there are more non-trivial case. There are even more use in applied mathematics, such as game theory and epidemic, and the examples below are on those with physical origin (Note: Choice of examples are subjected to my understanding):

Ising model: This is one of the simplest mathematical model developed to explain the magnetic ordering of real magnet. The general model is described by: $$\mathcal{H}=-\sum_{i,j} A_{ij} J_{ij}\sigma_{i}\sigma_{j}-\sum_{i}h_{i}\sigma_{i} \tag{1}$$ where $h_i$ defines the site specific interaction, and $J_{ij}$ defines the interaction between any two nodes. This model can also describe the cooperation in real social network.

Since this model can show non-trivial critical phenomenon though its simplicity, so it is usually used to test different theory and assumption. A network with diameter $\ln(N)$ is usually considered similar to infinite dimension lattice. However, the results of phase transition for some networks cannot be described by a simple mean field in which lattice can. It suggests that the thermal dynamic properties depends on network structure. The variation of this model in various network dynamics such as growing network is less known. See [2] for the very details review on this it.

Finding the ground state of Eq. (1) is a very non-trivial problem in general. In particular in the case of spin glass, the frustration in the interaction results in large amount of ground state with equal energy (except spin symmetry), and so residual entropy is large than 1. The frustration is very sensitive to network structure. Considering the following example: For a bipartite network, the ground state is to assign spin to each part with one of the spin. However, introduction of a local triangle will create a frustration on it, and it can grow exponential as the triangle (or clustering coefficient) increase. Therefore, most standard algorithm to find the ground state will fail since the energy landscape is complicated in a complex network.

Bose-Einstein Condensate and network: Each node $i$ of the network can be assigned with an energy $\epsilon_i = -\frac{1}{\beta} \ln(\eta)$. Therefore, the role of $\eta = exp(-\beta \epsilon)$ play the same role as Boltzmann factor. While new nodes are adding to the network, it prefers to attach to lower energy state, or high fitness node. This can be controlled by the temperature, and at low temperature, a single node can have hugh amount of links similar to the BEC transition. Details of this evolving network are described in Phys. Rev. Lett. 86, 5632–5635 (2001)

Laser and neural network: The non-linear coupling of laser can be used to test for various complex phenomenon such as chaos. The interaction between laser can be described by networks. In particular, the problem of synchronization between between different laser nodes is similar to the synchronization of neural network as both of them can be described by the Kuramoto oscillators in some regime. So, it suggests the simulation of brain by laser system. See Rev. Mod. Phys. 85, 421–470 (2013) for short discussion.

Quantum walk: Quantum walk can be used in quantum computation. Compared with classical walk, interference can exist when the walker is inside the network. Therefore, it is possible to obtain different quantum state at different nodes for different complex network, which is an interesting phenomenon. In particular, with suitable choice of network structure, it is possible to have destructive interference at all nodes except few of them, thereby obtain particular quantum state. For example, the scattering in network can create a phase gate.

Physical quantities of network: There are a set of quantities of network structure that are directly related to physics. These are fractal dimension $d_f$ which scale as $N\sim r^{d_f}$, random walk dimension $d_w$ which scale with time $t$ as $\langle r \rangle \sim t^{1/d_w}$, spectral dimension $\bar{d}$ which the probability of walker staying at origin scale as $c(0,t)\sim t^{-\bar{d}}$, and resistivity exponent $\zeta$ in which electrical resistivity scale as $\rho(r) \sim r^\zeta$. These are related with each other (see Phys. Rev. Lett. 103, 020601 (2009)) and is regarded as physical properties of a network.

Ground state and community detection: A community in network is the group of nodes that is strongly linked with each other, while keep those node with less links outside. It has been demonstrated that communities of a network can be found by the Hamiltonian in Eq. (1) or the equivalent Potts model with $\sigma_i$ indicates the group index of node $i$. See Phys. Rev. E 74, 016110 (2006) for details.

Fig. Community of arxiv cond-mat coauthorship network. Adjacency matrix.

Optimization problem and the use of quantum annealing: There are questions about why do people want to study physical system with complex network structure, and what is the use of the technique? One of the reason is that finding the ground state in Eq. (1) is an optimization problem. In fact, it defines a pretty general optimization for many real world problem. In practice, we usually want to know a suboptimal or approximate solution by trading off the computational time. The advance in technique of finding ground state in physical system like Eq. (1) can provide a better tools for solving many real world problem.

Therefore, there are actual motivation about building a physical system that have complex network structure and let the system to cool down find the ground state. An practice machine is the D wave quantum annealer which solve the exact problem in the form of Eq. (1). In order to use it, understanding of Eq. (1) is required and the mapping need to be found between them. As shown there, a long list of optimization problem includes protein folding, object detection, to community detection and solving conflict in timetable. This suggests some mathematical/biology/social problem can be directly simulated by physical systems.

-
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