Computing the fractal dimension - A global metrics for large software systems

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

2010-01-01

---

Abstract

A software system can be associated to a graph - called software network - whose nodes are the software modules (for instance, the classes in Object-oriented systems), and edges are the dependencies between modules. A recent paper demonstrated that the structure of software networks is also self-similar under a length-scale transformation, and calculated their fractal dimension using the "box counting" method. In this paper, we focus on describing and evaluating alternative approaches for the computation of the fractal dimension of networks. We show that a Merge Algorithm is the most efficient, while Simulated Annealing is the most accurate. However, the Greedy Coloring algorithm, based on the equivalence of the box counting problem with the graph coloring problem, looks the best compromise, having speed comparable to MA, and accuracy comparable with SA