What's currently called Complexity Science suffers from an unfortunate lack of consensus as to what is meant by these terms. A review of the common notions shows a field mined by controversies, with as many frameworks for the study of Complex Systems as there are authors who propose a generic one. This document is thus not an attempt to create yet another framework, but rather an application of the traditional scientific methodology to some Complex Systems in the domain of Computer Science. It is a demonstration that even for this field, the concrete application of predictive experiments set up to challenge the extent of the main notions proves fruitful. Moreover the tools and methods that are created along the way because they were necessary to carry on experiments represent by themselves an opportunity for making progress in the domain. This is precisely the case in the present Computer Science context in the form of new algorithms, that were successfully applied to the main experiments. Hence this work is both a call for a more classical and practical approach to Complexity, and a concrete application example for that call.