Three algorithms for analyzing fractal software networks

LOCCI, MARIO FRANCO;Concas G;TONELLI, ROBERTO;Turnu I.

2010-01-01

---

Abstract

In this work we propose an algorithm for computing the fractal dimension of a software network, and compare its performances with two other algorithms. Object of our study are various large, object-oriented software systems. We built the associated graph for each system, also known as software network, analyzing the binary relationships (dependencies), among classes. We found that the structure of such software networks is self-similar under a length-scale transormation, confirming previous results of a recent paper from the authors. The fractal dimension of these networks is computed using a Merge algorithm, first devised by the authors, a Greedy Coloring algorithm, based on the equivalence with the graph coloring problem, and a Simulated Annealing algorithm, largely used for efficiently determining minima in multi-dimensional problems. Our study examines both efficiency and accuracy, showing that the Merge algorithm is the most efficient, while the Simulated Annealing is the most accurate. The Greeding Coloring algorithm lays in between the two, having speed very close to the Merge algorithm, and accuracy comparable to the Simulated Annealing algorithm.