对等点（P2P）网络搜索技术的研究
|
摘要
对等点(Peer-to-Peer,简称P2P)网络是一种新兴的复杂网络。随着P2P网络的广泛应用,人们发现即使每个用户提供少量文件,整个用户群所共享的文件数也是非常庞大的。要想充分利用这些资源,首先要能够快速准确地找到它们。因此,P2P网络搜索技术研究成为了一个重要的研究课题。
P2P网络搜索技术涉及到图论、统计物理学、网络测量、数学建模及算法设计等多个领域。如何利用近年复杂网络的研究成果对P2P网络模型进行优化与改进,以达到提高搜索效率和精度的目的;如何基于现有P2P网络模型设计出更加有效的局部搜索策略等已成为P2P网络搜索技术研究中的重要内容。
本文研究了基于P2P网络结构原理的复杂网络映射模型,分析了基于P2P网络模型的局部搜索策略的搜索性能。论文的主要内容和成果总结如下:
①对复杂网络的研究背景进行了简介,并总结了现有P2P网络结构及搜索技术的研究成果。
②根据P2P网络是建立在Internet上的一种逻辑映射网络的特点,提出了一种基于较大规模的底层网络生成较小规模的映射网络模型的算法,并将均匀的随机图和非均匀的无标度网络作为底层网络,
Peer-to-Peer (P2P) network is a new kind of complex network. It is found that even if each individual provides only a few files, enormous files can be shared by the whole group of users. In order to use these abundant resources, the key problem is to find them effectively. Therefore, the issue of search in P2P networks has become an important topic.
The search in P2P networks is related to many fields, such as graph theory, statistical physics, network measuring, mathematics modeling, and algorithm design. Two main aspects of search in P2P networks have been studied in recent years: one is how to optimize and improve the P2P network models, according to the known results of the complex networks, to obtain high search efficiency and accuracy, the other is how to design more effective local search strategies based on current P2P network models.
In this thesis, we study the mapping model of complex network based on the principle of P2P network structure and analyze the performance of local search strategies. The main content and contributions of this thesis are as follows:
P2P网络搜索技术涉及到图论、统计物理学、网络测量、数学建模及算法设计等多个领域。如何利用近年复杂网络的研究成果对P2P网络模型进行优化与改进,以达到提高搜索效率和精度的目的;如何基于现有P2P网络模型设计出更加有效的局部搜索策略等已成为P2P网络搜索技术研究中的重要内容。
本文研究了基于P2P网络结构原理的复杂网络映射模型,分析了基于P2P网络模型的局部搜索策略的搜索性能。论文的主要内容和成果总结如下:
①对复杂网络的研究背景进行了简介,并总结了现有P2P网络结构及搜索技术的研究成果。
②根据P2P网络是建立在Internet上的一种逻辑映射网络的特点,提出了一种基于较大规模的底层网络生成较小规模的映射网络模型的算法,并将均匀的随机图和非均匀的无标度网络作为底层网络,
Peer-to-Peer (P2P) network is a new kind of complex network. It is found that even if each individual provides only a few files, enormous files can be shared by the whole group of users. In order to use these abundant resources, the key problem is to find them effectively. Therefore, the issue of search in P2P networks has become an important topic.
The search in P2P networks is related to many fields, such as graph theory, statistical physics, network measuring, mathematics modeling, and algorithm design. Two main aspects of search in P2P networks have been studied in recent years: one is how to optimize and improve the P2P network models, according to the known results of the complex networks, to obtain high search efficiency and accuracy, the other is how to design more effective local search strategies based on current P2P network models.
In this thesis, we study the mapping model of complex network based on the principle of P2P network structure and analyze the performance of local search strategies. The main content and contributions of this thesis are as follows:
引文
[1] Strogatz S H. Exploring Complex Networks. Nature, 410(6825): 268-276, 2001.
[2] 汪小帆,李翔,陈关荣. 复杂网络理论及其应用. 北京:清华大学出版社,2006.
[3] Erd?s P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17-60, 1959.
[4] Barabási A L. Linked: The New Science of Networks. Massachusetts: Persus Publishing, 2002.
[5] Watts D J. The New Science of Networks. Annual Review of Sociology, 30: 243-270, 2004.
[6] Travers J, Milgram S, An Experimental Study of the Small World Problem, Sociometry, 32: 425-443, 1969.
[7] Kleinberg J. Navigation in a Small World. Nature, 406: 845, 2000.
[8] Kleinberg J. The Small-world Phenomenon: An Algorithmic Perspective. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Association of Computing Machinery, New York, 163-170, 2000.
[9] Watts D J, Dodds P S, Newman M E J. Identity and Search in Social Networks. Science, 296: 1302-1305, 2002.
[10] Abrer K, Hauswirth M. Peer-to-Peer Information Systems: Concepts and Models, State-of-the-Art, and Future Systems. Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering, 326-327, 2001.
[11] Aslund J. Authentication in Peer-to-Peer Systems. http://www.ep.liu.se/ exjobb/isy/2002/3153/exjobb.pdf, 2002.
[12] Delaney B, Catarci T, Little T D C. The Power of P2P. IEEE Multimedia, 8(2): 100-103, 2001.
[13] http://www.napster.com
[14] http://www.gnutella.com
[15] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW. New York: Oxford University Press, 2003.
[16] Clarke I, Sandberg O, Wiley B, etc. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Proceedings of ICSI Workshop on Design Issues in Anonymity and Unobservability, 2000.
[1] Sundsted T. 对等计算实践:发现[EB/OL]. http://www.900.ibm.com/ developer works/java/j-P2P/part5/index.shtml, 2001.
[2] Minar N. Distributed Systems Topologies:Part 1. http://www.openp2p.com /pub/a/p2p/2001/12/14/topologies_one.html, 2001.
[3] Minar N. Distributed Systems Topologies:Part 2. http://www.openp2p.com /pub/a/p2p/2001/12/14/topologies_one.html, 2002.
[4] Hsiao H C, King C T. Tornado: A Capability-aware Peer-to-Peer Storage Overlay. Journal of Parallel Distribution Computing, 64(6):747-758, 2004.
[5] Lv Q, Cao P, Cohen E. Search and Replication in Unstructured Peer-to-Peer Networks. Proceedings of the 16th ACM International Conference on Supercomputing, 2002.
[6] www.napster.com
[7] www.gnutella.com
[8] Ripeanu M. Peer-to-Peer Architecture Case Study: Gnutella. Proceedings of International Conference on P2P Computing, 2001.
[9] Ivkovic I. Improving Gnutella Protocol:Protocol Analysis and Research Proposals. Prize-Winning Paper for LimeWire Gnutella Research Contest, September, 2001.
[10] Gribble S D, Brewer E A, Hellerstein J M, etc. Scalable. Distributed Data Structures for Internet Service Construction. Proceedings of Fourth Symposium on Operating Systems Design and Implementation, October, 2000.
[11] Stoica I, Morris R, D Liben-Nowell, etc. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. Proceedings of the ACM Annual Conference of the Special Interest Group on Data Communication, 2001.
[12] Stutzbach D, Rejaie R, Sen S. Characterizing Unstructured Overlay Topologies in Modern P2P File-sharing Systems. Proceedings of Internet Measurement Conference, Berkeley, CA, USA, October, 2005.
[13] Stutzbach D, Rejaie R. Characterizing the Two-tier Gnutella Topology. Proceedings of ACM SIGMETRICS (Poster), 402-403, June, 2005.
[14] Kalogeraki V, Gunopulos D, Yazti Z D. A Local Search Mechanism for P2P Networks. Proceedings of CIKM’02, McLean, Virginia, USA, November 4-9, 2002.
[15] Yang B, Garcia M H. Improving Search in Peer-to-Peer Networks. Proceedings of the 22nd IEEE International Conference on Distributed Computing, 2002.
[16] Gkantsidis C, Mihail M, Saberi A. Random Walks in Peer-to-Peer Networks. IEEE Infocom, 2004.
[17] Jawhar I, Wu J. A Two-Level Random Walk Search Protocol for Peer-to-Peer Networks. Proceedings of the 8th World Multi-Conference on Systems,Cybernetic and Informatic, 2004.
[18] Crespo A, Molina G H. Routing Indices for Peer-to-Peer Systems. Proceedings of the 22nd International Conference on Distributed Computing, 2002.
[19] Daniel Lubke, Jorge Marx Gomez. Applications for Mobile Agents in Peer-to-Peer-Networks. Proceedings of 11th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems, 2004.
[20] Clarke I, Sandberg O, Wiley B, etc. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Proceedings of ICSI Workshop on Design Issues in Anonymity and Unobservability, 2000.
[21] Adamic L A, Lukose R M, Puniyani A R. Search in Power-law Networks. Phys. Rev. E, 64: 046135, 2001.
[22] Sarnant K, Bhattacharyya S. Topology, Search, and Fault Tolerance in Unstructured P2P Networks. Proceedings of the 37th Annual Hawaii International Conference on System Sciences, 289-294, Jan 5-8, 2004.
[23] Adamic L A, Lukose R M, Huberman B A. Local Search in Unstructured Networks. In S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks, Wiley-VCH, Berlin, 2003.
[24] Wouhaybi R H, Campbell A T. Phenix: Supporting Resilient Low-diameter Peer-to-Peer topologies. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, 2004.
[25] Albert R, Barabási A L. Statistical Mechanics of Complex Networks. Rev Mod Phys, 74: 47-97, 2002.
[26] Barabási A L, Albert R. Emergence of Scaling in Random Networks. Science,286(5439): 509-512, 1999.
[27] Barabási A L, Bonabeau E. Scale-free Networks. Scientific American, 50-59, May, 2003.
[28] Watts D J, Strogatz S H. Collective Dynamics of ‘small-world’ Networks. Nature, 393(6684): 440-442, 1998.
[29] Watts D J. Six Degrees: The Science of a Connected Age. New York: Norton, 2003.
[30] Adamic L A, Adar E. How to Search a Social Network. cond-mat/0310120.
[31] Milgram S. The Small World Problem. Psychology Today, 60-67, May, 1967.
[32] Kleinberg J. The Small-world Phenomenon: An Algorithmic Perspective. Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000.
[33] Zhang H, Goel A, Govindan R. Using the Small-world Model to Improve Freenet Performance. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, 2003.
[34] Ratnasamy S, Francis P, Handley M, Karp R, Shenker S A Scalable Content-Addressable Network. Proceedings of ACM SIGCOMM, San Diego, California, USA, 2001.
[35] Rowstron A, Druschel P. Pastry: Scalable, Decentralized Object Location and Routing for Large-scale Peer-to-Peer Systems. Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms, 2001.
[36] Karger D, Lehman E, Leighton T, Levine M, Lewin D, Rina P. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 654-663, 1997.
[37] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST. National Technical Information Service, Springfield, VA, April, 1995.
[38] Matei R, Iamnitchi A, Foster P. Mapping the Gnutella Network. IEEE Internet Computing, 6(1): 50-57, 2002.
[39] Newman M E J. The Structure and Function of Complex Networks. SIAM Review, 45(2): 167-256, 2003.
[40] Peng Y, Yang M, Dai Y F. Analyze the Impact of User Search Behavior on DHT-based P2P File Sharing System. Proceedings of International Workshop on NGI and P2P Systems, October, 2006.
[41] Harvey N J A, Jones M B, Saroiu S, Theimer M, Wolman A. SkipNet: A Scalable Overlay Network with Practical Locality Properties. Proceedings of 4th USENIX Symposium on Internet Technologies and Systems, 2003.
[42] Shi X Q, Han J S. Popularity Biased Hybrid Search in P2P Systems.Proceedings of Fifth International Conference of IEEE Computer Society on Grid and Cooperative Computing, 2006.
[43] Wang X F, Chen G R. Complex Networks: Small-world, Scale-free and Beyond. IEEE Circuits & Systems Magazine, 3(1): 6-20, 2003.
[44] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW. New York: Oxford University Press, 2003.
[45] Wang F, Moreno Y, Sun Y. Structure of Peer-to-Peer Social Network. Phys.Rev.E, 73: 036123, 2006.
[1] Sarnant K, Bhattacharyya S. Topology, Search, and Fault Tolerance in Unstructured P2P Networks. Proceedings of the 37th Annual Hawaii International Conference on System Sciences, P: 289-294, Jan 5-8, 2004.
[2] Yang B, Garcia M H. Improving Search in Peer-to-Peer Networks. Proceeding of the 22nd IEEE International Conference on Distributed Computing, 2002.
[3] Matei R, Iamnitchi A, Foster P. Mapping the Gnutella Network. IEEE Internet Computing, 6(1): 50-57, 2002.
[4] Stutzbach D, Rejaie R, Sen S. Characterizing Unstructured Overlay Topologies in Modern P2P File-sharing Systems. In Internet Measurement Conference, Berkeley, CA, USA, Oct 2005.
[5] http://www.gnutella.com.
[6] Wang X F, Chen G R. Complex Networks: Small World, Scale-free and Beyond. IEEE Circuits and System Magazine, 3(1): 6-21, 2003.
[7] Erd?s P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17-60, 1960.
[8] Albert R, Barabási A L. Statistical Mechanics of Complex Networks. Review of Modern Physics, 74: 47-97, 2002.
[9] Newman M E J. The Structure and Function of Complex Networks. SIAM Review, 45(2): 167-256, 2003.
[10] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW. New York: Oxford University Press, 2003.
[11] Barabási A L, Albert R. Emergence of Scaling in Random Networks. Science,286(5439): 509-512, 1999.
[12] Watts D J, Strogatz S H. Collective Dynamics of ‘Small-world’ Networks. Nature, 393(6684): 440-442, 1998.
[13] Barabási A L, Bonabeau E. Scale-free Networks. Scientific American, 50-59, May 2003.
[14] Milgram S. The Small World Problem. Psychology Today, 60-67, May 1967.
[15] Watts D J. Six Degrees: The Science of a Connected Age. New York: Norton, 2003.
[16] Goh K I, Salvi G, Kahng B, etc. Skeleton and Fractal Scaling in Complex Networks. Phys.Rev.Lett, 96: 018701, 2006.
[17] Kim D H, Noh J D, Jeong H. Scale-free Trees:The Skeletons of Complex Networks. Phys.Rev.E, 70: 046126, 2004.
[1] Hughes D, Walkerdine J, Coulson G, etc. Peer-to-Peer: Is Deviant Behavior the Norm on P2P File-sharing Networks? IEEE Computer Society Vol. 7, No. 2, February, 2006.
[2] Wang F, Moreno Y, Sun Y. Structure of Peer-to-Peer Social Network. Phys.Rev.E, 73: 036123, 2006.
[3] Jasch F, Blumen A. Target Problem on Small-world Networks. Phys. Rev. E, 63: 041108, 2001.
[4] 汪小帆,李翔,陈关荣. 复杂网络理论及其应用. 北京:清华大学出版社,2006.
[5] Adamic L A, Lukose R M, Puniyani A R. Search in Power-law Networks. Phys. Rev. E, 64: 046135, 2001.
[6] Adamic L A, Lukose R M, Huberman B A. Local Search in Unstructured Networks. In S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs andNetworks, Wiley-VCH, Berlin, 2003.
[7] Erd?s P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17-60, 1960.
[8] Pandurangan G, Raghavan P, Upfal E. Builaing Low-diameter Peer-to-Peer Networks. IEEE J. Select. Areas Commun. , 21(6): 995-1002, 2003.
[9] Ratnasamy S, Francis P, Handley M, etc. A Scalable Content-Addressable Network. Proceedings of ACM SIGCOMM, San Diego, California, USA, 2001.
[10] Dixon C. Temporal Resolution: A Breadth-first Search Approach. Proceedings of IEEE Third International Workshop, 19-20, May, 1996.
[11] Hughes B D. Random Walks and Random Environments. Clarendon Press, Oxford, Vols. 1 and 2, 1996.
[12] Gkantsidis C, Mihail M, Saberi A. Random Walks in Peer-to-Peer Networks. IEEE Infocom, 2004.
[13] Kim B J, Yoon C N, Han S K. Path Finding Strategies in Scale-free Networks. Phys. Rev. E, 65: 027103, 2002.
[14] Ivkovic I. Improving Gnutella Protocol:Protocol Analysis and Research Proposals. Prize-Winning Paper for LimeWire Gnutella Research Contest, September, 2001.
[15] Barabási A L, Bonabeau E. Scale-free Networks. Scientific American, 50-59, May 2003.
[16] Milgram S. The Small World Problem. Psychology Today, 60-67, May 1967.
[17] Watts D J. Six Degrees: The Science of a Connected Age. New York: Norton, 2003.
[2] 汪小帆,李翔,陈关荣. 复杂网络理论及其应用. 北京:清华大学出版社,2006.
[3] Erd?s P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17-60, 1959.
[4] Barabási A L. Linked: The New Science of Networks. Massachusetts: Persus Publishing, 2002.
[5] Watts D J. The New Science of Networks. Annual Review of Sociology, 30: 243-270, 2004.
[6] Travers J, Milgram S, An Experimental Study of the Small World Problem, Sociometry, 32: 425-443, 1969.
[7] Kleinberg J. Navigation in a Small World. Nature, 406: 845, 2000.
[8] Kleinberg J. The Small-world Phenomenon: An Algorithmic Perspective. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Association of Computing Machinery, New York, 163-170, 2000.
[9] Watts D J, Dodds P S, Newman M E J. Identity and Search in Social Networks. Science, 296: 1302-1305, 2002.
[10] Abrer K, Hauswirth M. Peer-to-Peer Information Systems: Concepts and Models, State-of-the-Art, and Future Systems. Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering, 326-327, 2001.
[11] Aslund J. Authentication in Peer-to-Peer Systems. http://www.ep.liu.se/ exjobb/isy/2002/3153/exjobb.pdf, 2002.
[12] Delaney B, Catarci T, Little T D C. The Power of P2P. IEEE Multimedia, 8(2): 100-103, 2001.
[13] http://www.napster.com
[14] http://www.gnutella.com
[15] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW. New York: Oxford University Press, 2003.
[16] Clarke I, Sandberg O, Wiley B, etc. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Proceedings of ICSI Workshop on Design Issues in Anonymity and Unobservability, 2000.
[1] Sundsted T. 对等计算实践:发现[EB/OL]. http://www.900.ibm.com/ developer works/java/j-P2P/part5/index.shtml, 2001.
[2] Minar N. Distributed Systems Topologies:Part 1. http://www.openp2p.com /pub/a/p2p/2001/12/14/topologies_one.html, 2001.
[3] Minar N. Distributed Systems Topologies:Part 2. http://www.openp2p.com /pub/a/p2p/2001/12/14/topologies_one.html, 2002.
[4] Hsiao H C, King C T. Tornado: A Capability-aware Peer-to-Peer Storage Overlay. Journal of Parallel Distribution Computing, 64(6):747-758, 2004.
[5] Lv Q, Cao P, Cohen E. Search and Replication in Unstructured Peer-to-Peer Networks. Proceedings of the 16th ACM International Conference on Supercomputing, 2002.
[6] www.napster.com
[7] www.gnutella.com
[8] Ripeanu M. Peer-to-Peer Architecture Case Study: Gnutella. Proceedings of International Conference on P2P Computing, 2001.
[9] Ivkovic I. Improving Gnutella Protocol:Protocol Analysis and Research Proposals. Prize-Winning Paper for LimeWire Gnutella Research Contest, September, 2001.
[10] Gribble S D, Brewer E A, Hellerstein J M, etc. Scalable. Distributed Data Structures for Internet Service Construction. Proceedings of Fourth Symposium on Operating Systems Design and Implementation, October, 2000.
[11] Stoica I, Morris R, D Liben-Nowell, etc. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. Proceedings of the ACM Annual Conference of the Special Interest Group on Data Communication, 2001.
[12] Stutzbach D, Rejaie R, Sen S. Characterizing Unstructured Overlay Topologies in Modern P2P File-sharing Systems. Proceedings of Internet Measurement Conference, Berkeley, CA, USA, October, 2005.
[13] Stutzbach D, Rejaie R. Characterizing the Two-tier Gnutella Topology. Proceedings of ACM SIGMETRICS (Poster), 402-403, June, 2005.
[14] Kalogeraki V, Gunopulos D, Yazti Z D. A Local Search Mechanism for P2P Networks. Proceedings of CIKM’02, McLean, Virginia, USA, November 4-9, 2002.
[15] Yang B, Garcia M H. Improving Search in Peer-to-Peer Networks. Proceedings of the 22nd IEEE International Conference on Distributed Computing, 2002.
[16] Gkantsidis C, Mihail M, Saberi A. Random Walks in Peer-to-Peer Networks. IEEE Infocom, 2004.
[17] Jawhar I, Wu J. A Two-Level Random Walk Search Protocol for Peer-to-Peer Networks. Proceedings of the 8th World Multi-Conference on Systems,Cybernetic and Informatic, 2004.
[18] Crespo A, Molina G H. Routing Indices for Peer-to-Peer Systems. Proceedings of the 22nd International Conference on Distributed Computing, 2002.
[19] Daniel Lubke, Jorge Marx Gomez. Applications for Mobile Agents in Peer-to-Peer-Networks. Proceedings of 11th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems, 2004.
[20] Clarke I, Sandberg O, Wiley B, etc. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Proceedings of ICSI Workshop on Design Issues in Anonymity and Unobservability, 2000.
[21] Adamic L A, Lukose R M, Puniyani A R. Search in Power-law Networks. Phys. Rev. E, 64: 046135, 2001.
[22] Sarnant K, Bhattacharyya S. Topology, Search, and Fault Tolerance in Unstructured P2P Networks. Proceedings of the 37th Annual Hawaii International Conference on System Sciences, 289-294, Jan 5-8, 2004.
[23] Adamic L A, Lukose R M, Huberman B A. Local Search in Unstructured Networks. In S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks, Wiley-VCH, Berlin, 2003.
[24] Wouhaybi R H, Campbell A T. Phenix: Supporting Resilient Low-diameter Peer-to-Peer topologies. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, 2004.
[25] Albert R, Barabási A L. Statistical Mechanics of Complex Networks. Rev Mod Phys, 74: 47-97, 2002.
[26] Barabási A L, Albert R. Emergence of Scaling in Random Networks. Science,286(5439): 509-512, 1999.
[27] Barabási A L, Bonabeau E. Scale-free Networks. Scientific American, 50-59, May, 2003.
[28] Watts D J, Strogatz S H. Collective Dynamics of ‘small-world’ Networks. Nature, 393(6684): 440-442, 1998.
[29] Watts D J. Six Degrees: The Science of a Connected Age. New York: Norton, 2003.
[30] Adamic L A, Adar E. How to Search a Social Network. cond-mat/0310120.
[31] Milgram S. The Small World Problem. Psychology Today, 60-67, May, 1967.
[32] Kleinberg J. The Small-world Phenomenon: An Algorithmic Perspective. Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000.
[33] Zhang H, Goel A, Govindan R. Using the Small-world Model to Improve Freenet Performance. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, 2003.
[34] Ratnasamy S, Francis P, Handley M, Karp R, Shenker S A Scalable Content-Addressable Network. Proceedings of ACM SIGCOMM, San Diego, California, USA, 2001.
[35] Rowstron A, Druschel P. Pastry: Scalable, Decentralized Object Location and Routing for Large-scale Peer-to-Peer Systems. Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms, 2001.
[36] Karger D, Lehman E, Leighton T, Levine M, Lewin D, Rina P. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 654-663, 1997.
[37] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST. National Technical Information Service, Springfield, VA, April, 1995.
[38] Matei R, Iamnitchi A, Foster P. Mapping the Gnutella Network. IEEE Internet Computing, 6(1): 50-57, 2002.
[39] Newman M E J. The Structure and Function of Complex Networks. SIAM Review, 45(2): 167-256, 2003.
[40] Peng Y, Yang M, Dai Y F. Analyze the Impact of User Search Behavior on DHT-based P2P File Sharing System. Proceedings of International Workshop on NGI and P2P Systems, October, 2006.
[41] Harvey N J A, Jones M B, Saroiu S, Theimer M, Wolman A. SkipNet: A Scalable Overlay Network with Practical Locality Properties. Proceedings of 4th USENIX Symposium on Internet Technologies and Systems, 2003.
[42] Shi X Q, Han J S. Popularity Biased Hybrid Search in P2P Systems.Proceedings of Fifth International Conference of IEEE Computer Society on Grid and Cooperative Computing, 2006.
[43] Wang X F, Chen G R. Complex Networks: Small-world, Scale-free and Beyond. IEEE Circuits & Systems Magazine, 3(1): 6-20, 2003.
[44] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW. New York: Oxford University Press, 2003.
[45] Wang F, Moreno Y, Sun Y. Structure of Peer-to-Peer Social Network. Phys.Rev.E, 73: 036123, 2006.
[1] Sarnant K, Bhattacharyya S. Topology, Search, and Fault Tolerance in Unstructured P2P Networks. Proceedings of the 37th Annual Hawaii International Conference on System Sciences, P: 289-294, Jan 5-8, 2004.
[2] Yang B, Garcia M H. Improving Search in Peer-to-Peer Networks. Proceeding of the 22nd IEEE International Conference on Distributed Computing, 2002.
[3] Matei R, Iamnitchi A, Foster P. Mapping the Gnutella Network. IEEE Internet Computing, 6(1): 50-57, 2002.
[4] Stutzbach D, Rejaie R, Sen S. Characterizing Unstructured Overlay Topologies in Modern P2P File-sharing Systems. In Internet Measurement Conference, Berkeley, CA, USA, Oct 2005.
[5] http://www.gnutella.com.
[6] Wang X F, Chen G R. Complex Networks: Small World, Scale-free and Beyond. IEEE Circuits and System Magazine, 3(1): 6-21, 2003.
[7] Erd?s P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17-60, 1960.
[8] Albert R, Barabási A L. Statistical Mechanics of Complex Networks. Review of Modern Physics, 74: 47-97, 2002.
[9] Newman M E J. The Structure and Function of Complex Networks. SIAM Review, 45(2): 167-256, 2003.
[10] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW. New York: Oxford University Press, 2003.
[11] Barabási A L, Albert R. Emergence of Scaling in Random Networks. Science,286(5439): 509-512, 1999.
[12] Watts D J, Strogatz S H. Collective Dynamics of ‘Small-world’ Networks. Nature, 393(6684): 440-442, 1998.
[13] Barabási A L, Bonabeau E. Scale-free Networks. Scientific American, 50-59, May 2003.
[14] Milgram S. The Small World Problem. Psychology Today, 60-67, May 1967.
[15] Watts D J. Six Degrees: The Science of a Connected Age. New York: Norton, 2003.
[16] Goh K I, Salvi G, Kahng B, etc. Skeleton and Fractal Scaling in Complex Networks. Phys.Rev.Lett, 96: 018701, 2006.
[17] Kim D H, Noh J D, Jeong H. Scale-free Trees:The Skeletons of Complex Networks. Phys.Rev.E, 70: 046126, 2004.
[1] Hughes D, Walkerdine J, Coulson G, etc. Peer-to-Peer: Is Deviant Behavior the Norm on P2P File-sharing Networks? IEEE Computer Society Vol. 7, No. 2, February, 2006.
[2] Wang F, Moreno Y, Sun Y. Structure of Peer-to-Peer Social Network. Phys.Rev.E, 73: 036123, 2006.
[3] Jasch F, Blumen A. Target Problem on Small-world Networks. Phys. Rev. E, 63: 041108, 2001.
[4] 汪小帆,李翔,陈关荣. 复杂网络理论及其应用. 北京:清华大学出版社,2006.
[5] Adamic L A, Lukose R M, Puniyani A R. Search in Power-law Networks. Phys. Rev. E, 64: 046135, 2001.
[6] Adamic L A, Lukose R M, Huberman B A. Local Search in Unstructured Networks. In S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs andNetworks, Wiley-VCH, Berlin, 2003.
[7] Erd?s P, Rényi A. On the Evolution of Random Graphs. Publ. Math. Inst. Hung. Acad. Sci., 5: 17-60, 1960.
[8] Pandurangan G, Raghavan P, Upfal E. Builaing Low-diameter Peer-to-Peer Networks. IEEE J. Select. Areas Commun. , 21(6): 995-1002, 2003.
[9] Ratnasamy S, Francis P, Handley M, etc. A Scalable Content-Addressable Network. Proceedings of ACM SIGCOMM, San Diego, California, USA, 2001.
[10] Dixon C. Temporal Resolution: A Breadth-first Search Approach. Proceedings of IEEE Third International Workshop, 19-20, May, 1996.
[11] Hughes B D. Random Walks and Random Environments. Clarendon Press, Oxford, Vols. 1 and 2, 1996.
[12] Gkantsidis C, Mihail M, Saberi A. Random Walks in Peer-to-Peer Networks. IEEE Infocom, 2004.
[13] Kim B J, Yoon C N, Han S K. Path Finding Strategies in Scale-free Networks. Phys. Rev. E, 65: 027103, 2002.
[14] Ivkovic I. Improving Gnutella Protocol:Protocol Analysis and Research Proposals. Prize-Winning Paper for LimeWire Gnutella Research Contest, September, 2001.
[15] Barabási A L, Bonabeau E. Scale-free Networks. Scientific American, 50-59, May 2003.
[16] Milgram S. The Small World Problem. Psychology Today, 60-67, May 1967.
[17] Watts D J. Six Degrees: The Science of a Connected Age. New York: Norton, 2003.