社会网络分析中的数据挖掘综述.pdfVIP

社会网络分析中的数据挖掘综述 张引∗ (南京大学 计算机科学与技术系, 南京 210093) Data Mining in Social Network Analysis: A Survey * ZHANG Yin (Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China) Abstract : The application of techniques from data mining into social network analysis provides a new direction for the research of data mining. Different from the traditional tasks of data mining, which assume the instances are independent, instances in social network are dependent. Such dependence can be described as links. Mining from links can provide us more accurate and richer information about the social network. This paper briefly introduces 7 common link mining tasks based on their types. Key words: social network analysis; data mining; link mining 摘 要: 将数据挖掘的方法应用于社会网络分析是数据挖掘研究的一个新的方向。与传统数据挖掘研究的对 象不同，在社会网络分析中个体之间由于存在着相互的联系，故不满足独立的假设，个体之间这种相互的联 系就是链接。对链接信息的挖掘，即链接挖掘，可以给我们提供关于这个社会网络更丰富更准确的信息。本 文按照链接挖掘的种类简要介绍了其中7 个主要的研究热点任务。 关键词: 社会网络分析; 数据挖掘; 链接挖掘 中图法分类号: TP301 文献标识码: A 1 引言 传统的机器学习和数据挖掘任务处理的对象是单独的数据实例，这些数据实例往往可以用一个包含多 个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。例如要训练一个疾病诊断系统，它 的任务是诊断一个被试者是否患有某种传染病。传统的学习算法用一个向量来表示一个被试者，同时假设 两个被试者之间的患病情况是相互独立的，即知道一个确诊病人对于诊断其他被试者是否患病不能提供任 何帮助。直观经验告诉我们这种假设是不合理的，一个人的亲戚、朋友患有此传染病，则他相对其他人有 更大的可能性患病。在社会里，人与人不是简单的统计上独立的采样点，他们之间必然存在着联系和影响。 忽视了这种联系会对这个诊断系统的性能带来很大的影响。为了解决这个问题，必须将数据实例之间的关 系同时考虑进来，从而人们提出了社会网络的概念，试图用图结构来刻画这种社会结构。一个社会网络由 很多节点（node ）和连接这些节点的一种或多种特定的链接（link ）所组成。节点往往表示了个人或团体， 也即传统数据挖掘中的数据实例，链接则表示了他们之间存在的各种关系（relation ），如朋友关系、亲属关 系、贸易关系、性关系等。与传统的数据挖掘只关注数据实例不同，社会网络分析对链接同样关注。从数 ∗ 作者简介: 张引（1985-），男，浙江舟山人，硕士研究生，主要研究领域为机器学习和计算机视觉 2 据挖掘角度，社会网络分析又称为链接挖掘（link mining ）[38]。通过对链接的挖掘我们可以获得关于实例 更丰富（如某个实例在整个网络中的重要性）、更准确（如预测某个实例所属的类别）的信息。与此同时， 很多时候链接本身也是我们所关心的信息，如在某些情况下，并不是所有的链接都被观测到，因而我们可 能对预测实例之间的链接是否存在感兴趣。在其他领域，链接随着时间不断转变，那么我们的目标可能是 基于当前的观察来预测在未来某个时刻某个链接是否存在。更深入地，由于考