A peer-to-peer recommender system based on spontaneous affinities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A peer-to-peer recommender system based on spontaneous affinities

Full text

Pdf (1.40 MB)

Source

ACM Transactions on Internet Technology (TOIT) archive
Volume 9 , Issue 1 (February 2009) table of contents

Article No. 4

Year of Publication: 2009

ISSN:1533-5399

Authors

Giancarlo Ruffo	Università degli Studi di Torino, Torino, Italy
Rossano Schifanella	Università degli Studi di Torino, Torino, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 59, Downloads (12 Months): 455, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1462159.1462163 What is a DOI?

ABSTRACT

Network analysis has proved to be very useful in many social and natural sciences, and in particular Small World topologies have been exploited in many application fields. In this article, we focus on P2P file sharing applications, where spontaneous communities of users are studied and analyzed. We define a family of structures that we call “Affinity Networks” (or even Graphs) that show self-organized interest-based clusters. Empirical evidence proves that affinity networks are small worlds and shows scale-free features. The relevance of this finding is augmented with the introduction of a proactive recommendation scheme, namely DeHinter, that exploits this natural feature. The intuition behind this scheme is that a user would trust her network of “elective affinities” more than anonymous and generic suggestions made by impersonal entities. The accuracy of the recommendation is evaluated by way of a 10-fold cross validation, and a prototype has been implemented for further feedbacks from the users.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
	2	Achacoso, T. B. and Yamamoto, W. S. 1991. AYs Neuroanatomy of C Elegans for Computation. CRC-Press.
	3	Adamic, L. A. and Huberman, B. A. 2000. The nature of markets in the world wide web. Quarterly J. Electron. Commerce 1, 512.
	4	Albert, R. and Barabasi, A. L. 2002. Statistical mechanics of complex networks. Rev. Modern Physics 74, 1.
	5	Marko Balabanović , Yoav Shoham, Fab: content-based, collaborative recommendation, Communications of the ACM, v.40 n.3, p.66-72, March 1997 [doi>10.1145/245108.245124]
	6	Albert-Laszlo Barabasi, Linked: How Everything Is Connected to Everything Else and What It Means, Plume, 2003
	7	Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509.
	8	Paul Barford , Azer Bestavros , Adam Bradley , Mark Crovella, Changes in Web client access patterns: Characteristics and caching implications, World Wide Web, v.2 n.1-2, p.15-28, 1999 [doi>10.1023/A:1019236319752]
	9	Bhalla, U. S. and Iyengar, R. 1999. Emergent properties of networks of biological signaling pathways. Science 283, 381--387.
	10	Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. 1999. Web caching and zipf-like distributions: Evidence and implications. In Proceedings of INFOCOM. 126--134.
	11	Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
	12	Claypool, M., Gokhale, A., Miranda, T., Murnikov, P., Netes, D., and Sartin, M. 1999. Combining content-based and collaborative filters in an online newspaper. In Proceedings of the ACM SIGIR Workshop on Recommender Systems: Algorithms and Evaluation. ACM.
	13	Cohen, J. E., Briand, F., and Newman, C. M. 1986. A stochastic theory of community food webs III. Predicted and observed lengths of food. Royal Soc. London Proc. Series B 228, 317--353.
	14	Cox, R. A. K., Felton, J. M., and Chung, K. C. 1995. The concentration of commercial success in popular music: an analysis of the distribution of gold records. J. Cultural Economics 19, 333--340.
	15	Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
	16	de Sola Pool, I. and Kochen, M. 1978. Contacts and influence. Social Netw. 1, 1--48.
	17	D. DeRoure , W. Hall , S. Reich , G. Hill , A. Pikrakis , M. Stairmand, MEMOIR — an open framework for enhanced navigation of distributed information, Information Processing and Management: an International Journal, v.37 n.1, p.53-74, 2001 [doi>10.1016/S0306-4573(00)00019-4]
	18	deSolla Price, D. J. 1967. Networks of scientific papers. Science 155, 3767, 1213--1219.
	19	Erdős, P. and Rényi, A. 1959. On random graphs. Publicationes Mathematicae 6.
	20	Erdős, P. and Rényi, A. 1960. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5.
	21	Erdős, P. and Rényi, A. 1961. On the strength of connectedness of a random graph. Acta Mathematica Scientia Hungary 12.
	22	Estoup, J. B. 1916. Les gammes stenographiques. Institut Stenographique de France.
	23	Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	24	David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
	25	Gutenberg, B. and Richter, R. F. 1944. Frequency of earthquakes in california. Bul. Seismological Soc. Amer. 34, 185--188.
	26	Han, P., Xie, B., Yang, F., and Shen, R. 2004. A scalable p2p recommender system based on distributed collaborative filtering. Expert Syst. Appl. 27, 2, 203--210.
	27	Hartwell, L. H., Hopfield, J. J., Leibler, S., and Murray, A. W. 1999. From molecular to modular cell biology. Nature 402, 6761 Suppl.
	28	Jonathan L. Herlocker , Joseph A. Konstan , John Riedl, Explaining collaborative filtering recommendations, Proceedings of the 2000 ACM conference on Computer supported cooperative work, p.241-250, December 2000, Philadelphia, Pennsylvania, United States [doi>10.1145/358916.358995]
	29	Howe, A. E. and Dreilinger, D. 1997. SAVVYSEARCH: A metasearch engine that learns which search engines to query. AI Mag. 18, 2, 19--25.
	30	Iamnitchi, A., Ripeanu, M., and Foster, I. 2004. Small-world file-sharing communities. In The 23rd Conference of the IEEE Communications Society (INFOCOM'04). Vol. 2. 952--963.
	31	Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., and Barabási, A. L. 2000. The large-scale organization of metabolic networks. Nature 407, 6804, 651--654.
	32	Karinthy, F. 1929. Chains. Everything is Different. Atheneum Press.
	33	Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
	34	Kleinfeld, J. S. 2001. Could it be a big world after all? the “six degrees of separation” myth. Society.
	35	Klingberg, T. and Manfredi, R. 2002. Gnutella protocol development. http://rfc-gnutella.sourceforge.net/src/rfc-0_6-draft.html (last access:1/13/09).
	36	Kohli, R. and Sah, R. 2003. Market shares: Some power law results and observations. Working paper 04.01, School of Public Policy, University of Chicago.
	37	Kohn, K. W. 1999. Molecular interaction map of the mammalian cell cycle control and DNA repair systems. Mol. Biol. Cell 10, 8, 2703--2734.
	38	Joseph A. Konstan , Bradley N. Miller , David Maltz , Jonathan L. Herlocker , Lee R. Gordon , John Riedl, GroupLens: applying collaborative filtering to Usenet news, Communications of the ACM, v.40 n.3, p.77-87, March 1997 [doi>10.1145/245108.245126]
	39	Krulwich, B. 1997. Lifestyle finder: Intelligent user profiling using large-scale demographic data. AI Maga. 18, 2, 37--45.
	40	Lang, K. 1995. NewsWeeder: learning to filter netnews. In Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann Publishers Inc. 331--339.
	41	Nathaniel Leibowitz , Matei Ripeanu , Adam Wierzbicki, Deconstructing the Kazaa Network, Proceedings of the The Third IEEE Workshop on Internet Applications, p.112, June 23-24, 2003
	42	Lotka, A. J. 1926. The frequency distribution of scientific production. J. Wash. Acad. Sci. 16, 317--323.
	43	Lu, E. T. and Hamilton, R. J. 1991. Avalanches and the distribution of solar flares. Astrophysical J. 380, L89--L92.
	44	Milgram, S. 1967. The small world problem. Psych. Today 2, 60--67.
	45	Bradley N. Miller , Joseph A. Konstan , John Riedl, PocketLens: Toward a personal recommender system, ACM Transactions on Information Systems (TOIS), v.22 n.3, p.437-476, July 2004 [doi>10.1145/1010614.1010618]
	46	Monasson, R. 1999. Diffusion, localization and dispersion relations on “small-world” lattices. European Physical J. B 12, 4, 555--567.
	47	Miquel Montaner , Beatriz López , Josep Lluís De La Rosa, A Taxonomy of Recommender Agents on theInternet, Artificial Intelligence Review, v.19 n.4, p.285-330, June 2003 [doi>10.1023/A:1022850703159]
	48	Neukum, G. and Ivanov, B. A. 1994. Crater size distributions and impact probabilities on earth from lunar, terrestrial-planet, and asteroid cratering Data. In Hazards Due to Comets and Asteroids, T. Gehrels, M. S. Matthews, and A. M. Schumann, Eds. The University of Arizona Press, 359--416.
	49	Newman, M. E. 2001. The structure of scientific collaboration networks. Proc. Nat. Acad. Sci. 98, 2, 404--409.
	50	Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45, 167.
	51	Newman, M. E. J. 2005. Power laws, pareto distributions and zipf's law. Contemp. Physics 46, 323.
	52	Newman, M. E. J. and Watts, D. J. 1999. Renormalization group analysis of the small-world network model. Physics Lett. A 263, 341--346.
	53	Toshio Oka , Hiroyuki Morikawa , Tomonori Aoyama, Vineyard: A Collaborative Filtering Service Platform in Distributed Environment, Proceedings of the 2004 Symposium on Applications and the Internet-Workshops (SAINT 2004 Workshops), p.575, January 26-30, 2004
	54	Pagallo, U. 2006. Teoria giundica della Complessità. Dalla “Polis primitiva” di Socrate ai “mondi piccoli” dellinformatica—Un approccio evolutivo. Giapichelli, Torino, Italy.
	55	Michael J. Pazzani, A Framework for Collaborative, Content-Based and Demographic Filtering, Artificial Intelligence Review, v.13 n.5-6, p.393-408, Dec. 1999 [doi>10.1023/A:1006544522159]
	56	Pazzani, M. J., Muramatsu, J., and Billsus, D. 1996. Syskill webert: Identifying interesting web sites. In Proceedings of AAAI/IAAI, Vol. 1. 54--61.
	57	Phex Team. 2003. Phex file-sharing gnutella client. http://www.phex.org/mambo/(last access: 1/13/09).
	58	Brian Pinkerton , Edward Lazowska , John Zahorjan, Webcrawler: finding what people want, University of Washington, 2000
	59	Alexandrin Popescul , Lyle H. Ungar , David M. Pennock , Steve Lawrence, Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.437-444, August 02-05, 2001
	60	Redner, S. 1998. How popular is your paper? An empirical study of the citation distribution. European Physical J. B 4, 131.
	61	Y. Rekhter , B. Moskowitz , D. Karrenberg , G. J. de Groot , E. Lear, Address Allocation for Private Internets, RFC Editor, 1996
	62	Paul Resnick , Hal R. Varian, Recommender systems, Communications of the ACM, v.40 n.3, p.56-58, March 1997 [doi>10.1145/245108.245121]
	63	Rich, E. 1979. User modeling via stereotypes. Cognitive Sci. 3, 329--354.
	64	Roberts, D. C. and Turcotte, D. L. 1998. Fractality and selforganized criticality of wars. Fractals 6, 351--357.
	65	Giancarlo Ruffo , Rossano Schifanella, Evaluating peer-to-peer recommender systems that exploit spontaneous affinities, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244338]
	66	Ruffo, G., Schifanella, R., and Ghiringhello, E. 2006. A decentralized recommendation system based on self-organizing partnerships. Lecture Notes in Computer Science, vol. 3976. Springer, 618--629.
	67	Badrul M. Sarwar , Joseph A. Konstan , Al Borchers , Jon Herlocker , Brad Miller , John Riedl, Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.345-354, November 14-18, 1998, Seattle, Washington, United States [doi>10.1145/289444.289509]
	68	Rossano Schifanella , André Panisson , Cristina Gena , Giancarlo Ruffo, MobHinter: epidemic collaborative filtering and self-organization in mobile ad-hoc networks, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454014]
	69	Seglen, P. O. 1992. The skewness of science. J. Amer. Soc. Inform. Sci. 43, 9, 628--638.
	70	Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
	71	Sripanidkulchai, K., Maggs, B., and Zhang, H. 2003. Efficient content location using interest-based locality in peer-topeer systems. In Proceedings of the InfoCom.
	72	Daniel Stutzbach , Reza Rejaie , Subhabrata Sen, Characterizing unstructured overlay topologies in modern P2P file-sharing systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.5-5, October 19-21, 2005, Berkeley, CA
	73	Terveen, L. and Hill, W. 2001. Beyond recommender systems: Helping people help each other. In HCI in the New Millennium. Addison-Wesley, 487--509.
	74	Amund Tveit, Peer-to-peer based recommendations for mobile commerce, Proceedings of the 1st international workshop on Mobile commerce, p.26-29, July 2001, Rome, Italy [doi>10.1145/381461.381466]
	75	von Goethe, J. W. 1809. Die Wahlverwandtschaften. http://en.wikipedia.org/wiki/Elective_Affinities.
	76	Jun Wang , Marcel J. T. Reinders , Reginald L. Lagendijk , Johan Pouwelse, Self-organizing distributed collaborative filtering, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076177]
	77	Wasserman, S. and Faust, K. 1994. Social Network Analysis. Cambridge University Press, Cambridge, U.K.
	78	Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
	79	Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 6684, 440--442.
	80	Yan Zheng Wei , Luc Moreau , Nicholas R. Jennings, A market-based approach to recommender systems, ACM Transactions on Information Systems (TOIS), v.23 n.3, p.227-266, July 2005 [doi>10.1145/1080343.1080344]
	81	Williams, R. J. and Martinez, N. D. 2000. Simple rules yield complex food webs. Nature 404, 6774, 180--183.
	82	Willis, J. C. and Yule, G. U. 1922. Some statistics of evolution and geographical distribution in plants and animals, and their significance. Nature 109, 177--179.
	83	Bo Xie , Peng Han , Ruimin Shen, PipeCF: a scalable DHT-based collaborative filtering recommendation system, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013407]
	84	Tak W. Yan , Hector Garcia-Molina, SIFT: a tool for wide-area information dissemination, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.15-15, January 16-20, 1995, New Orleans, Louisiana
	85	Zanette, D. H. and Manrubia, S. C. 2001. Vertical transmission of culture and the distribution of family names. Physica A: Statist. Mechanics Appl. 295, 1-2, 1--8.

CITED BY 2

	Alessandro Basso , Marco Milanesio , Giancarlo Ruffo, Events discovery for personal video recorders, Proceedings of the seventh european conference on European interactive television conference, June 03-05, 2009, Leuven, Belgium
	Francesca Carmagnola , Andrea Loffredo , Giorgio Berardi, Vcast on facebook: bridging social and similarity networks, Proceedings of the 20th ACM conference on Hypertext and hypermedia, June 29-July 01, 2009, Torino, Italy