DISTRIBUTION OF MAXIMAL CLIQUE SIZE UNDER THE WATTS-STROGATZ MODEL OF EVOLUTION OF COMPLEX NETWORKS

In this paper, we analyze the evolution of a small-world network and its subsequent transformation to a random network using the idea of link rewiring under the well-known Watts-Strogatz model for complex networks. Every link u-v in the regular network is considered for rewiring with a certain probability and if chosen for rewiring, the link u-v is removed from the network and the node u is connected to a randomly chosen node w (other than nodes u and v). Our objective in this paper is to analyze the distribution of the maximal clique size per node by varying the probability of link rewiring and the degree per node (number of links incident on a node) in the initial regular network. For a given probability of rewiring and initial number of links per node, we observe the distribution of the maximal clique per node to follow a Poisson distribution. We also observe the maximal clique size per node in the small-world network to be very close to that of the average value and close to that of the maximal clique size in a regular network. There is no appreciable decrease in the maximal clique size per node when the network transforms from a regular network to a small-world network. On the other hand, when the network transforms from a small-world network to a random network, the average maximal clique size value decreases significantly