A Study of NK Landscapes’ Basins and Local Optima Networks
A second important aspect in the study of networks has been the realization that in many real-world networks, the distribution of the number of neighbours (the degree distribution) is typically right-skewed with a "heavy tail", meaning that most of the nodes have less-than-average degree whilst a small fractions of hubs have a large number of connections. These qualitative description can be described mathematically by a power-law [1], which has the asymptotic form p(k) k− . This means that the probability of a randomly chosen point having a degree k decays like a power of k, where the exponent (typically in the range [2, 3]) determines the rate of decay. A distinguishing feature of power-law distributions is that when plotted on a double logarithmic scale, a powerlaw appears as a straight line with negative slope . This behavior contrasts with a normal distribution which would curve sharply on a log-log plot, such that the probability of a node having a degree greater than a certain "cutoff" value is nearly zero. The mean would then trivially represent a characteristic scale for the network degree distribution. Since networks with power-low degree distribution lack any such cutoff value, at least in theory, they are often called scale-free networks [20]. Examples of such scale-free networks are the world-wide-web, the internet, scientific collaboration and citation networks, and biochemical networks.