Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Scale free interval graphs
Miyoshi N., Shigezumi T., Uehara R., Watanabe O. Theoretical Computer Science410 (45):4588-4600,2009.Type:Article
Date Reviewed: Jan 29 2010

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.

Reviewer:  Apostolos Papadopoulos Review #: CR137686 (1006-0597)
Bookmark and Share
  Reviewer Selected
 
 
Graphs And Networks (E.1 ... )
 
 
Interval Arithmetic (G.1.0 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graphs And Networks": Date
Complete inverted files for efficient text retrieval and analysis
Blumer A., Blumer J., Haussler D., McConnell R., Ehrenfeucht A. Journal of the ACM 34(3): 578-595, 1987. Type: Article
Oct 1 1988
Deformable spanners and applications
Gao J., Guibas L., Nguyen A.  Computational geometry (Proceedings of the 20th Annual Symposium on Computational Geometry, Brooklyn, New York, USA, Jun 8-11, 2004)190-199, 2004. Type: Proceedings
Sep 13 2004
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Henzinger M., King V. Journal of the ACM 46(4): 502-516, 1999. Type: Article
Mar 1 2000
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy