文件共享網絡是非結構疊蓋式網路(unstructured P2P networks)的主要應用。
當任一節點(peer)加入非結構疊蓋式網路，隨機互相連結；他們常常是藉由訊息廣播(flooding query messages)來搜尋網際網路上的物件，實驗研究證實在疊蓋式網路，節點擁有共同喜好（preferences）比較高的機會為彼此提供所需要的物件，在最近
提出的非結構疊蓋式網路；意指以小世界(small-world)的模式藉由節點中的儲存內容來組織參與的節點。
由於目前開發小世界模式的非結構疊蓋式網路演算法沒有準確的表示共享物件的模式，由此產生的網絡可能無法有效率的搜索和有效地利用相同興趣的節點。鑑於此，我們建立一個分析模型來說明小世界特徵可以準確的被納入廣播基礎下的非結構疊蓋式網路(flooding-based unstructured P2P networks)。根據我們的分析模型，
我們進一步提出一個新的疊蓋式網路演算法來建構小世界模式下的非結構網路。我們的演算法在模擬實驗中以實際數據組進行模擬，實驗結果證明，我們的建議在搜尋效率以及效益是優於其他現有的演算法。

Unstructured peer-to-peer (P2P)file-sharing networks are popular in the mass market.
As the peers participating in unstructured networks interconnect randomly, they rely on flooding query messages to discover objects of interest. Empirical measurement
studies indicate that the peers in P2P networks have similar preferences, and recently proposed unstructured P2P networks intend to organize the participating peers in a
small-world (SW) fashion by exploiting the knowledge of contents stored in peers. As existing algorithms often develop SW-based unstructured P2P networks without
precisely revealing the object sharing patterns, the resultant networks may not perform searches efficiently and effectively by exploiting the common interests among peers.
In light of this, we develop an analytical model to illustrate how the SW feature can be faithfully included into flooding-based unstructured P2P networks. Based on our
analytical model, we further suggest a novel P2P network formation algorithm to construct SW-based unstructured networks. We validate our proposal in simulations with
empirical data sets, and the simulation results prove that our proposal greatly outperforms existing algorithms in terms of search efficiency and effectiveness.

