107. Emergence of Symmetry in Complex Networks

'The ubiquity of symmetry in disparate real-world systems suggests that it may be related to generic self-organizational principles' (MacArthur & Anderson 2006).

http://stat.kaist.ac.kr/OurWork.php

Symmetry is supreme, and real-life complex networks are no exception to this aspect of natural phenomena. Several of them are rich in symmetry, and exploring the origins of that symmetry can provide insights useful for modelling the dynamics and topology of the network (see my book Wadhawan (2011) for a literature survey on this topic. If you would like to have a free soft copy, please write to me at vkw1412@gmail.com).

http://home.physics.ucla.edu/~arisaka/home/Introduction/Consciousness/

In network theory, the ‘symmetry transformations’ under which a network remains ‘invariant’ are usually taken to be the appropriate permutations of vertices. And by ‘invariance’ we mean the invariance of the adjacency of the vertices of the network. Thus a network structure is said to possess symmetry if certain permutations of its vertices do not change the adjacency of the vertices.

Symmetry analyses of networks have led to an important result that 'similar linkage pattern' is the underlying factor responsible for the manifestation of symmetry in networks (Xiao et al. 2008).

I now introduce some formal definitions in the context of symmetry of graphs or networks. Let G be the graph underlying a network. A one-to-one mapping from the vertices of G onto itself is called a permutation. Let S(V) be the set of all the permutations possible for a set V of vertices comprising the graph G. In the set S(V) there can be some permutations which preserve the adjacency of each vertex of the set V. These permutations are called the automorphisms, acting on the set V of vertices of the graph G. The set of all automorphisms of the graph G is denoted by Aut(G).

A network is said to be symmetric if its underlying graph G has at least one automorphism which is not an identity or trivial permutation. If the identity permutation is the only automorphism of G, then the graph and the network are asymmetric.

Since permutations are mappings, one can define successive permutations or products of permutations. A product of two permutations f and g (written as fg) is another permutation h (h = fg). h is the mapping which takes the vertex set V onto itself, and this mapping has the same effect on a vertex x as if we first applied f on x (getting x^f), and then applied g on x^f (getting (x^f)^g). Thus, x^h = (x^f)^g. It can be shown that the set of automorphisms under the product of permutations forms a group, called the automorphism group.

Given the automorphism group Aut(G) for the vertex set V, we can create a partition P = {V₁, V₂, ..., V_k} such that a vertex x is equivalent to a vertex y if and only if Aut(g) contains a mapping g such that x_g = y. Such a partition is called an automorphism partition. And each cell of this partition is called an orbit of Aut(g). A trivial orbit contains only a single vertex. Otherwise it is nontrivial orbit.

The above figure is an example of a symmetric graph (Xiao et al. 2008). There are 7 vertices, so the possible number of permutations is 7!, or 5040. Clearly, the adjacency of vertex 3 is different from that of 4. So a permutation that interchanges 3 and 4, and does nothing else, is not a symmetry transformation. So it is not an automorphism of this graph. A permutation that is an example of an automorphism is that in which only vertices 1 and 2 are interchanged. Thus, vertices 1 and 2 belong to the same orbit. Similarly, the vertices 5, 6 and 7 form a subset of the graph in which any interchange is an automorphism, so these three vertices all belong to another orbit. We can find all the orbits, and write the automorphism partition as

P = {{1,2}, {3}, {4}, {5,6,7}}

Measures of symmetry of networks

If a graph is shown to be symmetric, the next question is: How symmetric is it? I describe two measures of such symmetry here (Xiao etal. 2008).

The order |Aut(G)| or α_G of the automorphism group of a graph is clearly a measure of the extent of symmetry in the graph. We should normalize it to be able to compare the symmetries of graphs of different orders N. The following is one such normalized measure of symmetry (MacArthur and Anderson 2006):

β_G = (α_G)^1/N

It is intuitively clear from the figure above that a network or graph with more nontrivial orbits is more symmetric. Xiao et al. (2008) have used a measure of symmetry which accounts for this:

γ_G = [∑_{1≤i≤k, |Vi|≥1} |V_i|] / N

Here V_i is the ith orbit in the automorphism partition, and k is the number of cells in the partition.

I have reviewed the symmetry aspect of complex networks in substantial detail in my book LATENT, MANIFEST, AND BROKEN SYMMETRY: A Bottom-up Approach toSymmetry, with Implications for Complex Networks (2011). I have argued that symmetry emerges in complex networks for the same reasons for which it arises in, say, crystals. In crystals it is 'equal placement of equal parts', and in nets it is ' similar linkage patterns'. The second law of thermodynamics for open systems is the mother of all symmetrizing and other organizing principles governing natural phenomena (cf. Part 6).

http://cnets.indiana.edu/groups/casci