Miyoshi, Naoto; Shigezumi, Takeya; Uehara, Ryuhei; Watanabe, Osamu Scale free interval graphs. (English) Zbl 1143.68507 Fleischer, Rudolf (ed.) et al., Algorithmic aspects in information and management. 4th international conference, AAIM 2008, Shanghai, China, June 23–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68865-5/pbk). Lecture Notes in Computer Science 5034, 292-303 (2008). Summary: Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose a natural and simple random model for generating scale free interval graphs. The model generates a set of intervals randomly, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of the generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from the most of the other models for which we need to approximate the processes by certain differential equations. We indeed show that the distribution of degrees follows power law, and it achieves large cluster coefficient.For the entire collection see [Zbl 1139.90005]. Cited in 2 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C80 Random graphs (graph-theoretic aspects) Keywords:scale free graph; small world network; interval graphs PDFBibTeX XMLCite \textit{N. Miyoshi} et al., Lect. Notes Comput. Sci. 5034, 292--303 (2008; Zbl 1143.68507) Full Text: DOI References: [1] Barabási, A.: Linked: The New Science of Networks. Perseus Books Group (2002) [2] Barabási, A.; Albert, R., Emergence of Scaling in Random Networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 [3] Cox, D. R.; Isham, V., Point Processes (1980), Boca Raton: Chapman & Hall, Boca Raton · Zbl 0441.60053 [4] Newman, M., The structure and function of complex networks, SIAM Review, 45, 167-256 (2003) · Zbl 1029.68010 · doi:10.1137/S003614450342480 [5] Miyoshi, N., Shigezumi, T., Uehara, R., Watanabe, O.: Scale Free Interval Graphs. Dept. of Math. and Comp. Sciences Tokyo Institute of Technology Research Reports (Series C), series C-255 (2008), http://www.is.titech.ac.jp/research/research-report/C/C-255.pdf · Zbl 1143.68507 [6] Takács, L., Introduction to the Theory of Queues (1962), Oxford: Oxford University Press, Oxford · Zbl 0118.13503 [7] Watts, D. J., Small Worlds: The Dynamics of Networks Between Order and Randomness (2004), Princeton: Princeton University Press, Princeton · Zbl 1046.00006 [8] Watts, D. J.; Strogatz, D. H., Collective Dynamics of ’Small-World’ Networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 · doi:10.1038/30918 [9] Wolff, R. W., Poisson Arrivals See Time Averages, Operations Research, 30, 223-231 (1982) · Zbl 0489.60096 · doi:10.1287/opre.30.2.223 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.