Mining Conversing Groups of Chatters in IRC Sooial Networks

论文摘要

在聊天室环境下进行互联网对话已经成为在虚拟社区中进行通信的一种普遍形式。然而,聊天室的非正式对话与正规的静态集会在本质上有许多不同的属性（如噪声、简洁的表达语句、缩写字、易被利用的、多变和动态的讨论话题等）。互联网中继聊天（Internet Relay Chat,IRC）网络文档的这种特性使得它的聊天数据不太适合使用现有的文本挖掘方法进行分析。例如,常被用来发现聊天者群组的挖掘方法如搜索聚类和降维方法通常是基于这样一个假设：搜索集合是一个用适当的语言书写的静态的离散文档集,而这种文档的属性在IRC的聊天数据中是缺乏的。但是,IRC聊天室中的交流和沟通中包含了关于聊天者群组的有价值的信息,这些聊天者群组是正式的或自主形成的,他们进行交流的目的也是多样化的。同时,人类的沟通巾通常包含一种用来强调结果的隐喻效果。因此,进行IRC聊天数据的搜索和分析是一个很有意义的工作。本文的工作主要关注如何设计一种易于使用的方法来增强针对IRC聊天数据的搜索算法的实现。在本文中,我们设计了一个完全自动化的客户端-服务器-客户端（client-server-client,CSC）系统,用于数据收集和对三个被观测的聊天室（政策、食品安全和趣味聊天）的社交网络图（Social Network Graphs）进行推测。这个CSC系统由如下三个组件组成：首先,CSC系统包含了一个主IRC客户端,这个客户端为聊天者进行私下或公开的基于文本的会议交流提供了聊天室环境。IRC客户端本身可以对聊天者个人和聊天室行为的数据进行收集,这些数据可以用于静态的分析。第二,CSC系统包含一个名为pieSpy的代理客户端（bot-client）组件,它连接到主IRC客户端的服务器上,其功能是通过服务器从CSC系统中提取信息,使用一些基本的启发式算法来推测出三个聊天室的社交网络图。第三,系统中包含一个或多个服务器,它形成了整个CSC系统的中心,因为它是IRC协议中唯一的可以通过提供一个或多个节点来将其他组件链接到一起的组件,而客户端或服务器可以通过连接到这些节点来与其他客户端或服务器进行对话。系统由一个基于奇异值分解（Singular Value Decomposition）的计算算法支持,该算法主要用于搜索聊天室中的聊天者群组和隐藏的通信模式。但是,这个基于奇异值分解的算法的计算复杂度达到了O（m3）,代价过高,这样,在有效的计算时问内无法进行太大的矩阵运算。本文提出了一种基于快速奇异值分解的算法,它已被证明比基于奇异值分解的算法更简单、清晰,且具有更好的计算性能和更快的运行时间。而该算法仅要求在采样阶段做更多的工作。在我们的实验中,性能评估被用来对PieSpy程序、基于奇异值分解的算法以及本文设计的快速奇异值分解算法在真实IRC数据上进行有效性的验证。通过这个验证方法,可以得出如下结论：（i）不同聊天室的静态属性有显著变化,因此对聊天室进行数据分析是可能的。（ii）所实现的两个分析工具（基于奇异值分解和快速奇异值分解的算法）都是基于采用更过数学运算过程的降维方法来搜索在IRC社交网络中被观测的聊天室中的普通群组和隐藏群组（如由边相连的节点组）。在这个算法评估的过程中,本文利用收集的数据手工制作了一个图形工具,利用它生成的点和边与各各算法生成的点和边进行比较。比较的结果再通过一个数学的计算来确定每个算法丢失的点和边的百分比。有趣的是,本文的算法,快速奇异值分解算法被证明比基于奇异值分解的算法具有更高的性能,它能生成更低的点和边丢失率。

论文目录

• DEDICATION
• Abstract
• 摘要
• TABLE OF CONTENTS
• Acknowledgement
• LIST OF FIGURES
• LIST OF TABLES
• CHAPTER ONE:INTRODUCTION
• 1.1 Background of the study
• 1.2 Statement of the problem
• 1.3 The aim and objectives of the study
• 1.4 Organization of the thesis
• 1.5 Summary
• CHAPTER TWO:LITERATURE REVIEW OF RELATED WORKS
• 2.1 Chatroom environment for conversations
• 2.2 Efficient search tools for IRC data analysis
• 2.3 Summary
• CHAPTER THREE:AN OVERVIEW OF IRC PROTOCOL
• 3.1 An introduction to the IRC protocol
• 3.2 Basic components of the IRC protocol
• 3.2.1 Servers
• 3.2.1.1 Modern IRC server
• 3.2.2 Clients
• 3.2.3 IRC architecture
• 3.2.4 IRC protocol services
• 3.2.5 Channel hosting and management
• 3.2.6 IRC concepts
• 3.3 User control measures in IRC protocol
• 3.3.1 Authentication in IRC
• 3.3.2 Multiple nicknames
• 3.3.3 Time-stamping versus nick/channel delay protocol
• 3.4 Current problems of IRC protocol
• 3.5 Summary
• CHAPTER FOUR: METHODOLOGY FOR DATA ACQUISITION
• 4.1 Client-Server-Client model
• 4.1.1 Generating data matrices for SVD-based algorithm
• 4.1.2 Data structure
• 4.1.2.1 Heuristics
• 4.1.2.2 Data scrubbing
• 4.2 Summary
• CHAPTER FIVE:TOOLS FOR DISCOVERING OF GROUPS OF CHATTERS BASED ON SVD-BASED ALGORITHM
• 5.1 An introduction of SVD tool
• 5.2 Definition of SVD tool
• 5.3 Implementation of SVD algorithm to discover groups of chatters in IRC corpus
• 5.4 Summary
• CHAPTER SIX:EXPERIMENTAL RESULTS
• 6.1 Statistical analysis of chatrooms
• 6.2 Social networks of the chatrooms
• 6.3 Performance evaluation of SVD-based algorithm
• 6.4 Performance evaluation of the designed SVD-Fast algorithm
• 6.5 Summary
• CONCLUSION
• REFERENCES