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

社会网络分析中的数据挖掘综述张引∗(南京大学计算机科学与技术系,南京210093)DataMininginSocialNetworkAnalysis:ASurveyZHANGYin*(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:Theapplicationoftechniquesfromdataminingintosocialnetworkanalysisprovidesanewdirectionfortheresearchofdatamining.Differentfromthetraditionaltasksofdatamining,whichassumetheinstancesareindependent,instancesinsocialnetworkaredependent.Suchdependencecanbedescribedaslinks.Miningfromlinkscanprovideusmoreaccurateandricherinformationaboutthesocialnetwork.Thispaperbrieflyintroduces7commonlinkminingtasksbasedontheirtypes.Keywords:socialnetworkanalysis;datamining;linkmining摘要:将数据挖掘的方法应用于社会网络分析是数据挖掘研究的一个新的方向。与传统数据挖掘研究的对象不同，在社会网络分析中个体之间由于存在着相互的联系，故不满足独立的假设，个体之间这种相互的联系就是链接。对链接信息的挖掘，即链接挖掘，可以给我们提供关于这个社会网络更丰富更准确的信息。本文按照链接挖掘的种类简要介绍了其中7个主要的研究热点任务。关键词:社会网络分析;数据挖掘;链接挖掘中图法分类号:TP301文献标识码:A1引言传统的机器学习和数据挖掘任务处理的对象是单独的数据实例，这些数据实例往往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。例如要训练一个疾病诊断系统，它的任务是诊断一个被试者是否患有某种传染病。传统的学习算法用一个向量来表示一个被试者，同时假设两个被试者之间的患病情况是相互独立的，即知道一个确诊病人对于诊断其他被试者是否患病不能提供任何帮助。直观经验告诉我们这种假设是不合理的，一个人的亲戚、朋友患有此传染病，则他相对其他人有更大的可能性患病。在社会里，人与人不是简单的统计上独立的采样点，他们之间必然存在着联系和影响。忽视了这种联系会对这个诊断系统的性能带来很大的影响。为了解决这个问题，必须将数据实例之间的关系同时考虑进来，从而人们提出了社会网络的概念，试图用图结构来刻画这种社会结构。一个社会网络由很多节点（node）和连接这些节点的一种或多种特定的链接（link）所组成。节点往往表示了个人或团体，也即传统数据挖掘中的数据实例，链接则表示了他们之间存在的各种关系（relation），如朋友关系、亲属关系、贸易关系、性关系等。与传统的数据挖掘只关注数据实例不同，社会网络分析对链接同样关注。从数∗作者简介:张引（1985-），男，浙江舟山人，硕士研究生，主要研究领域为机器学习和计算机视觉2据挖掘角度，社会网络分析又称为链接挖掘（linkmining）[38]。通过对链接的挖掘我们可以获得关于实例更丰富（如某个实例在整个网络中的重要性）、更准确（如预测某个实例所属的类别）的信息。与此同时，很多时候链接本身也是我们所关心的信息，如在某些情况下，并不是所有的链接都被观测到，因而我们可能对预测实例之间的链接是否存在感兴趣。在其他领域，链接随着时间不断转变，那么我们的目标可能是基于当前的观察来预测在未来某个时刻某个链接是否存在。更深入地，由于考虑了数据之间的链接，社会网络的结构属性，如节点的度数（degree）、连通性（connectivity）在挖掘中也提供了重要信息，同时，更复杂的模式，如子图（subgraph）（可理解为社团或群体等）随之出现，如何获得关于这些模式的更复杂的信息也给链接挖掘提出了更大的挑战。由于链接挖掘包括了很广泛的任务，这篇综述只能介绍在这些任务中较为核心的研究热点。本文其他部分的结构如下：第二部分分析了链接挖掘中社会网络数据的表示形式及其存在的问题；第三部分根据挖掘任务侧重点的不同（节点、链接、图）将它们分成七种（参见表1）分别介绍；昀后总结全文。表1常见的链接挖掘任务及其分类基于链接的节点排序（Link-BasedObjectRanking）基于链接的节点分类（Link-BasedObjectClassification）节点相关任务节点聚类（ObjectClustering）链接相关任务链接预测（LinkPrediction）子图发现（SubgraphDiscovery）图分类（GraphClassification）图相关任务图的产生式模型（GenerativeModelsforGraphs）2链接挖掘中的数据表示为了做到有效的链接挖掘，首先要将社会网络形式化。图论中的图（graph）为形式化社会网络提供了直观的表示形式。Freeman提出了社会网络分析必须具备的四个特征[1]：1.社会网络分析更注重行动者(Actor)之间的联系，而不是行动者本身所具有的性质；2.关于行动者之间联系(tie)的数据必须通过系统化的方法收集；3.建立在图模型之上；4.使用数学和计算工具来从这些关系中获取有意义的信息。第三点明确告诉我们，图作为社会网络为基本的表示是合适的。社会网络就是由行动者（即图中的节点）和行动者之间的联系（即图中的链接）组成的，其中行动者(Actor)：社会实体，可以表示具体的个人，社团及其它集体社会单元。联系(Relationtie)：不同的社会实体通过联系连接在一起。在不同的网络中，其意义也不同。例如：一个人对另一个人的评价，物质资料在实体间的转移，实体间的行为互动，两者的合作关系等等。除了以上两种基本元素之外，更复杂的模式包括：二元组(Dyad)：由两个行动者及他们之间的关系组成，这是研究关系模式的基本单位；子图(Subgroup)：由网络中的一部分行动者和他们之间的关系组成，可以通过子图来研究社会网络中的一个小团体所具有的特征；图(Graph)：所有行动者及其之间的关系，分析社会网络的总体特征。然而这种直观的表示并不意味着链接挖掘中的数据表示的确很简单。为了说明这种表示存在的缺陷，我们可以考虑一个描述了行动者和他们所参与的事件的社会网络[2]。如果用表结构表示，这个社会网络可以很容易表示为三个表：行为者表、事件表和参与关系表。如果用图结构表示，一个自然地表示可以用二分图：一个集合包含行为者节点，一个集合包含事件节点。连接这两个集合中的点的边表示了行为者的参3与关系，即如果一个行为者参与了一个事件，则这个行为者节点和这个事件节点之间就存在一条边，反之则没有边。然而我们还可以采用其他的表示，从另一种视角看待这个社会网络。如我们可以以行为者为节点，两个行为者之间的边则表征了这两个行为者参与了同一个事件。这种表示使我们的分析能更加以行为者为中心。另一方面，如果我们把事件作为节点，两个事件之间的链接表征了有行为者参与了这两个事件，那么这种表示使我们的分析更加以事件为中心。对于存在多种节点和链接的社会网络，这样的表示形式会更多。尽管一般认为表示的选择不是链接挖掘的一部分，但它对挖掘中的统计推断有着非常重要的影响。所以为解决一个具体社会问题，合理地选择社会网络表示形式对于好的链接挖掘系统是非常关键的。在下面部分的链接挖掘的介绍中我们假设已经选取了合适的表示。3典型链接挖掘任务介绍3.1基于链接的节点排序基于链接的节点排序是社会网络分析中一个核心分析任务[3]，它的目的是通过分析利用图中的链接结构，根据某种衡量节点重要性的度量来对图中节点进行排序，这种可度量的重要性被称为中心度（centrality）。根据复杂程度的不同，它们可分为局部度量和全局度量。其中前者包括“度中心度”（degreecentrality）[4]，即个顶点的度数，后者包括“特征向量/能量中心度”（eigenvector/powercentrality）[5]，即通过谱方法（Spectralmethods）根据一个节点到其他重要节点的连接来刻画该节点的重要性。除了上述基于在静态图上用给定的度量进行全局排序的工作外，对相对于图中若干相关节点的局部节点排序[6]和在动态图上的节点排序[7]也同样引人注目。Jeh和Widom[6]提出了一种估计两个节点间相似程度的新的度量，这种度量基于这两个节点到他们所链接的相似节点的度数。在他们的文章中，这种相似度是通过随机游走来计算的。Sun等人[8]则在此基础上引入了图分块以提高算法的稳定性。在动态图上排序考虑了事件的时间信息，这种考虑是必要的，如电子邮件、电话或者文献发表情况。与静态图上的排序不同，动态排序的目标是追踪节点随着新事件发生的排序变化O'Madadhain等人[7]关于这个问题提出了一系列需要满足的算法性质，讨论了静态排序算法的局限性并引入了基于潜流（potentialflow）的满足上述要求的排序算法。3.2基于链接的节点分类传统机器学习中的分类问题是基于数据实例（节点）是独立同分布的假设，然而很多现实问题不满足这个假设。在基于链接的节点分类问题中，一个数据图G=(O;L)表示了节点集合O和他们之间的链接集合L，我们的任务是将O中的成员赋予某一类标签。基于链接的节点分类与传统分类问题的昀显著的不同在于节点的类别是彼此相关的。如何设计合理的分类算法能有效地利用这些相关信息是研究者所面临的挑战。Chakrabarti等人[9]昀早在Reuters新闻数据集上考虑了这个问题。Lafferty等人[10]提出了条件随机场(ConditionalRandomFields)的概念，扩展了传统昀大熵模型对于数据的结构必须是链式结构的限制。Lu和Getoor[11]通过对每个数据实例增加新的属性来扩展简单的机器学习分类器，目的是使其能处理基于链接的节点分类问题。增加的新属性度量了类标签在节点组成的马尔可夫毯（Markovblanket）中的分布。除了机器学习的研究者外，计算机视觉、自然语言处理的研究者由于各自的应用需要同样关注基于链接的节点分类问题。Chakrabarti等人[13]利用Rosenfeld等人[12]提出的放松标签（relaxationlabeling）概念实现了基于链接的节点分类中的推断算法。Lafferty等人[10]将条件随机场用于词性标注。3.3节点聚类节点聚类又称为群体检测（GroupDetection），它的目的是将有着共同的特征的节点聚类。首先假设图中的节点和链接都属于同一种类。在这种假定下，群体检测的技术可以分成聚合聚类和分裂聚类两种。社会网络分析中块建模（blockmodeling）的任务是将社会网络分割成个体的集合，这种集合称为位置（position），显示了在网络中相似链接的集合[4]。一种定义在链接集合和聚合聚类之间的相似度量被用来寻找位置。谱4图分割的方法（Spectralgraphpartitioningmethods）用确定为了使图达到指定数量群体而可以去掉的近似昀小链接集合来解决群体检测问题[14]。昀近的另外的群体检测方法利用了一种刻画边的连接的度量来确定连接群体的链接[15]。这种想法源于Freeman关于连接中心度（betweennesscentrality）的观点[4]。为了分割图，有较高的边连接度的链接不断地被从图中删去。与上述确定地群体指派的方法不同的，很多群体检测的方法是基于社会网络分析中的随机块建模（stochasticblockmodeling）。在随机块建模中，观测到的社会网络被假设为对依赖的随机块模型的一种实现[3]