'

*The ubiquity of symmetry in disparate real-world systems suggests that it may be related to generic self-organizational principles*' (MacArthur & Anderson 2006).
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).

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*), and then applied^{f}*g*on*x*(getting (^{f}*x*)^{f}*). Thus,*^{g}*x*= (^{h}*x*)^{f}*. It can be shown that the set of automorphisms under the product of permutations forms a group, called the*^{g}*automorphism group*.
Given the
automorphism group Aut(

*G*) for the vertex set*V*, we can create a partition*P*= {*V*_{1},*V*_{2}, ...,*V*} such that a vertex_{k}*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*α*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_{G}*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*is the_{i}*i*th 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).*
## No comments:

## Post a Comment