Eigen-trend: trend analysis in the blogosphere based on singular value decompositions

ABSTRACT

The blogosphere - the totality of blog-related Web sites - has become a great source of trend analysis in areas such as product survey, customer relationship, and marketing. Existing approaches are based on simple counts, such as the number of entries or the number of links. In this paper, we introduce a novel concept, coined eigen-trend, to represent the temporal trend in a group of blogs with common interests and propose two new techniques for extracting eigen-trends in blogs. First, we propose a trend analysis technique based on the singular value decomposition. Extracted eigen-trends provide new insights into multiple trends on the same keyword. Second, we propose another trend analysis technique based on a higher-order singular value decomposition. This analyzes the blogosphere as a dynamic graph structure and extracts eigen-trends that reflect the structural changes of the blogosphere over time. Experimental studies based on synthetic data sets and a real blog data set show that our new techniques can reveal a lot of interesting trend information and insights in the blogosphere that are not obtainable from traditional count-based methods.

REFERENCES

• 1: Junghoo Cho , Hector Garcia-Molina, Effective page refresh policies for Web crawlers, ACM Transactions on Database Systems (TODS), v.28 n.4, p.390-426, December 2003 [doi>10.1145/958942.958945]
• 2: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, A Multilinear Singular Value Decomposition, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1253-1278, March – May 2000 [doi>10.1137/S0895479896305696]
• 3: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, On the Best Rank-1 and Rank-(R₁,R₂,. . .,R_N) Approximation of Higher-Order Tensors, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1324-1342, March – May 2000 [doi>10.1137/S0895479898346995]
• 4: S. Deerwester, S. Dumais, T. Landauer, G. Furnas, and R. Harshman. Indexing by latent semantic analysis. J. American Soc. Info. Sci., 41, 1990.
• 5: F. Douglis, A. Feldmann, and B. Krishnamurthy. Rate of change and other metrics: a live study of the World Wide Web. In Proc. of the USENIX Symposium on Internet Technologies and Systems, 1997.
• 6: Dennis Fetterly , Mark Manasse , Marc Najork , Janet Wiener, A large-scale study of the evolution of web pages, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775246]
• 7: N. S. Glance, M. Hurst, and T. Tomokiyo. BlogPulse: Automated trend discovery for weblogs. In WWW 2004 Workshop on the Weblogging Ecosystem: Aggregation, Analysis and Dynamics, 2004.
• 8: G. Golub and C. V. Loan. Matrix Computations. Johns Hopkins University Press, third edition, 1996.
• 9: Daniel Gruhl , R. Guha , David Liben-Nowell , Andrew Tomkins, Information diffusion through blogspace, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988739]
• 10: I. Jolliffe. Principal Component Analysis. Springer, second edition, 2002.
• 11: 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]
• 12: Tamara G. Kolda , Brett W. Bader , Joseph P. Kenny, Higher-Order Web Link Analysis Using Multilinear Algebra, Proceedings of the Fifth IEEE International Conference on Data Mining, p.242-249, November 27-30, 2005 [doi>10.1109/ICDM.2005.77]
• 13: 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]
• 14: D. Lai. Temporal analysis of the human development indicators: Principal component approach. Social Indicators Research, 51, 2000.
• 15: Anukool Lakhina , Konstantina Papagiannaki , Mark Crovella , Christophe Diot , Eric D. Kolaczyk , Nina Taft, Structural analysis of network traffic flows, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 16: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 17: Qiaozhu Mei , Chao Liu , Hang Su , ChengXiang Zhai, A probabilistic approach to spatiotemporal theme pattern mining on weblogs, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135857]
• 18: B. H. Murray. Sizing the internet. In White paper, Cyveillance, Inc., 2000.
• 19: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 20: X. Song, B. L. Tseng, C.-Y. Lin, and M.-T. Sun. ExpertiseNet: Relational and evolutionary expert modeling. In Int. Conf. on User Modeling, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Experimentation, Measurement

Keywords:
blog, blogosphere, higher-order singular value decomposition, singular value ecomposition, trend analysis