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

《社会网络分析中的数据挖掘综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、社会网络分析中的数据挖掘综述∗张引(南京大学计算机科学与技术系,南京210093)DataMininginSocialNetworkAnalysis:ASurvey*ZHANGYin(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:Theapplicationoftechniquesfromdataminingintosocialnetworkanalysisprovidesane

2、wdirectionfortheresearchofdatamining.Differentfromthetraditionaltasksofdatamining,whichassumetheinstancesareindependent,instancesinsocialnetworkaredependent.Suchdependencecanbedescribedaslinks.Miningfromlinkscanprovideusmoreaccurateandricherinformationabou

3、tthesocialnetwork.Thispaperbrieflyintroduces7commonlinkminingtasksbasedontheirtypes.Keywords:socialnetworkanalysis;datamining;linkmining摘要:将数据挖掘的方法应用于社会网络分析是数据挖掘研究的一个新的方向。与传统数据挖掘研究的对象不同，在社会网络分析中个体之间由于存在着相互的联系，故不满足独立的假设，个体之间这种相互的联系就是链接。对链接信息的挖掘，即链接挖掘，可以给我们提

4、供关于这个社会网络更丰富更准确的信息。本文按照链接挖掘的种类简要介绍了其中7个主要的研究热点任务。关键词:社会网络分析;数据挖掘;链接挖掘中图法分类号:TP301文献标识码:A1引言传统的机器学习和数据挖掘任务处理的对象是单独的数据实例，这些数据实例往往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。例如要训练一个疾病诊断系统，它的任务是诊断一个被试者是否患有某种传染病。传统的学习算法用一个向量来表示一个被试者，同时假设两个被试者之间的患病情况是相互独立的，即知道一个确诊病人对

5、于诊断其他被试者是否患病不能提供任何帮助。直观经验告诉我们这种假设是不合理的，一个人的亲戚、朋友患有此传染病，则他相对其他人有更大的可能性患病。在社会里，人与人不是简单的统计上独立的采样点，他们之间必然存在着联系和影响。忽视了这种联系会对这个诊断系统的性能带来很大的影响。为了解决这个问题，必须将数据实例之间的关系同时考虑进来，从而人们提出了社会网络的概念，试图用图结构来刻画这种社会结构。一个社会网络由很多节点（node）和连接这些节点的一种或多种特定的链接（link）所组成。节点往往表示了个人或团体，也即传

6、统数据挖掘中的数据实例，链接则表示了他们之间存在的各种关系（relation），如朋友关系、亲属关系、贸易关系、性关系等。与传统的数据挖掘只关注数据实例不同，社会网络分析对链接同样关注。从数∗作者简介:张引（1985-），男，浙江舟山人，硕士研究生，主要研究领域为机器学习和计算机视觉2据挖掘角度，社会网络分析又称为链接挖掘（linkmining）[38]。通过对链接的挖掘我们可以获得关于实例更丰富（如某个实例在整个网络中的重要性）、更准确（如预测某个实例所属的类别）的信息。与此同时，很多时候链接本身也是我们

7、所关心的信息，如在某些情况下，并不是所有的链接都被观测到，因而我们可能对预测实例之间的链接是否存在感兴趣。在其他领域，链接随着时间不断转变，那么我们的目标可能是基于当前的观察来预测在未来某个时刻某个链接是否存在。更深入地，由于考虑了数据之间的链接，社会网络的结构属性，如节点的度数（degree）、连通性（connectivity）在挖掘中也提供了重要信息，同时，更复杂的模式，如子图（subgraph）（可理解为社团或群体等）随之出现，如何获得关于这些模式的更复杂的信息也给链接挖掘提出了更大的挑战。由于链接挖

8、掘包括了很广泛的任务，这篇综述只能介绍在这些任务中较为核心的研究热点。本文其他部分的结构如下：第二部分分析了链接挖掘中社会网络数据的表示形式及其存在的问题；第三部分根据挖掘任务侧重点的不同（节点、链接、图）将它们分成七种（参见表1）分别介绍；最后总结全文。表1常见的链接挖掘任务及其分类基于链接的节点排序（Link-BasedObjectRanking）节点相关任务基于链接的节点分类（Link-BasedObjec