Structural and temporal analysis of the blogosphere through community factorization

ABSTRACT

The blogosphere has unique structural and temporal properties since blogs are typically used as communication media among human individuals. In this paper, we propose a novel technique that captures the structure and temporal dynamics of blog communities. In our framework, a community is a set of blogs that communicate with each other triggered by some events (such as a news article). The community is represented by its structure and temporal dynamics: a community graph indicates how often one blog communicates with another, and a community intensity indicates the activity level of the community that varies over time. Our method, community factorization, extracts such communities from the blogosphere, where the communication among blogs is observed as a set of subgraphs (i.e., threads of discussion). This community extraction is formulated as a factorization problem in the framework of constrained optimization, in which the objective is to best explain the observed interactions in the blogosphere over time. We further provide a scalable algorithm for computing solutions to the constrained optimization problems. Extensive experimental studies on both synthetic and real blog data demonstrate that our technique is able to discover meaningful communities that are not detectable by traditional methods.

REFERENCES

• 1: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 2: Deepayan Chakrabarti , Ravi Kumar , Andrew Tomkins, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150467]
• 3: Yun Chi , Belle L. Tseng , Junichi Tatemura, Eigen-trend: trend analysis in the blogosphere based on singular value decompositions, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183628]
• 4: A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.
• 5: 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]
• 6: C. Ding, T. Li, and M. Jordan. Convex and semi-nonnegative matrix factorizations for clustering and low-dimension representation. Technical Report LBNL-60428, Lawrence Berkeley National Laboratory, 2006.
• 7: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 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: D. A. Harville. Matrix Algebra From a Statistician's Perspective. Springer, first edition, 2000.
• 11: T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer, first edition, 2003.
• 12: Hidehiko Ino , Mineichi Kudo , Atsuyoshi Nakamura, Partitioning of Web graphs by community topology, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060841]
• 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: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150476]
• 15: D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401, 1999.
• 16: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings 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: M. E. J. Newman. Modularity and community structure in networks. Proc. Natl. Acad. Sci., 2006.
• 19: Arun Qamra , Belle Tseng , Edward Y. Chang, Mining blog stories using community-based and temporal clustering, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183627]
• 20: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 21: Tanja Falkowski , Jorg Bartelheimer , Myra Spiliopoulou, Mining and Visualizing the Evolution of Subgroups in Social Networks, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.52-58, December 18-22, 2006 [doi>10.1109/WI.2006.118]
• 22: G. Wahba. Spline Models for Observational Data. Society for Industrial and Applied Mathematics, 1990.
• 23: Xuerui Wang , Andrew McCallum, Topics over time: a non-Markov continuous-time model of topical trends, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150450]
• 24: S. White and P. Smyth. A spectral clustering approach to finding communities in graph. In SDM, 2005.
• 25: Wei Xu , Yihong Gong, Document clustering by concept factorization, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009029]
• 26: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, 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.860485]

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

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
blog, blogosphere, community factorization, iterative search, non-negative matrix factorization, regularization