小世界網路架構擁有兩項特性：低直徑和高叢聚系數，這兩項特性也是在大型P2P網路中常被探討的，從過去的研究得知，以d-規則圖的網路架構為基礎，圖中的每個節點除了擁有原先的d個鏈結之外，再額外加上一些長距離的鏈結，就形成了小世界網路。在小世界網路中，給定一個來源端(s)和目的端(t)，從s出發到t存在著一條較短的路徑，但是從s要如何走到t，才能得到這條較短的路徑，卻是個難題，之後Kleinberg提出了一個可繞路的d維格狀的小世界網路，利用貪婪的繞路演算法可以使得s出發到t只需要經過O(log2N)個節點，N為網路中的節點數量。
在這篇論文當中，我們提出了一個可繞路的小世界網路，和先前的研究結果有些不一樣的地方：(一)我們提出的網路架構的建構方式是完全分散式的；(二)在我們所提出的網路架構底下，每個節點可以動態的加入和離開，加入的時候是採隨機的方式，而且過程中經過的節點數量為對數等級；(三)在我們所提出的網路架構底下，利用貪婪的繞路演算法，保證在任兩節點間經過節點數量的期望值為對數等級。我們透過嚴謹的效能分析和實驗模擬，來證實我們所提出的網路架構的效能。

Small-world (SW) networks possess two properties, namely low diameter and high clustering coefficient, that are often desired by large-scale peer-to-peer (P2P) networks. Prior studies have shown that the construction of a SW network can be based no a d-regular graph, and that each node in the graph maintains d local and a few constant numbers of long-distance contacts, However, it is commonly understood that it is difficult to find a short route in a SW network, given source (s) and target (t) nodes, though a SW network guarantees that a short route from s to t exists. Kleinberg then proposed a "navigable" SW network for a d-dimensional lattice such that a simple greedy routing algorithm can be devised to route a message from s to t using O(log^2N) hops, where N is the number of nodes in the network.
In this paper, we present the construction of a navigable SW network. Compared to previous efforts, the novelty of our study includes (i) that our network construction is fully decentralized, (ii) that the nodes in our network can dynamically join and leave; each node takes logarithmic hopcount in probability to join the netwrok; and (iii) that we guarantee routing a message greedily between any two nodes takes logarithmic hopcount in expection. We support the performance of proposal in this study through rigorous performance analysis and simulations.

[1] B. Bollobas and F. R. K. Chung. The Diameter of a Cycle Plus a Random Matching. SIAM Journal on discrete Mathematics, 1(3):328-333, August 1988.

[2] I. Clarke, S. G.. Miller, T. W. Hong, O. Sandberg, and B. Wiley. Protecting Free Expression Online with Freenet. IEEE Internet Computing, 6(1):40-49, January/February 2002.

[3] S. Dongen. A New Cluster Algorithm for Graphs. Technical report, Centrum voor Wiskunde en Informatica, December 1998.

[4] P. Duchon, N. Hanusse, E. Lebhar, and N. Schabanel. Towards Small World Emergence. In Proceedings of the Annual Symposium on Parallelism in Algorithms and Architectures, pages 225-232. ACM Press, July 2006.

[5] Gnutella. http://rfc-gnutella.sourceforge.net/.

[6] Y.K. Hui, C.S. Lui, and K.Y. Yau. Small-World Overlay P2P Networks: Construction and Handling Dynamic Flash Crowd. Computer Networks, 50(15):2727-2746, October 2006.

[7] A. Iamnitchi and I. Foster. Interest-Aware Information Dissemination in Small-World Communities. In Proceedings of the International Symposium on High Performance Distributed Computing, pages 167-175. IEEE Computer Society, July 2005.

[8] D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-Restricted Metrics. In Proceedings of the Annual Symposium on Theory of Computing, pages 741-750. ACM Press, May 2002.

[9] J. M. Kleinberg. The Small-World Phenomenon: An Algorithm Perspective. In Proceedings of the Annual Symposium on Theory of Computing, pages 163-170. ACM Press, December 2001.

[10] J. M. Kleinberg. Advances in Neural Information Processing Systems 14, chapter Small-World Phenomena and the Dynamics of Information, pages 431-438. MIT Press, December 2001.

[11] J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. OceanStore: An Architecture for Global-Scale Persistent Storage. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 190-201. ACM Press, November 2000.

[12] M. Li, W.-C. Lee, and A. Sivasubramaniam. Semantic Small World: An Overlay Network for Peer-to-Peer Search. In Proceedings of the International Conference on Network Protocols, pages 228-238. IEEE Computer Society, October 2004.

[13] Y. Li, S. Verma, L. Lao, and J.-H. Cui. SACA: SCM-based Adaptive Clustering Algorithm. In Proceedings of International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, pages 271-279, September 2005.

[14] Y. Liu, L. Xiao, X. Liu, L. M. Ni, and X. Zhang. Location Awareness in Unstructured Peer-to-Peer Systems. IEEE Transactions on Parallel and Distributed System, 12(2):163-174, February 2005.

[15] G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed Hashing in a Small World. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, March 2003.

[16] S. Milgram. The Small-World Problem. Psychology Today, 2:60-67, 1997.

[17] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge, 2005.

[18] L. Ramaswamy, B. Gedik, and L. Liu. A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks. IEEE Transactions on Parallel and Distributed Systems, 16(9):1-16, September 2005.

[19] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A Scalable Content-Addressable Network. In Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 161-172. ACM Press, August 2001.

[20] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. Topologically-Aware Overlay Construction and Server Selection. In Proceedings of IEEE INFOCOM, pages 1190-1199, June 2002.

[21] S. M. Ross. Introduction to Probability Models. Academic Press, 2nd edition, 2002.

[22] A. Rowstron and P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems. Lecture Notes in Computer Science, 2218:161-172, November 2001.

[23] H. Shen and C.-Z. Xu. Locality-Aware and Churn-Resilient Load-Balancing Algorithm in Structured Peer-to-Peer Networks. IEEE Transactions on Parallel and Distributed Systems, 18(6):849-862, June 2007.

[24] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 149-160. ACM Press, August 2001.

[25] S. Wang, D. Xuan, and W. Zhao. Analyzing and Enhancing the Resilience of Structured Peer-to-Peer Systems. Journal of Parallel and Distributed Computing, 65(2):207-219, February 2005.

[26] D. J. Watts and S. H. Strogatz. Collective Dynamics of Small-World Networks. Nature, 393:440-442, June 1998.

[27] L. Xiao, Y. Liu, and L. M. Ni. Improving Unstructured Peer-to-Peer Systems by Adaptive Connection Establishment. IEEE Transactions on Computers, 54(9):1901-1103, September 2005.

[28] Z. Xu, C. Tang, and Z. Zhang. Building Topology-Aware Overlays Using Global Soft-State. In Proceedings of the International Conference of Distributed Computing Systems, pages 500-508. IEEE Computer Society, May 2003.

[29] H. Zhang, A. Goel, and R. Govindan. Using the Small-World Model to Improve Freenet Performance. Computer Networks, 46(4):555-574, November 2004.

[30] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A Resilient Global-scale Overlay for Service Deployment. IEEE Journal on Selected Areas in Communications, 22(1):41-53, January 2004.

[31] Y. Zhu and Y. Hu. Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems. IEEE Transactions on Parallel and Distributed Systems, 16(4):349-361, April 2005.