×

An adaptive overlay network inspired by social behaviour. (English) Zbl 1233.68044

Summary: Nature is a great source of inspiration for scientists, because natural systems seem to be able to find the best way to solve a given problem by using simple and robust mechanisms. Studying complex natural systems, scientists usually find that simple local dynamics lead to sophisticated macroscopic structures and behaviour. It seems that some kind of local interaction rules naturally allow the system to auto-organize itself as an efficient and robust structure, which can easily solve different tasks. Examples of such complex systems are social networks, where a small set of basic interaction rules leads to a relatively robust and efficient communication structure. In this paper, we present PROSA, a semantic peer-to-peer (P2P) overlay network inspired by social dynamics. The way queries are forwarded and links among peers are established in PROSA resemble the way people ask other people for collaboration, help or information. Behaving as a social network of peers, PROSA naturally evolves to a small world, where all peers can be reached in a fast and efficient way. The underlying algorithm used for query forwarding, based only on local choices, is both reliable and effective: peers sharing similar resources are eventually connected with each other, allowing queries to be successfully answered in a really small amount of time. The resulting emergent structure can guarantee fast responses and good query recall.

MSC:

68M14 Distributed systems

Software:

Python
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lada A. Adamic, Zipf, power-laws, and Pareto – a ranking tutorial
[2] Albert, Reka; Barabasi, Albert-Laszlo: Statistical mechanics of complex networks, Reviews of modern physics 74, 47 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[3] Bawa, Mayank; Manku, Gurmeet Singh; Raghavan, Prabhakar: Sets: search enhanced by topic segmentation, , 306-313 (2003)
[4] Mark Buchanan, Nexus: Small Worlds and the Groundbreaking Theory of Networks, 2003
[5] V. Carchiolo, M. Malgeri, G. Mangioni, V. Nicosia, Social behaviours applied to p2p systems: An efficient algorithm for resources organisation, in: 2nd International Workshop on Collaborative P2P Information Systems, COPS 2006, Manchester, 2006 · Zbl 1233.68044
[6] V. Carchiolo, M. Malgeri, G. Mangioni, V. Nicosia, Efficient searching and retrieval of documents in prosa, in: Fourth International Workshop on Databases, Information Systems and P2P Computing, DBISP2P06–AAMAS 2006, 2006
[7] V. Carchiolo, M. Malgeri, G. Mangioni, V. Nicosia, On robustness and self-adaptiveness of a socially inspired p2p network, in: Computer and Information Sciences, ISCIS 2007, 22nd International Symposium on, 2007, pp. 1–6 · Zbl 1233.68044
[8] Crespo, Arturo; Garcia-Molina, Hector: Routing indices for peer-to-peer systems, , 23 (2002)
[9] Chris GauthierDickey, Christian Grothoff, Bootstrapping of peer-to-peer networks, Turku, Finland, 1/8/2008 2008, IEEE
[10] Gnutella website, World Wide Web. http://www.gnutella.com
[11] Peter Haase, Jeen Broekstra, Marc Ehrig, Maarten Menken, Peter Mika, Michal Plechawski, Pawel Pyszlak, Björn Schnizler, Ronny Siebes, Steffen Staab, Christoph Tempich, Bibster – A semantics-based bibliographic peer-to-peer system, in: Proceedings of the International Semantic Web Conference, ISWC2004, November 2004
[12] I. Jawhar, J. Wu, A two-level random walk search protocol for peer-to-peer networks, in: Proc. of the 8th World Multi-Conference on Systemics, Cybernetics and Informatics, 2004
[13] , Journal of political philosophy (1998–2006)
[14] , Journal of social philosophy (1998–2006)
[15] , Journal of the American mathematical society (1998–2006)
[16] Kalogeraki, Vana; Gunopulos, Dimitrios; Zeinalipour-Yazti, D.: A local search mechanism for peer-to-peer networks, , 300-307 (2002) · Zbl 1102.68406
[17] Li, Xiuqi; Wu, Jie: Searching techniques in peer-to-peer networks, , 613-642 (2006)
[18] Löeser, Alexander; Staab, Steffen; Tempich, Christoph: Semantic social overlay networks, IEEE JSAC – journal on selected areas in communication 25, No. 1 (2007)
[19] B.T. Loo, R. Huebsch, I. Stoica, J.M. Hellerstein, The case for a hybrid p2p search infrastructure, in: Proceedings of the 3rd International Workshop on Peer–to–Peer Systems, IPTPS, February 2004
[20] Lusseau, David; Newman, M. E. J.: Identifying the role that individual animals play in their social network, Proceedings of the royal society of London, series B 271, S477 (2004)
[21] Lv, Qin; Cao, Pei; Cohen, Edith; Li, Kai; Shenker, Scott: Search and replication in unstructured peer-to-peer networks, , 84-95 (2002)
[22] Milgram, S.: The small world problem, Psychol today 2, 60-67 (1967)
[23] Newman, M. E. J.: Models of the small world: A review, Journal of statistical physics 101, 819 (2000) · Zbl 1049.82520 · doi:10.1023/A:1026485807148
[24] Newman, M. E. J.: The structure of scientific collaboration networks, Proceedings of the national Academy of sciences of the united states of America 98, 404 (2001) · Zbl 1065.00518 · doi:10.1073/pnas.021544898
[25] Newman, M. E. J.: The structure and function of complex networks, SIAM review 45, 167 (2003) · Zbl 1029.68010 · doi:10.1137/S003614450342480
[26] Newman, M. E. J.: Scientific collaboration networks. Ii. shortest paths, weighted networks, and centrality, Physical review E 64, 016132 (2001)
[27] Newman, M. E. J.; Park, Juyong: Why social networks are different from other types of networks, Physical review E 68, 036122 (2003)
[28] Newman, M. E. J.; Strogatz, S. H.; Watts, D. J.: Random graphs with arbitrary degree distributions and their applications, Physical review E 64, 026118 (2001)
[29] Juyong Park, Oscar Celma, Markus Koppenberger, Pedro Cano, Javier M. Buldu, The social network of contemporary popular musicians, 2006 · Zbl 1185.91145
[30] , Philosophical issues (1998–2006)
[31] , Philosophical perspectives (1998–2006)
[32] , Proceedings of the American mathemetical society (1998–2006)
[33] Rhea, S. C.; Kubiatowicz, J.: Probabilistic location and routing, INFOCOM 2002, twenty-first annual joint conference of the IEEE computer and communications societies, Proceedings 3, 1248-1257 (2002)
[34] Rostami, Habib; Habibi, Jafar; Livani, Emad: Semantic routing of search queries in p2p networks, Journal of parallel and distributed computing 68, No. 12, 1590-1602 (2008)
[35] Gerard Salton, Chris Buckley, Term weighting approaches in automatic text retrieval, Technical Report, Ithaca, NY, USA, 1987 · Zbl 1226.68035
[36] H. Schutze, C. Silverstein, A comparison of projections for efficient document clustering, in: Proceedings of ACM SIGIR, Philadelphia, PA, July 1997, pp. 74–81
[37] Parongama Sen, Complexities of social networks: A physicist’s perspective, 2006
[38] Kunwadee Sripanidkulchai, The popularity of Gnutella queries and its implications on scalability, World Wide Web. http://www.cs.cmu.edu/kunwadee/research/p2p/gnutella.html · Zbl 1014.68868
[39] , Lecture notes on computer science 3485 (2005)
[40] The python programming language http://www.python.org
[41] , Transactions of the American mathemetical society (1998–2006)
[42] D. Tsoumakos, N. Roussopoulos, Adaptive probabilistic search in peer-to-peer networks, in: Proc. of the 2nd International Workshop on Peer-to-Peer Systems, IPTPS 03, 2003
[43] Wang, Fang; Moreno, Yamir; Sun, Yaoru: Structure of peer-to-peer social networks, Physical review E 73, 036123 (2006)
[44] Watts, Duncan J.; Strogatz, Steven H.: Collective dynamics of small-world networks, Nature 393, 440-442 (1998) · Zbl 1368.05139
[45] Williams, R. J.; Berlow, E. L.; Dunne, J. A.; Barabasi, A. -L.; Martinez, N. D.: Two degrees of separation in complex food webs, Proceedings of the national Academy of sciences 99, 12913-12916 (2002)
[46] Yang, Beverly; Garcia-Molina, Hector: Improving search in peer-to-peer networks, , 5 (2002) · Zbl 1022.68506
[47] C. Yang, J. Wu, A dominating-set-based routing in peer-to-peer networks, in: Proc. of the 2nd International Workshop on Grid and Cooperative Computing Workshop, GCC’03, 2003
[48] Zhuge, Hai: Resource space model, its design method and applications, Journal of system software 72, No. 1, 71-81 (2004)
[49] Zhuge, H.; Li, X.: Rsm-based gossip on p2p network, Lecture notes in computer science 4494, 1-12 (2007)
[50] Zhu, Yingwu; Yang, Xiaoyu; Hu, Yiming: Making search efficient on Gnutella-like p2p systems, (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.