在Web 2.0的時代，部落格無庸置疑地已成為了一個重要的代表，而每個網際網路使用者可透過個人之部落格空間作為發表想法、見解、評論或是作品的平台，資訊的散播與分享也因此變得更為容易，相關的技術和概念亦造就了部落格圈內使用者社群的發展與演進。在本論文中，藉由觀察部落客之間社群關係之演變來進行資訊散播現象的研究，部落格間的社群網路係由部落客與其訂閱行為所組成，而由於資訊散播的現象，部落客們可透過互相訂閱的行為而漸漸拉近彼此間的距離；於是，我們提出了一種新的資料探勘型態，稱之為捷徑樣式，並發展了一對應的演算法以發掘這些樣式。從理論與實驗的結果顯示我們所提出之技術可適用於病毒式行銷與個人化推薦等多種應用。

Undoubtedly, blogs are a significant representative in the Web 2.0 age. Every user on the Internet is able to own his or her blog site as a platform to publish personal thoughts, ideas, comments or works. Information can thus be propagated and shared in a much easier way. Corresponding techniques and concepts have led to the development and evolution of user communities in blogospheres. In this work, the phenomenon of information diffusion is studied through the observation of evolving social relationships among bloggers. It is noted that a social network can be formed with bloggers and corresponding subscription relationships. Moreover, the subscription of a blogger to another blog site may reflect that the distance among relevant bloggers is shortened due to information diffusion. Consequently, we devise in this work a new data mining capability, i.e., the shortcut pattern, and a proper approach to identify such patterns. Theoretical and empirical studies have shown that the proposed scheme can be feasible in various applications, including viral marketing and personalized recommendation.

