The number of items that users can now access when navigating on the Web is so huge that these might feel lost. Recommender systems are a way to cope with this profusion of data by suggesting items that fit the users needs. One of the most popular techniques for recommender systems is the collaborative filtering approach that relies on the preferences of items expressed by users, usually under the form of ratings. In the absence of ratings, classical collaborative filtering techniques cannot be applied. Fortunately, the behavior of users, such as their consultations, can be collected. In this paper, we present a new approach to perform collaborative filtering when no rating is available but when user consultations are known. We propose to take inspiration from local community detection algorithms to form communities of users and deduce the set of mentors of a given user. We adapt one state-of-the-art algorithm so as to fit the characteristics of collaborative filtering. Experiments conducted show that the precision achieved is higher then the baseline that does not perform any mentor selection. In addition, our model almost offsets the absence of ratings by exploiting a reduced set of mentors. 1. Introduction The democratization of Internet and network technologies has resulted in a large increase of information, readily accessible to everybody. This growth had been an advantage during its first years as the access to information became generalized. However, the volume of information is now so enormous that users cannot easily get the information they search for and are drowned in the mass of resources. This overabundance has very often the effect of leading to unsatisfied users. As a consequence, a critical issue of the current Web applications is the incorporation of mechanisms for delivering information that fits users' needs, whilst increasing their satisfaction. Recommender systems (RSs) provide users with personalized recommendations of resources or items, based on the knowledge they have about users. A recent observation showed that users are now aware of their need to be assisted [1] and are prepared to adopt recommender systems [2]. The increasing popularity of these systems in information seeking or commercial e-services has meant that the need for quality, accuracy, and reliability of recommendations has become tremendous. Recommender systems generally fall into three categories: content-based systems which compute recommendations from the semantic content of items [3], knowledge-based systems where recommendations rely on knowledge about the
References
[1]
I. ChoiceStream, “Choicestream personalization survey,” 2006.
[2]
S. Castagnos, N. Jones, and P. Pu, “Eye-tracking product recommender's usage,” in Proceedings of the 4th ACM Conference on Recommender Systems (RecSys '10), pp. 29–36, Barcelona, Spain, 2010.
[3]
M. Pazzani and D. Billsus, “The adaptive web,” in Content-Based Recommendation Systems, Springer, Berlin, Germany, 2007.
[4]
R. D. Burke, K. J. Hammond, and B. C. Young, “Knowledge-based navigation of complex information spaces,” in Proceedings of the 13th National Conference on Artificial Intelligence (AAAI '96), vol. 1, pp. 462–468, Portland, Ore, USA, August 1996.
[5]
D. Goldberg, D. Nichols, B. Oki, and D. Terry, “Using collaborative filtering to weave an information tapestry,” Communications of the ACM, vol. 35, no. 12, pp. 61–70, 1992.
[6]
J. Wang, A. P. de Vries, and M. J. T. Reinders, “Unifying user-based and item-based collaborative filtering approaches by similarity fusion,” in Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 501–508, Seatttle, Wash, USA, August 2006.
[7]
S. Bruninghaus and K. D. Ashley, “Toward adding knowledge to learning algorithms for indexing legal cases,” in Proceedings of the 7th International Conference on Artificial Intelligence and Law, pp. 9–17, June 1999.
[8]
K.-Y. Jung, D.-H. Park, and J.-H. Lee, “Hybrid collaborative filtering and content-based filtering for improved recommender system,” in Proceedings of the International Conference on Computational Science (ICCS '04), vol. 3036 of Lecture Notes in Computer Science, pp. 295–302, 2004.
[9]
J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl, “Evaluating collaborative filtering recommender systems,” ACM Transactions on Information Systems, vol. 22, no. 1, pp. 5–53, 2004.
[10]
A. Brun, A. Hamad, O. Buffet, and A. Boyer, “Towards preference relations in recommender systems,” in Proceedings of the Workshop on Preference Learning, European Conference on Machine Learning and Principle and Practice of Knowledge Discovery in Databases (ECML-PKDD '10), 2010.
[11]
S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3–5, pp. 75–174, 2009.
[12]
J. Chen, R. Zaane, and R. Goebel, “Local community identification in social networks,” in Proceedings of the Advances in Social Network Analysis and Mining, pp. 237–242, 2009.
[13]
J. Breese, D. Heckerman, and C. Kadie, “Empirical analysis of predictive algorithms for collaborative filtering,” in Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI '98), 1998.
[14]
B. M. Sarwar, G. Karypis, J. Konstan, and J. Reidl, “Item-based collaborative filtering recommendation algorithms,” in Proceedings of the 10th International Conference on World Wide Web (WWW '01), pp. 285–295, 2001.
[15]
L. Candillier, F. Meyer, and M. Boullé, “Comparing state-of-the-art collaborative filtering systems,” in Proceedings of the 5th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM '07), vol. 4571 of Lecture Notes in Computer Science, pp. 548–562, Leipzig, Germany, July 2007.
[16]
S. Castagnos and A. Boyer, “A client/server user-based collaborative filtering algorithm: model and implementation,” in Proceedings of the 17th European Conference on Artificial Intelligence (ECAI '06), pp. 617–621, 2006.
[17]
S. Castagnos and A. Boyer, “Personalized communities in a distributed recommender system,” in Proceedings of the 29th European Conference on IR Research (ECIR '07), vol. 4425 of Lecture Notes in Computer Science, pp. 343–355, Rome, Italy, April 2007.
[18]
N. Lathia, S. Hailes, and L. Capra, “Trust-based collaborative filtering,” International Federation for Information Processing, vol. 263, pp. 119–134, 2008.
[19]
G. Amati, C. Carpineto, and G. Romano, “An effective threshold-based neighbor selection in collaborative filtering,” in Proceedings of European Conference on Information Retrieval (ECIR '07), pp. 712–715, 2007.
[20]
J. Herlocker, J. Konstan, A. Borchers, and J. Riedl, “An algorithmic framework for performing collaborative filtering,” in Proceedings of the SIGIR Conference, pp. 230–237, 1999.
[21]
M. Grcar, B. Fortuna, and D. Mladenic, “kNN versus SVM in the collaborative filtering framework,” in Proceedings of the 7th WEBKDD Workshop on Knowledge Discovery from the Web (WEBKDD '05), 2005.
[22]
B. Mobasher, R. Burke, and J. J. Sandvig, “Model-based collaborative filtering as a defense against profile injection attacks,” in Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference (AAAI '06), vol. 2, pp. 1388–1393, Boston, Mass, USA, July 2006.
[23]
L. Terán and A. Meier, “A fuzzy recommender system for eElections,” in Proceedings of the 1st International Conference on Electronic Government and Information Systems Perspective (EGOVIS '10), vol. 6267 of Lecture Notes in Computer Science, pp. 62–76, Bilbao, Spain, August-September 2010.
[24]
M. O’Connor and J. Herlocker, “Clustering items for collaborative filtering,” in Proceedings of the 22nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '99), 1999.
[25]
L. Ungar and D. Foster, “Clustering methods for collaborative filtering,” in Proceedings of AAAI Workshop on Recommendation Systems, 1998.
[26]
A. M. Martinez, P. Mittrapiyanuruk, and A. C. Kak, “On combining graph-partitioning with non-parametric clustering for image segmentation,” Computer Vision and Image Understanding, vol. 95, no. 1, pp. 72–85, 2004.
[27]
P. S. Bradley and U. M. Fayyad, “Refining initial points for -means clustering,” in Proceedings of the 15th International Conference on Machine Learning (ICML '98), pp. 91–99, Morgan Kaufmann, May 1998.
[28]
P. Perny and J. Zucker, “Collaborative filtering methods based on fuzzy preference relations,” in Proceedings of the 4th Meeting of the Euro Working Group on Fuzzy Sets (EUROFUSE-SIC '99), 1999.
[29]
R. A. Jarvis and E. A. Patrick, “Clustering using a similarity measure based on shared near neighbors,” IEEE Transactions on Computers, vol. 22, no. 11, pp. 1025–1034, 1973.
[30]
L. Ert？z, M. Steinbach, and V. Kumar, “Information retrivial and clustering,” in Finding Topics in Collections of Documents: A Shared Nearest Neighbor Approach, W. Wu, H. Xiong, and S. Shekhar, Eds., 2002.
[31]
S. Guha, R. Rastogi, and K. Shim, “CURE: an efficient clustering algorithm for large databases,” in Proceedings of the ACM-SIGMOD International Conference on Management of Data (SIGMOD '98), no. 2, pp. 73–84, 1998.
[32]
J. Yin, X. Fan, Y. Chen, and J. Ren, “High-dimensional shared nearest neighbor clustering algorithm,” in Proceedings of the 2nd International Conference on Fuzzy Systems and Knowledge Discovery (FSKD '05), vol. 3614 of Lecture Notes in Computer Science, pp. 494–502, Changsa, China, August 2005.
[33]
G. Xue, C. Lin, Q. Yang, et al., “Scalable collaborative filtering using cluster-based smoothing,” in Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '05), 2005.
[34]
N. Srinivasa and S. Medasani, “Active fuzzy clustering for collaborative filtering,” in Proceedings of IEEE International Conference on Fuzzy Systems, pp. 1697–1702, July 2004.
[35]
J. B. Schafer, J. A. Konstan, and J. Riedl, “E-commerce recommendation applications,” Data Mining and Knowledge Discovery, vol. 5, no. 1-2, pp. 115–153, 2001.
[36]
X.-M. Jiang, W.-G. Song, and W.-G. Feng, “Optimizing collaborative filtering by interpolating the individual and group behaviors,” in Proceedings of the 8th Asia-Pacific Web Conference (APWeb '06), vol. 3841 of Lecture Notes in Computer Science, pp. 568–578, Harbin, China, January 2006.
[37]
D. Oard and J. Kim, “Implicit feedback for recommender systems,” in Proceedings of the AAAI Workshop on Recommender Systems, pp. 81–83, 1998.
[38]
S. Castagnos, Modélisation de comportements et apprentissage stochastique non supervisé de stratégies d’interactions sociales au sein de systèmes temps réel de recherche et d’accès à l’information, Ph.D. thesis, Nancy University, 2008.
[39]
S. Castagnos and A. Boyer, “Privacy concerns when modeling users in collaborative filtering recommender systems,” in Social and Human Elements of Information Security: Emerging Trends and Countermeasures, 2008.
[40]
G. Karypis, “Evaluation of item-based top-N recommendation algorithms,” in Proceedings of the ACM 10th International Conference on Information and Knowledge Management (CIKM '01), pp. 247–254, November 2001.
[41]
G. Linden, B. Smith, and J. York, “Amazon.com recommendations: item-to-item collaborative filtering,” IEEE Internet Computing, vol. 7, no. 1, pp. 76–80, 2003.
[42]
C. Miranda and A. M. Jorge, “Incremental collaborative filtering for binary ratings,” in Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence (WI '08), pp. 389–392, Sydney, Australia, December 2008.
[43]
J. Redpath, D. H. Glass, S. McClean, and L. Chen, “Collaborative filtering: the aim of recommender systems and the significance of user ratings,” in Proceedings of the 32nd European Conference on Information Retrieval (ECIR '10), vol. 5993 of Lecture Notes in Computer Science, pp. 394–406, Milton Keynes, UK, March 2010.
[44]
B. Mobasher, H. Dai, T. Luo, and M. Nakagawa, “Improving the effectiveness of collaborative filtering on anonymous web usage data,” in Proceedings of the IJCAI 2001 Workshop on Intelligent Techniques for Web Personalization (ITWP '01), 2001.
[45]
G. Bonnin, A. Brun, and A. Boyer, “Web Intelligence and Intelligent Agents, chap. Skipping-Based Collaborative Recommendations Inspired from Statistical Language Modeling,” Zeeshan-ul-Hassan Usmani, March 2010.
[46]
G. W. Flake, R. Tarjan, and K. Tsioutsiouliklis, “Graph clustering and minimum cut trees,” Internet Mathematics, vol. 1, no. 4, pp. 385–408, 2004.
[47]
D. Zhou, J. Huang, and B. Sch？lkopf, “Learning from labeled and unlabeled data on a directed graph,” in Proceedings of the 22nd International Conference on Machine Learning (ICML'05), pp. 1036–1043, 2005.
[48]
K. Tsuda and W. S. Noble, “Learning kernels from biological networks by maximizing entropy,” Bioinformatics, vol. 20, no. 1, pp. 326–333, 2004.
[49]
J. Callut, K. Franoisse, M. Saerens, and P. Dupont, “Semi-supervised classification in graphs using bounded random walks,” in Proceedings of the 17th Annual Machine Learning Conference of Belgium and the Netherlands (BENELEARN '08), pp. 67–68, 2008.
[50]
S. E. Schaeffer, “Graph clustering,” Computer Science Review, vol. 1, no. 1, pp. 27–64, 2007.
[51]
S. Papadopoulos, Y. Kompatsiaris, and A. Vakali, “Leveraging collective intelligence through community detection in tag networks,” in Proceedings of Workshop on Collective Knowledge Capturing and Representation (CKCaR '09), 2009.
[52]
M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences of the United States of America, vol. 99, no. 12, pp. 7821–7826, 2002.
[53]
N. Mishra, R. Schreiber, I. Stanton, and R. E. Tarjan, “Clustering social networks,” in Proceedings of Weaving the Astronomy Web (WAW '07), Lecture Notes in Computer Science, pp. 56–67, 2007.
[54]
P. Wanjantuk and J. A. Keane, “Finding related documents via communities in the citation graph,” in Proceedings of the IEEE International Symposium on Communications and Information Technologies (ISCIT '04), vol. 1, pp. 445–450, Sapporo, Japan, October 2004.
[55]
M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proceedings of the National Academy of Sciences of the United States of America, vol. 105, no. 4, pp. 1118–1123, 2008.
[56]
G. W. Flake, S. Lawrence, and C. L. Giles, “Efficient identification of web communities,” in Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '01), pp. 150–160, Boston, Mass, USA, August 2000.
[57]
Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos, “Epidemic spreading in real networks: an eigenvalue viewpoint,” in Proceedings of the 22nd International Symposium on Reliable Distributed Systems (SRDS '03), pp. 25–34, Florence, Italy, October 2003.
[58]
Y. Qi, F. Balem, C. Faloutsos, J. Klein-Seetharaman, and Z. Bar-Joseph, “Protein complex identification by supervised graph local clustering,” BioInformatics, vol. 24, no. 13, pp. 250–268, 2008.
[59]
L. Tang, “Community detection in social networks,” http://www.public.asu.edu/~huanliu/dmml_presentation/2008/.
[60]
R. Alba, “A graph-theoretic definition of a sociometric clique,” Journal of Mathematical Sociology, pp. 112–126, 1973.
[61]
L. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, pp. 35–41, 1977.
[62]
H. Ino, M. Kudo, and A. Nakamura, “Partitioning of web graphs by community topology,” in Proceedings of the 14th International Conference on World Wide Web, pp. 661–669, 2005.
[63]
B. Yang, W. K. Cheung, and J. Liu, “Community mining from signed social networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 10, pp. 1333–1348, 2007.
[64]
S. Gregory, “An algorithm to find overlapping community structure in networks,” in Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD '07), vol. 4702 of Lecture Notes in Computer Science, pp. 91–102, Warsaw, Poland, September 2007.
[65]
J. Scott, Social Network Analysis: A Handbook, Sage, London, UK, 2nd edition, 2000.
[66]
D. Chakrabarti, “AutoPart: parameter-free graph partitioning and outlier detection,” in Proceedings of the Principles and Practice of Knowledge Discovery in Databases Conference (PKDD '04), vol. 3202 of Lecture Notes in Computer Science, pp. 112–124, 2004.
[67]
A. Pother, “Graph partitioning algorithms with applications to scientific computing,” Tech. Rep., Norfolk, Va, USA, 1997.
[68]
F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Paris, “Defining and identifying communities in networks,” Proceedings of the National Academy of Sciences of the United States of America, vol. 101, no. 9, pp. 2658–2663, 2004.
[69]
A. Clauset, M. Newmann, and C. Moore, “Finding community structure in very large networks,” Physical Review, vol. 72, 2005.
[70]
F. Luo, J. Z. Wang, and E. Promislow, “Exploring local community structures in large networks,” in Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence (WI '06), pp. 233–239, December 2006.
[71]
L. Branting, “Incremental detection of local community structure,” in Proceedings of the International Conference on Advances in Social Networks Analysis and Mining, pp. 80–87, 2010.
[72]
J. Tian, D. Chen, and Y. Fu, “A new local algorithm for detecting communities in networks,” in Proceedings of the 1st International Workshop on Education Technology and Computer Science (ETCS '09), vol. 2, pp. 721–724, Wuhan, China, March 2009.
[73]
Q. Song and N. Kasabov, “Foundations of cognitive science,” in ECM—A Novel On-Line, Evolving Clustering Method and Its Applications, M. I. Posner, Ed., pp. 631–682, 2001.
[74]
J. G. Booth, G. Casella, and J. P. Hobert, “Clustering using objective functions and stochastic search,” Journal of the Royal Statistical Society B, vol. 70, no. 1, pp. 119–139, 2008.
[75]
C. C. Aggarwal, J. L. Wolf, K. lung Wu, and P. S. Yu, “Horting hatches an egg: a new graph-theoretic approach to collaborative filtering,” in Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 201–212, ACM Press, 1999.
[76]
M. D. Ekstrand, P. Kannan, J. A. Stemper, J. T. Butler, J. A. Konstan, and J. T. Riedl, “Automatically building research reading lists,” in Proceedings of the 4th ACM Conference on Recommender Systems (RecSys '10), pp. 159–166, Barcelona, Spain, September 2010.
[77]
P. Viappiani, B. Faltings, and P. Pu, “Preference-based search using example-critiquing with suggestions,” Journal of Artificial Intelligence Research, vol. 27, pp. 465–503, 2006.
[78]
V. Schickel-Zuber and B. Faltings, “Using hierarchical clustering for learning theontologies used in recommendation systems,” in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '07), pp. 599–608, San Jose, Calif, USA, August 2007.
[79]
L. Baltrunas and F. Ricci, “Dynamic item weighting and selection for collaborative filtering,” in Web Mining 2.0 Workshop, ECML-PKDD, Springer, 2007.
[80]
C. Ziegler, Towards decentralized recommender systems, Ph.D. thesis, Albert-Ludwigs-Universitt Freiburg, 2005.
[81]
A. Brun, G. Bonnin, and A. Boyer, “History dependent recommender systems based on partial matching,” in Proceedings of the 17th International Conference on User Modeling, Adaptation, and Personalization (UMAP '09), vol. 5535 of Lecture Notes in Computer Science, pp. 343–348, Trento, Italy, June 2009.
[82]
U. Shardanand and P. Maes, “Social information filtering: algorithms for automating "word of mouth",” in Proceedings of the Conference on Human Factors in Computing Systems (CHI '95), vol. 1, pp. 210–217, May 1995.
[83]
J. Herlocker, J. A. Konstan, and J. Riedl, “An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms,” Information Retrieval, vol. 5, no. 4, pp. 287–310, 2002.
[84]
R. Burke and B. Mobasher, “Trust and bias in multi-agent recommender systems,” in Proceedings of Workshop on Multi-Agent Information Retrieval and Recommender Systems, in Conjunction with the 19th International Joint Conference on Artificial Intelligence (IJCAI '05), Edinburgh, Scotland, 2005.
