The "Kawachi" algorithm: a single-parameter network constructor?

Abstract

The last decade has seen resurgence of interest in the modelling of networked phenomena. In 1999, Albert and Barabási identified "scale-free" networks as being surprisingly widespread in phenomena as wide-ranging as the World-Wide-Web, social networks, and transport networks. By then the classical random network model of Erdös and Rényi (1959) had been extended by the concept of "small world" networks (Watts and Strogatz, 1998). Constructive algorithms for networks had been proposed by various authors. Watts and Strogatz published an algorithm in which the links of an initial regular lattice are randomly "rewired" without altering the number of nodes and links. The probability of re-wiring p produces networks ranging from a regular lattice (p = 0), through small world networks, to an Erdos/Renyi random network (p = 1). Albert and Barabási devised an algorithm for evolving scale-free networks (only), based on preferential linking between nodes. The idea of a single mechanism to unify all of these kinds of networks is appealing. In 2004 researchers Kawachi, Murata, Yoshi and Kakzu proposed a constructive algorithm based on a single probability parameter p for which they claimed the range 0 >= p >= 1 would output networks ranging from a regular lattice, through small-world, to random, to scale-free. Work by the present writer intended to confirm results reported by Kawachi et al. has revealed that their claim to construct scale-free networks is limited to quite small networks; those with a total size in the order of 100 nodes. Larger, more realistic networks constructed using this algorithm reveal a substantial shortfall in the number of nodes with large connectivities. We report on the nature of the difficulties with the Kawachi et al. algorithm and examines possible solutions to problems identified.