[1] M. Bawa, H. Garcia-Molina, A. Gionis, and R. Motwani. Estimating Aggregates
on a Peer-to-Peer Network. Technical report, Stanford InfoLab, Apr. 2003. [online]
http://ilpubs.stanford.edu:8090/586/.
[2] M. W. Berry, Z. Drmac, and E. R. Jessup. Matrices, Vector Spaces, and Informa-
tion Retrieval. SIAM Rev., 41(2):335{362, June 1999.
[3] B. Bollob¶as. Random Graphs. Cambridge University Press, 2nd edition, 2001.
[4] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker. Making
Gnutella-like P2P Systems Scalable. In Proc. ACM SIGCOMM'03, pages 407{
418, Aug. 2003.
[5] H. Chen, H. Jin, Y. Liu, and L. M. Ni. Di±culty-Aware Hybrid Search in Peer-
to-Peer Networks. IEEE Trans. Parallel Distrib. Syst., 20(1):71{82, Jan. 2009.
[6] X. Cheng, C. Dale, and J. Liu. Statistics and Social Networking of YouTube
Videos. In Proc. 16th IEEE Int'l Workshop Quality of Service (IWQOS'08), pages
229{238, June 2008.
[7] A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-Law Distributions in
Empirical Data. SIAM Rev., 51(4):661{703, 2009.
[8] E. Cohen and S. Shenker. Replication Strategies in Unstructured Peer-to-Peer
Networks. In Proc. ACM SIGCOMM'02, pages 177{190, Aug. 2002.
[9] A. Crespo and H. Garcia-Molina. Routing Indices for Peer-to-Peer Systems. In
Proc. 22th IEEE Int'l Conf. Distributed Computing Systems (ICDCS'02), pages
23{32, July 2002.
[10] P. Erd}os and A. R¶enyi. On Random Graphs. Publ. Math. Debrecen, 6:290{297,
1959.
[11] F. Le Fessant, S. B. Handurukande, A.-M. Kermarrec, and L. Massouli¶e. Cluster-
ing in Peer-to-Peer File Sharing Workloads. In Proc. 3rd Int'l Workshop Peer-to-
Peer Systems (IPTPS'04), pages 217{226, Feb. 2004.
[12] L. C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry,
40(1):35{41, Mar. 1977.
[13] M. Girvan and M. E. J. Newman. Community Structure in Social and Biological
Networks. In Proc. Natl. Acad. Sci. USA, volume 99, pages 7821{7826, June 2002.
[14] Gnutella. [online] http://rfc-gnutella.sourceforge.net/.
[15] H.-C. Hsiao, Y.-C. Lin, and H. Liao. Building Small-World Peer-to-Peer Networks
Based on Hierarchical Structures. IEEE Trans. Parallel Distrib. Syst., 20(7):1023{
1037, July 2009.
[16] Y. K. Hui, C. S. Lui, and K. Y. Yau. Small-World Overlay P2P Networks: Con-
struction and Handling Dynamic Flash Crowd. Computer Networks, 50(15):2727{
2746, Oct. 2006.
[17] A. Iamnitchi, M. Ripeanu, and I. Foster. Small-World File-Sharing Communities.
In Proc. IEEE INFOCOMM'04, pages 952{963, Mar. 2004.
[18] IPOQUE. ipoque Internet Study 2007: P2P File Sharing Still Dominates the
Worldwide Internet. [online] http://www.ipoque.com/news-and-events/news/
archive/2007.
[19] M. H. Kalos and P. A. Whitlock. Monte Carlo Methods, chapter Random Walks,
Integral Equations, and Variance Reduction, pages 107{130. Wiley-VCH, 2nd
edition, 2008.
[20] J. M. Kleinberg. Navigation in a Small World. Nature, 406:845, Aug. 2000.
[21] M. Li, W.-C. Lee, A. Sivasubramaniam, and J. Zhao. SSW: A Small-World-Based
Overlay for Peer-to-Peer Search. IEEE Trans. Parallel Distrib. Syst., 19(6):735{
749, June 2008.
[22] X. Li and J. Wu. Searching Techniques in Peer-to-Peer Networks, chapter Hand-
book of Theoretical and Algorithmic Aspects of Ad Hoc, Sensor, and Peer-to-Peer
Networks, pages 613{642. Auerbach, 2006.
[23] K. C.-J. Lin, C.-P. Wang, C.-F. Chou, and L. Golubchik. SocioNet: A Social-
Based Multimedia Access System for Unstructured P2P Networks. IEEE Trans.
Parallel Distrib. Syst., Aug. 2009. [online] http://doi.ieeecomputersociety.
org/10.1109/TPDS.2009.135.
[24] Y. Liu, L. Xiao, X. Liu, L. M. Ni, and X. Zhang. Location Awareness in Unstruc-
tured Peer-to-Peer Systems. IEEE Trans. Parallel Distrib. Syst., 12(2):163{174,
Feb. 2005.
[25] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and Replication in
Unstructured Peer-to-Peer Networks. In Proc. ACM Int'l Conf. Supercomputing
(ICS'02), pages 84{95, June 2002.
[26] S. Milgram. The Small-World Problem. Psychology Today, 2:60{67, 1967.
[27] M. E. J. Newman. The Structure of Scienti¯c Collaboration Networks. In Proc.
Natl. Acad. Sci. USA, volume 98, pages 404{409, Jan. 2001.
[28] S. M. Ross. Introduction to Probability Models, chapter Markov Chains, pages
185{280. Academic Press, 9th edition, 2007.
[29] S. Saroiu, P. K. Gummadi, and S. D. Gribble. Measuring and Analyzing the
Characteristics of Napster and Gnutella Hosts. Multimedia Systems, pages 170{
184, Aug. 2003.
[30] S. Sen and J. Wang. Analyzing Peer-to-Peer Tra±c Across Large Networks.
IEEE/ACM Trans. Netw., 12(2):219{232, Apr. 2004.
[31] H. Shen, C.-Z. Xu, and G. Chen. Cycloid: A Scalable Constant-Degree Lookup-
E±cient P2P Overlay Network. Performance Evaluation, 63(3):195{216, Mar.
2006.
[32] X. Shi, J. Han, Y. Liu, and L. M. Ni. Popularity Adaptive Search in Hybrid P2P
Systems. J. Parallel Distrib. Comput., 69(2):125{134, Feb. 2009.
[33] K. Sripanidkulchai, B. Maggs, and H. Zhang. E±cient Content Location Using
Interest-Based Locality in Peer-to-Peer Systems. In Proc. IEEE INFOCOMM'03,
pages 2166{2176, Mar. 2003.
[34] M. Srivatsa, B. Gedik, and L. Liu. Scaling Unstructured Peer-to-Peer Networks
with Heterogeneity-Aware Topology And Routing. IEEE Trans. Parallel Distrib.
Syst., 17(10):1277{1293, Oct. 2006.
[35] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek,
and H. Balakrishnan. Chord: a Scalable Peer-to-Peer Lookup Protocol for Internet
Applications. IEEE/ACM Trans. Netw., 11(1):17{21, Feb. 2003.
[36] C. Tang, Z. Xu, and S. Dwarkadas. Peer-to-Peer Information Retrieval Using
Self-Organizing Semantic Overlay Networks. In Proc. ACM SIGCOMM'03, pages
175{186, Aug. 2003.
[37] D. J. Watts and S. H. Strogatz. Collective Dynamics of Small-World Networks.
Nature, 393:440{442, June 1998.
[38] L. Xiao, Y. Liu, and L. M. Ni. Improving Unstructured Peer-to-Peer Systems by
Adaptive Connection Establishment. IEEE Trans. Computers, 54(9):1091{1103,
Sept. 2005.
[39] L. Xiao, Z. Zhuang, and Y. Liu. Dynamic Layer Management in Superpeer Ar-
chitectures. IEEE Trans. Parallel Distrib. Syst., 16(11):1078{1091, Nov. 2005.
[40] X. Zhang, Q. Zhang, Z. Zhang, G. Song, and W. Zhu. A Construction of Locality-
Aware Overlay Network: mOverlay and Its Performance. IEEE J. Selected Areas
in Comm., 18(28):995{1002, Jan. 2004.
[41] Y. Zhu and Y. Hu. Enhancing Search Performance on Gnutella-Like P2P Systems.
IEEE Trans. Parallel Distrib. Syst., 17(12):1482{1495, Dec. 2006.
[42] Y. Zhu and Y. Hu. Semantic Search in Peer-to-Peer Systems, chapter Hand-
book of Theoretical and Algorithmic Aspects of Ad Hoc, Sensor, and Peer-to-Peer
Networks, pages 643{664. Auerbach, 2006.