A complementary view on the growth of directory trees

摘要

Trees are a special sub-class of networks with unique properties, such as the level distributionwhich has often been overlooked. We analyse a general tree growth model proposed by Klemm et al. [Phys.Rev. Lett. 95, 128701 (2005)] to explain the growth of user-generated directory structures in computers.The model has a single parameter q which interpolates between preferential attachment and randomgrowth. Our analysis results in three contributions: first, we propose a more efficient estimation methodfor q based on the degree distribution, which is one specific representation of the model. Next, we introducethe concept of a level distribution and analytically solve the model for this representation. This allows for analternative and independent measure of q. We argue that, to capture real growth processes, the q estimationsfrom the degree and the level distributions should coincide. Thus, we finally apply both representationsto validate the model with synthetically generated tree structures, as well as with collected data of userdirectories. In the case of real directory structures, we show that q measured from the level distribution areincompatible with q measured from the degree distribution. In contrast to this, we find perfect agreementin the case of simulated data. Thus, we conclude that the model is an incomplete description of the growthof real directory structures as it fails to reproduce the level distribution. This insight can be generalisedto point out the importance of the level distribution for modeling tree growth.