[1] E. Adar, L. Zhang, L. A. Adamic and R. M. Lukose, “Implicit Structure and the Dynamics of Blogspace,” Proceedings of the 13th International World Wide Web Conference, May 2004.
[2] E. Adar and L. A. Adamic, “Tracking Information Epidemics in Blogspace,” Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, Pages: 207-214, September 2005.
[3] L. A. Adamic and N. Glance, “The Political Blogosphere and the 2004 U.S. Election: Divided They Blog,” Proceedings of the 3rd International Workshop on Link Discovery, Pages: 36-43, 2005.
[4] P. Baldi, P. Frasconi, P. Smyth, “Modeling the Internet and the Web: Probabilistic Methods and Algorithms,” Wiley, ISBN: 0-470-84906-1, 2003.
[5] N. Bansal and N. Koudas, “BlogScope: Spatio-temporal Analysis of the Blogosphere,” Proceedings of the 16th International Conference on World Wide Web, Pages: 1269-1270, 2007.
[6] N. Bansal, A. Blum, and S. Chawla, “Correlation Clustering,” Proceedings of the 43rd Symposium on Foundations of Computer Science, Pages: 238-247, 2002.
[7] A.-L. Barabasi and R. Albert, “Emergence of Scaling in Random Networks,” Science Vol. 286, Pages: 509-512, October 1999.
[8] F. Bass, “A New Product Growth Model for Consumer Durables,” Management Science 50(12): 1825-1832, December 2004.
[9] S. Brin and L. Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine,” Computer Networks and ISDN Systems Vol. 30, Pages: 107-117, April 1998.
[10] J. Brown and P. Reinegen, “Social Ties and Word-of-Mouth Referral Behavior,” Journal of Consumer Research, 14(3): 350-362, 1987.
[11] D. Cai, Z. Shao, X. He, X. Yan and J. Han, “Mining Hidden Community in Heterogeneous Social Networks,” Proceedings of the 3rd International Workshop on Link discovery, Pages: 58-65, 2005.
[12] S. Chakrabarti, “Mining the Web,” Morgan Kaufman, 2002.
[13] A. Chin and M. Chignell, “A Social Hypertext Model for Finding Community in Blogs,” Proceedings of the 17th Conference on Hypertext and Hypermedia, Pages: 11-22, 2006.
[14] A. Chin and M. Chignell, “Finding Evidence of Community from Blogging Co-citations: A Social Network Analytic Approach,” Proceedings of 3rd IADIS International Conference Web Based Communities, Pages: 191-200, Feburary 2006.
[15] A. Clauset, M. E. J. Newman, C. Moore, “Finding Community Structure in Very Large Networks,” Physical Review E, 70(6):066111, 2004.
[16] D. J. Cook and L. B. Holder, “Graph-Based Data Mining,” IEEE Intelligent Systems, 15(2): 32-41, 2000.
[17] J. N. Cummings, B. Butler and R. Kraut, “The Quality of Online Social Relationships,” Communications of the ACM, 45(7): 103-108, 2002.
[18] K. Dasgupta, R. Singh, B. Viswanathan, D. Chakraborty, S. Mukherjea, A. A. Nanavati and A. Joshi, “Social Ties and Their Relevance to Churn in Mobile Telecom Networks,” Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, Pages: 668-677, 2008.
[19] P. Domingos, “Mining Social Networks for Viral Marketing,” IEEE Intelligent Systems, 20(1): 80-82, 2005.
[20] P. Domingos and M. Richardson, “Mining the Network Value of Customers,” Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages: 57-66, 2001.
[21] Y. Dourisboure, F. Geraci and M. Pellegrini, “Extraction and Classification of Dense Communities in the Web,” Proceedings of the 16th International Conference on World Wide Web, Pages: 461-470, 2007.
[22] S. Džeroski and N. Lavrac, “Relational Data Mining,” Springer, ISBN: 3540422897, 2001.
[23] L. C. Freeman, “Centrality in Social Networks: Conceptual Clarification,” Social Networks Vol. 1, No.3, Pages: 215-239, 1979.
[24] R. Feldman, “Link Analysis: Current State of The Art,” 2002.
[25] G. W. Flake, S. Lawrence, C. L. Giles and F. M. Coetzee, “Self-Organization and Identification of Web Communities,” Computer, 35(3): 66-71, 2002.
[26] T. Furukawa, M. Ishizuka, Y. Matsuo, I. Ohmukai and K. Uchiyama, “Analyzing Reading Behavior by Blog Mining,” Proceedings of the 22nd AAAI Conference on Artificial Intelligence, Pages: 1353-1358, 2007.
[27] S. Gao and C. Yao, “A Comprehensive Review on Blog Mining under a Cross-Disciplinary Framework,” Journal of Computational Information Systems, 3(4): 1725-1730, April 2007.
[28] L. Getoor and C. P. Diehl, “Link Mining: A Survey,” ACM SIGKDD Explorations Newsletter, 7(2): 3-12, 2005.
[29] D. Gibson, J. Kleinberg and P. Raghavan, “Inferring Web Communities from Link Topology,” Proceedings of the 9th ACM Conference on Hypertext and Hypermedia, 1998.
[30] M. Girvan and M. E. J. Newman, “Community Structure in Social and Biological Networks,” Proceedings of the National Academy of Sciences, 99(12): 7821-7826, June 2002.
[31] J. Goldenberg, B. Libai and E. Muller, “Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth,” Marketing Letters, 12(3): 211-223, 2001.
[32] J. Goldenberg, B. Libai and E. Muller, “Using Complex Systems Analysis to Advance Marketing Theory Development,” Academy of Marketing Science Review Vol. 2001, No. 9, 2001.
[33] M. Granovetter, “The Strength of Weak Ties,” American Journal of Sociology, 78(6): 1360-1380, 1973.
[34] D. Gruhl, R. Guha, D. Liben-Nowell and A. Tomkins, “Information Diffusion through Blogspace,” Proceedings of the 13th International Conference on World Wide Web, Pages: 491-501, 2004.
[35] A. C. Halavais, “Linking Weblog Neighborhoods: Between "Small Pieces" and "Winner-Take-All",” In Association of Internet Researchers Annual Conference: IR 5.0: Ubiquity, September 2004.
[36] S. C. Herring, I. Kouper, J. C. Paolillo, L. A. Scheidt, M. Tyworth and P. Welsch, “Conversations in the Blogosphere: An Analysis "From the Bottom-Up",” Proceedings of the 38th Hawaii International Conference on System Sciences, 2005.
[37] H. W. Hethcote, “The Mathematics of Infectious Diseases,” SIAM Review, 42(4): 599-653, 2000.
[38] R. Ichise, H. Takeda and T. Muraki, “Research Community Mining with Topic Identification,” Proceedings of the Conference on Information Visualization, Pages: 276-281, 2006.
[39] D. Jensen and H. Goldberg, “Artificial Intelligence and Link Analysis: Papers from the 1998 AAAI Fall Symposium,” AAAI Press, 1998.
[40] A. Joshi, T. Finin, A. Java, A. Kale and P. Kolari, “Web 2.0 Mining: Analyzing Social Media,” Proceedings of the NSF Symposium on Next Generation of Data Mining and Cyber-Enabled Discovery for Innovation, October 2007.
[41] D. Kempe, J. Kleinberg and É. Tardos, “Maximizing the Spread of Influence through a Social Network,” Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages: 137-146, 2003.
[42] M. Kitsuregawa, M. Toyoda and I. Pramudiono, “Web Community Mining and Weblog Mining: Commodity Cluster Based Execution,” Proceedings of the 13th Australasian Database Conference, Pages: 3-10, 2002.
[43] J. Kleinberg, “Authoritative Sources in a Hyperlinked Environment,” Journal of the ACM, 46(5): 604-632, 1999.
[44] R. Kumar, J. Novak, P. Raghaven and A. Tomkins, “On the Bursty Evolution of Blogspace,” Proceedings of the 12th International Conference on World Wide Web, Pages: 568-576, 2003.
[45] R. Kumar, J. Novak, P. Raghaven and A. Tomkins, “Structure and Evolution of Blogspace,” Communications of the ACM, 47(12): 35-39, 2004.
[46] R. Kumar, J. Novak, A. Tomkins, “Structure and Evolution of Online Social Networks,” Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages: 611-617, 2006.
[47] G. Lappas, “An Overview of Web Mining in Societal Benefit Areas,” Proceedings of the 9th IEEE International Conference on E-Commerce Technology and the 4th IEEE International Conference on Enterprise Computing, E-Commerce, and E-Services, Pages: 683-690, July 2007.
[48] J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance and M. Hurst, “Cascading Behavior in Large Blog Graphs,” SIAM International Conference on Data Mining, 2007.
[49] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and Natalie Glance, “Cost-Effective Outbreak Detection in Networks,” Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages: 420-429, 2007.
[50] X. Li and B. Liu, “Mining Community Structure of Named Entities from Free Text,” Proceedings of the 14th ACM International Conference on Information and Knowledge Management, Pages: 275-276, 2005.
[51] X. Li, B. Liu and P. S. Yu, “Mining Community Structure of Named Entities from Web Pages and Blogs,” Proceedings of the AAAI Spring 2006 Symposia on Computational Approaches to Analyzing Weblogs, March 2006.
[52] Y.-R. Lin, H. Sundaram, Y. Chi, J. Tatemura and B. L. Tseng, “Blog Community Discovery and Evolution Based on Mutual Awareness Expansion,” Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, Pages: 48-56, 2007.
[53] S.-D. Lin and H. Chalupsky, “Using Unsupervised Link Discovery Methods to Find Interesting Facts and Connections in a Bibliography Dataset,” ACM SIGKDD Explorations Newsletter, 5(2): 173-178, 2003.
[54] V. Mahajan, E. Muller and F. Bass, “New Product Diffusion Models in Marketing: A Review and Directions for Research,” Journal of Marketing, 54(1): 1-26, 1990.
[55] D. Mehta, “My Blog is My Social Software and My Social Network,” Conversations with Dina. Available: http://radio.weblogs.com/0121664/2004/01/27.html#a356, 2004.
[56] J. J. Merelo-Guervós, B. Prieto, F. Rateb and F. Tricas, “Mapping Weblog Communities,” Computer Networks, 2003.
[57] S. Milgram, “The Small World Problem,” Psychology Today Vol. 2, Pages: 60-67, 1967.
[58] M. Newman, “The Structure and Function of Complex Networks,” SIAM Review, 45(2): 167-256, 2003.
[59] L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web,” Technical Report, Stanford University, 1998.
[60] P. Pons and M. Latapy, “Computing Communities in Large Networks Using Random Walks,” Proceedings of the 20th International Symposium on Computer and Information Sciences, Pages: 284-293, 2005.
[61] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, “Defining and Identifying Communities in Networks,” Proceedings of the National Academy of Science, 101(9): 2658-2663, March 2004.
[62] M. Richardson and P. Domingos, “Mining Knowledge-Sharing Sites for Viral Marketing,” Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages: 61-70, 2002.
[63] W.-G. Teng and M.-C. Chou, “Mining Communities of Acquainted Mobile Users on Call Detail Records,” Proceedings of the 2007 ACM Symposium on Applied Computing, Pages: 957-958, 2007.
[64] B. Ulicny, K. Baclawski and A. Magnus, “New Metrics for Blog Mining,” Proceedings of SPIE Defense & Security Symposium, 2007.
[65] J. Walker, “Weblog, In Definition for the Routledge Encyclopedia of Narrative Theory Forthcoming from Routledge,” 2005.
[66] C. Wei, “Formation of Norms in a Blog Community,” In L.Gurak, S. Antonijevic, L. Johnson, C. Ratliff, & J. Reyman (Eds.), Into the Blogosphere; Rhetoric, Community and Culture of Weblogs, University of Minnesota, 2004.
[67] Wikipedia, http://en.wikipedia.org/wiki/Main_Page.
[68] D. Winer, “What Makes a Weblog a Weblog? Weblogs at Harvard Law [On-line],” Available: http://blogs.law.harvard.edu/whatMakesAWeblogAWeblog, 2003.
[69] Y.-H. Yang, T.-J. Zhao, H. Yu and D.-Q. Zheng, “A Survey of Research on Blog,” Journal of Software, 19(4): 902-914, April 2008.
[70] H. P. Young, “The Diffusion of Innovations in Social Networks,” Santa Fe Institute Working Paper, April 2002.