Computer Science and Application
Vol.4 No.11(2014), Article ID:14397,5 pages
DOI:10.12677/CSA.2014.411038

A Star-Tree-Structured Deterministic Small-World Network

Pengfeng Hou1, Haixing Zhao2

1Department of Mathematics, Qinghai Normal University, Xining

2School of Computer Science, Qinghai Normal University, Xining

Email: houpengfeng@gmail.com, haixingzhao@yahoo.com.cn

Copyright © 2014 by authors and Hans Publishers Inc.

Received: Sep. 28th, 2014; revised: Oct. 30th, 2014; accepted: Nov. 8th, 2014

Abstract

In the past dozen years, many probabilistic small-world networks and some deterministic smallworld networks have been proposed utilizing various mechanisms. Recently, Guo et al. [1] proposed a deterministic small-world network model by first constructing a binary-tree structure from star K1,2 by adding some edges in each iteration with a simple mechanism. In this paper, we propose a new deterministic small-world network model by constructing a binary-tree structure from a star K1,6 and then adding links between each grandfather node and its four grandson nodes for each tree in each iteration. Furthermore, we give the analytic solution to several topological characteristics, which shows that the proposed model is a small-world network.

Keywords:Small World Network, Star-Tree-Structure, Topological Characteristics

1青海师范大学数学系，西宁

2青海师范大学计算机学院，西宁

1. 引言

2. 确定性小世界网络的构建

(1)

3. 确定性小世界网络的相关特性

3.1. 度分布

(2)

(3)

Figure 1. The first four iterations of the growth of the proposed network

3.2. 聚集系数和聚集度相关性

(4)

(5)

3.3. 直径和平均路径长度

Figure 2. The APL and D versus the logarithm of the number of nodes

(6)

4. 结论

1. [1]   Guo, S.Z., Lu, Z.M., Kang, G.Y., Chen, Z. and Luo, H. (2012) A tree-structured deterministic small-world network. IEICE Transactions on Information and Systems, E95-D.

2. [2]   Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of “small-world” networks. Nature, 393, 440-442.

3. [3]   Newman, M.E.J. and Watts, D.J. (1999) Renormalization group analysis of the small-world network model. Physics Letters A, 263, 341-346.

4. [4]   Newman, M.E.J. and Watts, D.J. (1999) Scaling and percolation in the small-world network model. Physical Review E, 60, 7332-7342.

5. [5]   Kasturirangan, R. (1999) Multiple scales in small-world network.

6. [6]   Ozik, J., Hunt, B.-R. and Ott, E. (2004) Growing networks with geographical attachment preference: Emergence of small worlds. Physical Review E, 69, Article ID: 026108.

7. [7]   Comellas, F., Ozon, J. and Peters, J.G. (2000) Deterministic small-world communication networks. Information Processing Letters, 76, 83-90.

8. [8]   Boettcher, S., Gongalves, B. and Guclu, H. (2008) Hierarchical regular small-world networks. Physics A: Mathematical and Theoretical, 41, Article ID: 252001.

9. [9]   Chandra, A.K. and Dasgupta, S. (2005) A small world network of prime numbers. Physica A, 357, 436-446.

10. [10]   Corso, G. (2004) Families and clustering in a natural numbers network. Physical Review E, 69, Article ID: 036106.

11. [11]   Xiao, W.J. and Parhami, B. (2006) Cayley graphs as models of deterministic small-world networks. Information Processing Letters, 97, 115-117.