Software Engineering and Scale-Free Networks$^{\ast}$

Abstract

Complex-network theory is a new approach in studying different types of large systems in both the physical and the abstract worlds. In this paper, we have studied two kinds of network from software engineering: the component dependence network and the sorting comparison network (SCN). It is found that they both show the same scale-free property under certain conditions as complex networks in other fields. These results suggest that complex-network theory can be a useful approach to the study of software systems. The special properties of SCNs provide a more repeatable and deterministic way to study the evolution and optimization of complex networks. They also suggest that the closer a sorting algorithm is to the theoretical optimal limit, the more its SCN is like a scale-free network. This may also indicate that, to store and retrieve information efficiently, a concept network might need to be scale-free.