Scale free interval graphs

详细信息    查看全文

• 作者：Naoto Miyoshi ; Takeya Shigezumi ; Ryuhei Uehara ; Osamu Watanabe
• 关键词：Scale free network ; Clustering coefficient ; Interval graphs ; Immigration– ; death process
• 刊名：Theoretical Computer Science
• 出版年：2009
• 出版时间：28 October 2009
• 年：2009
• 卷：410
• 期：45
• 页码：4588-4600
• 全文大小：711 K

文摘

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 under a certain distribution, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from many other models. Based on such arguments, we show for our random interval graph that its degree distribution follows a power law, and that it has a large average clustering coefficient.