An online blog reading system by topic clustering and personalized ranking

ABSTRACT

There is an increasing number of people reading, writing, and commenting on blogs. According to a recent survey made by Technorati, there are about 75,000 new blogs and 1.2 million new posts everyday. However, it is difficult and time consuming for a blog reader to find the most interesting posts in the huge and dynamic blog world. In this article, an online Personalized Blog Reader (PBR) system is proposed, which facilitates blog readers in browsing the coolest and newest blog posts of their interests by automatically clustering the most relevant stories. PBR aims to make a user's potential favorite topics always ranked higher than those nonfavorite ones. This is accomplished in the following steps. First, the system collects and provides a unified incremental index of posts coming from different blogs. Then, an incremental clustering algorithm with a flexible half-bounded window of observation is proposed to satisfy the requirements of online processing. It learns people's personalized reading preferences to present a user with a final reading list. The experimental results show that the proposed incremental clustering algorithm is effective and efficient, and the personalization of the PBR performs well.

REFERENCES

• 1: Adar, E., Zhang, L., Adamic, L. A., and Lukose, R. M. 2004. Implicit structure and the dynamics of blogspace. In Proceedings of the 13th International World Wide Web Conference Workshop on the Weblogging Ecosystem. 35--39.
• 2: James Allan , Ron Papka , Victor Lavrenko, On-line new event detection and tracking, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.37-45, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290954]
• 3: Avesani, P., Cova, M., Hayes, C., and Massa, P. 2005. Learning contextualised Weblog topics. In Proceedings of the 2nd Annual Workshop on the Weblogging Ecosystem: Aggregation, Analysis and Dynamics, E. Adar, N. Glance, and M. Hurst, Eds.
• 4: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 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: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 7: Nilesh Bansal , Fei Chiang , Nick Koudas , Frank Wm. Tompa, Seeking stable clusters in the blogosphere, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 8: Nilesh Bansal , Nick Koudas, BlogScope: a system for online analysis of high volume text streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 9: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 10: Bonett, M. 2001. Personalization of Web services: Opportunities and challenges. Ariadne 28.
• 11: Thorsten Brants , Francine Chen , Ayman Farahat, A System for new event detection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860495]
• 12: Brooks, C. H. and Andmontanez, N. 2005. An analysis of the effectiveness of tagging in blogs. In AAAI Spring Symposium on Computational Approaches to Analyzing Weblogs, vol. 4737, 1--20.
• 13: Steve Cayzer, Semantic blogging and decentralized knowledge management, Communications of the ACM, v.47 n.12, December 2004 [doi>10.1145/1035134.1035164]
• 14: Jilin Chen , Jun Yan , Benyu Zhang , Qiang Yang , Zheng Chen, Diverse Topic Phrase Extraction through Latent Semantic Analysis, Proceedings of the Sixth International Conference on Data Mining, p.834-838, December 18-22, 2006 [doi>10.1109/ICDM.2006.61]
• 15: Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., and Harshman, R. 1990. Indexing by latent semantic analysis. J. Amer. Soc. Inform. Sci. 41, 6, 391--407.
• 16: Delwiche, A. 2005. Agenda-setting, opinion leadership, and the world of Weblogs. First Monday, 10, 12.
• 17: Weiguo Fan , Michael D. Gordon , Praveen Pathak, Discovery of Context-Specific Ranking Functions for Effective Information Retrieval Using Genetic Programming, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.523-527, April 2004 [doi>10.1109/TKDE.2004.1269663]
• 18: Weiguo Fan , Michael D. Gordon , Praveen Pathak, Genetic Programming-Based Discovery of Ranking Functions for Effective Web Search, Journal of Management Information Systems, v.21 n.4, p.37-56, Number 4/Spring 2005
• 19: Paolo Ferragina , Antonio Gulli, A personalized search engine based on web-snippet hierarchical clustering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062760]
• 20: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 21: Ioannis Giotis , Venkatesan Guruswami, Correlation clustering with a fixed number of clusters, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1167-1176, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109686]
• 22: Michael Gordon , Weiguo (Patrick) Fan , Praveen Pathak, Adaptive Web Search: Evolving a Program That Finds Information, IEEE Intelligent Systems, v.21 n.5, p.72-77, September 2006 [doi>10.1109/MIS.2006.86]
• 23: Hayes, C., Avesani, P., and Veeramachaneni, S. 2006a. An analysis of the use of tags in a blog recommender system. ITC-IRST Tech. rep., IJCAI: 2772--2777.
• 24: Hayes, C., Avesani, P., and Veeramachaneni, S. 2006b. An analysis of bloggers and topics for a blog recommender system. In Proceedings of the 7th European Conference on Machine Learning and the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD) Workshop on Web Mining.
• 25: Susan C. Herring , Inna Kouper , John C. Paolillo , Lois Ann Scheidt , Michael Tyworth , Peter Welsch , Elijah Wright , Ning Yu, Conversations in the Blogosphere: An Analysis "From the Bottom Up", Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 4, p.107.2, January 03-06, 2005 [doi>10.1109/HICSS.2005.167]
• 26: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 27: Mark Kantrowitz , Behrang Mohit , Vibhu Mittal, Stemming and its effects on TFIDF ranking (poster session), Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.357-359, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345650]
• 28: Karger, D. R. and Quan, D. 2005. What would it mean to blog on the semantic Web. Web In Semantics: Science, Services and Agents on the World Wide Web, vol. 3, 147--157.
• 29: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 30: Jerome Kelleher , Derek Bridge, An Accurate and Scalable Collaborative Recommender, Artificial Intelligence Review, v.21 n.3-4, p.193-213, June 2004 [doi>10.1023/B:AIRE.0000036255.53433.26]
• 31: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 32: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 33: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the bursty evolution of blogspace, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775233]
• 34: Fang Liu , Clement Yu , Weiyi Meng, Personalized Web Search For Improving Retrieval Effectiveness, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.28-40, January 2004 [doi>10.1109/TKDE.2004.1264820]
• 35: S. Mancoridis , B. S. Mitchell , C. Rorres , Y. Chen , E. R. Gansner, Using Automatic Clustering to Produce High-Level System Organizations of Source Code, Proceedings of the 6th International Workshop on Program Comprehension, p.45, June 24-26, 1998
• 36: Marlow, C. 2004. Audience, structure and authority in the Weblog community. In Proceedings of the International Communication Association Conference.
• 37: Page, L., Brin, S., Motwani, R., and Winograd, T. 1998. The PageRank citation ranking: Bringing order to the Web. Tech. rep. Stanford University.
• 38: Feng Qiu , Junghoo Cho, Automatic identification of user interest for personalized search, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135883]
• 39: Quintarelli, E. 2005. Folksonomies: Power to the people. ISKO Italy-UniMIB Meeting.
• 40: Rand, W. M. 1971. Objective criteria for the evaluation of clustering methods. J. Amer. Statis. Assoc. 66, 336, 846--850.
• 41: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 42: Sarwar, B. M., Karypis, G., Konstan, J., and Riedl, J. 2002. Recommender systems for large-scale e-commerce: Scalable neighborhood formation using clustering. In Proceedings of the 5th International Conference on Computer and Information Technology.
• 43: Singhal, A. and Salton, G. 1995. Automatic text browsing using vector space model. In Proceedings of the 5th Dual-Use Technologies and Applications Conference. 318--324.
• 44: Solomonoff, A., Mielke, A., Schmidt, M., and Gish, H. 1998. Clustering speakers by their voices. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. 757--760.
• 45: Z. Wu , R. Leahy, An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.11, p.1101-1113, November 1993 [doi>10.1109/34.244673]
• 46: Tsai, T.-M., Shih, C.-C., and Chou, S.-C. T. 2006. Personalized blog recommendation using the value, semantic, and social model. In Innovations in Information Technology. 1--5.
• 47: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Information browsers

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Prototyping; User-centered design; Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Design, Human Factors, Performance

Keywords:
Blog, connected subgraph, content information, link information, personalization, ranking, story, topic