Generating realistic graphs is a very important tool, since this process can lead to synthetic graphs with properties that characterize real-life networks. Therefore, synthetically generated graphs can be used in performance evaluation experiments and their properties may be controlled. Moreover, generating realistic synthetic graphs helps us understand real-life graphs. Many real-life networks are scale free, have large clustering coefficients, and have a small diameter. The random model proposed in this paper is scale free and has large clustering coefficients, but does not have a small diameter.

The paper consists of six sections: “Introduction,” “Preliminaries,” “Scale Free Interval Graph Model,” “Scale Free Property,” “Clustering Coefficients,” and “Concluding Remarks.” It also includes an appendix and references.

The proposed model is applied to the generation of random interval graphs, where two vertices of G are joined with an edge if the corresponding intervals intersect. The model is based on queueing theory concepts and is applied to the generation of a set of intervals following specific probability distributions. Two parameters are taken into account: the number of intervals and the length of the intervals.

The generation process is given as an algorithm called “gen_intervals.” It has a complexity of O(n), where n is the number of intervals. It is proven that interval graphs generated by gen_intervals satisfy both the scale-free and the large clustering coefficient properties. Although the conclusion discusses the third property--small diameter or small world--further work is needed.

In summary, the proposed model is simple, intuitive, and can be implemented easily. The conclusion also mentions a very useful extension of this work: adapting the model to existing networks. In other words, given a real-life network, how can we modify the model to resemble the existing network? Such a scheme could be used to compare different models.