社会网络发现综述 (肖韬,南京大学计算机系,数据挖掘大作业)_图文

1、社会网络发现综述肖韬1(南京大学计算机科学与技术系,南京210093Comprehensive Introduction to Social Network DiscoveryXiaoTao1(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, ChinaAbstract: As a subdomain of data mining discipline, social network discovery concentrates on finding relationship a

2、mong objects. In contrast to traditional data mining tasks, data in social network discovery tasks do not satisfy the assumption that they are independent, identically distributed. This paper introduces the concept of social network discovery, the feature of concerned data, basic methods and applica

3、tions as well as the concept of link mining and its theoretical background and classical tasks.Keywords: data mining; social network discovery; graph; relationship; link mining摘 要: 社会网络发现是数据挖掘学科的一个子领域,致力于从数据中找出对象与对象之间的关系。与传统的数据挖掘任务不同,社会网络发现任务中的数据不满足独立同分布的假设。本文介绍了社会网络发现的概念、数据特征、基本方法与实际应用,并对链接挖掘的概念、理论

4、背景及几种常见的任务做了简要阐述。关键词: 数据挖掘;社会网络发现;图;关系;链接挖掘1 数据挖掘学科概述在计算机被发明之前的时代,人类存储信息的主要载体是纸张。虽然全世界的图书(以及报纸等各种类型的纸张很多,但是以今天的眼光来看,当时的信息量并不算多。自从计算机被发明以来,记录信息的方式发生了根本性的变化:计算机所独有的数据存储、输入、生成、交换功能,使得人类可以以前所未有的低成本和高速度来存储、生成、使用和传递大量的信息,几乎可以说人类进入了信息时代。但是真正带来信息爆炸效应的是Internet的普及。随着目前Internet的无孔不入,在互联网上每天都有海量的信息在生成和传递,并且这些海

5、量数据每天还在以越来越快的速度增长,这些数据在目前的技术条件下已经不可能全部地进行实时处理(当然对于我们所需的部分数据是可以进行有效分析的,并且将来处理的难度和强度将越来越大,以至于人们处理数据的速度将跟不上数据产生的速度,这就是人们惊呼的“信息爆炸”时代的到来。面对如此海量的数据,人们发现已有的数据处理和提炼的工具是多么地匮乏,我们迫切需要新的、更加有效的工具来从这海量的数据中“挖掘”出对我们有价值的信息,这就是数据挖掘这门学科最根本的目的所在。按照J. W. Han和Micheline Kamber的定义,数据挖掘是从巨量数据中发现有效的、新颖的、潜在有用的并且最终可理解的模式的非平凡过程

6、3。经过几十年的研究和发展,数据挖掘学科已经在社会经济的各个方面得到了普遍的应用,其从海量数据中挖掘出极具价值的信息的例子也是数不胜数,例如沃尔玛超市中“啤酒和尿布”的例子就是一个典型:经过对货物的销售记录数据进行分析,沃尔玛发现很多购买尿布的人同时也购买了啤酒,故而沃尔玛有意将尿布与啤酒的货架放在一起,大大提高了这二者的销量。*作者简介:肖韬(生于1985年,男,江苏省南京市人,硕士研究生在读,主要研究领域为计算机体系结构与并行计算。经过数十年的研究与发展,数据挖掘技术已经在很多的方面取得了成功,同时,数据挖掘技术也呈现出更加细化和专业化的发展趋势:向着各个子领域深入地发展。例如,在多媒体领

7、域的数据挖掘、在医疗领域的数据挖掘以及在消费市场领域的数据挖掘等等。本文将对数据挖掘技术在社会网络发现这一子领域展开介绍与论述。2 社会网络发现的概念与研究意义2.1 社会网络与社会网络分析人类是群居动物,从远古时代起,人类就在一起共同耕种、狩猎、劳作,从而形成了社会。社会发展到现在,每一个人都不可避免地与其他一些人发生着联系,如工作、学习、交友等。这样,社会中各个成员中就形成了某种稳定的关系,进而构成了社会网络,就如Mickenberg和Dugan在1995年所说的那样,“We all connect, like a net we cannot see”6。维基百科对社会网络给出了如下的定义

8、:社会网络是一个社会结构,该结构由被称为节点的个体(或者组织构成,各个节点之间由一种或者多种特定类型的相互依赖性(如友谊、亲属关系、共同爱好、金融交易、两性关系、信仰、知识或者威望连接起来1。在20世纪30年代,Jacob L. Moreno和哈佛大学的一组研究人员分别提出社会网络模型这个概念,想借此来研究和分析社会学中的一些现象和问题。而社会网络分析,则是指对那些连接社会网络中的个体的结构模型进行研究。在大部分情况下,社会网络分析致力于找出两种模型:(1能够揭示属于同一个特定群体的个体的模型;(2能够揭示那些处在同一社会地位或者扮演相同社会角色的个体的模型5。2.2 对社会网络发现这一领域进

9、行研究和分析的意义现代社会中的人不可能是独居的人,而必定是时刻都在与他人发生着各种各样的联系,他们几乎所有的活动也都是建立在这种种联系的基础之上的。通过研究社会网络中人们之间的联系,我们可以从中发掘出大量的极具价值的信息。例如,可以寻找出具有某些相同特征的人,如共同的爱好、相似的工作等等;通过对已知患者群的社会网络关系进行发掘,可以预测出这些患者群所患疾病的传播趋势;在已知对某项业务有需求的初始人群时,通过社会网络发现与分析找出与该初始人群有密切联系或者共同活动特征的其他关键人群,可以有效地对该关键人群展开业务推广,从而产生口碑效应,提高业务推广的成功率与效率。可见,对社会网络发现进行研究和分

10、析在当今的信息化社会中具有重大的现实应用意义。3 社会网络发现的研究历史及进展美籍奥地利人Jacob L. Moreno是最早提出社会网络分析这一学科概念并对其开展研究工作的学者之一4。他认为,这一学科是通过对连接各个对象的网络的分析,对个体在某个群体或者社区中的角色进行定量的评价。而社会网络发现,则是指利用已有的数据来发现对象与对象之间的关系,这样这些对象以及发现的关系则构成了社会网络。可见,社会网络分析与社会网络发现是数据挖掘中两个相互有关联的子领域:社会网络分析技术可以用于发现潜在的社会网络,而社会网络发现则是社会网络分析预备步骤,亦可以看作是社会网络分析的目标之一。目前,社会网络发现在

11、现实生活中已经取得了一定的应用。很多在线购物网站通过对消费者的浏览及消费记录进行分析,确定该消费者与其他哪些消费者具有相似的购物倾向,并给出该消费者可能感兴趣的其它商品的推荐。例如,在当当网上的搜索框内输入关键字“数据挖掘”,该网站不仅会列出书名叫数据挖掘的书籍(图1,还会根据其他浏览过该书的用户的购买及浏览记录,列出购买过和浏览过该书的其他读着所购买和浏览的其他书籍(图2和图3。更有意义的是,通过对读者的购买和浏览记录这些数据进行分析,该网站能够确定出一个社会网络,该网络由与该购书者具备相似购书需求或者兴趣的个体组成。由此,网站进一步地预测了浏览过该书的其他个体还可能会购买哪些其他书籍(图4

12、,以及与该购书者具有相似兴趣的顾客关注的其他商品(图5。 图1 图2 图3 图4 图54 社会网络中的数据、特征及表示方式4.1 社会网络中的数据的特点在传统的数据挖掘任务中,数据是孤立的记录,每一条记录可以由一个属性向量表示,向量的每一维对应着一种条件属性的取值,而这些属性向量之间都是相互独立的2。显然,社会网络中的数据不满足以上这些假设:之所以把各个节点组成社会网络,就是为了发现与研究这些个体之间的关系,如果一开始就认为这些个体(及其数据是相互独立的,那么这项数据挖掘任务本身失去了意义。而在现实生活中,这也是显然的。举例来说,在研究甲型H1N1流感病毒传染趋势的模型中,如果仅仅考虑个体的自

13、身免疫系统状况,只能得到一些简单的分类依据。如果两个人的免疫状况差不多,则很难进一步地预测哪一个会感染甲型H1N1流感病毒。而如果将两个人的生活圈子也考虑进来进行分析,则可以进行更加精确的预测。因为如果一个人的交际圈子中有人已经感染了甲型H1N1流感病毒,那么这个人也感染甲型H1N1流感病毒的概率显然要更高。可见,在社会网络中数据中最有价值的部分就是其中蕴藏着的个体之间的联系信息,在社会网络中进行数据挖掘,个体之间已经不再是独立的了。所以如果想利用依赖性(dependencies来改善预测结果的话,就必须充分地考虑个体之间的关系,以建立更加准确的模型。4.2 社会网络中数据的表示方式任何数据都

14、有其表示方式,而社会网络分析需要强有力的数学工具作支撑,如概率论、数理统计和图论等,这样,数据以怎样的形式来表示就显得尤为重要。合理的数据表示方式,可以使得对社会网络的分析更加地方便和高效,也有利于分析结果的可视化。Freeman在文6中提出,现代的社会网络分析必须具备以下四个特征:1社会网络分析是以基于社会活动者(social actor之间关系的结构直觉(structure intuition为动机的;2基于系统的实验数据(systematic empirical data;3充分利用图的表示形式(graphic imagery;4依赖于数学及/或计算模型的使用。这四点对现代的社会网络分析

15、任务作了特征描述,其中的第三点指出了图是社会网络中的数据的最基本表示方式。而在大量的研究项目里,也的确是把图论作为最基本的分析工具,这一点非常易于理解:既然社会网络由被称为节点的个体(或者组织构成,且各个节点之间由一种或者多种特定类型的相互依赖关系连接起来,那么很自然地想到使用图论中的图这一概念来进行数据的表示,即将各个个体看做图中的顶点,而在两个个体之间存在的联系则看做是两顶点之间的边。在文6中,Freeman还提出了在社会网络发现及分析中的几个处于中心地位的概念,并对其做了定义:1活动者(Actor:社会网络中的实体,可以是单个个体或者是团体、社会单元,如群体中的人、公司中的部门、城市中的

16、公共服务机构或者世界范围内的国家。2联系(Relational Tie:社会网络中的各个活动者之间通过联系连接在一起,其范围和种类十分地宽泛,但是最显著的特征是其能够在一对活动者之间建立链接。3二元组(Dyad:由一对活动者及他们之间可能的联系构成。二元组分析注重一对活动者之间联系的属性,如联系是否是双向作用的(reciprocated及某几种特定类型的联系是否会同时存在。二元组常常是对社会网络进行统计分析的基本单元。4三元组(Triad:由三个活动者及他们之间可能的联系构成,为许多重要的社会网络方法及模型所关注。平衡理论(Balance Theory提出和激发了许多三元组分析相关的问题,其中

17、特别有意义的是三元组是否是可传递的(transitive及平衡的(balanced。5子群(Subgroup:由所有活动者的任意大小的子集(subset及他们之间的联系构成。使用特定的标准来定位和研究子图已经成为社会网络分析中重要的关注点。6群体(Group:从社会学家的角度出发有很宽泛的定义,在社会网络领域中定义为一群活动者及其中的联系。5 社会网络发现任务及其理论基础在J. W. Han的书中,数据挖掘任务通常可以被划分为两大类:描述型(descriptive任务和预测型(predictive任务。描述型数据挖掘任务侧重于对已有的样本数据的整体特征进行刻画和归纳,而预测型数据挖掘任务则侧重

18、于根据从已有数据样本中得到的已知规律,预测在未来或者新的情况下将会产生哪些变化。作为数据挖掘的子领域,社会网络发现兼具描述型和预测型数据挖掘任务的特征,即侧重于从已有的样本数据中发现潜在的关系网络。经过这几十年的研究,已经有了若干理论与方法来进行关于社会网络的数据挖掘任务,如常见的有基于相似度度量的方法、基于统计的方法、基于ILP的方法、基于频繁模式挖掘的方法、基于图性质的方法等9。本节将介绍由L. Getoor和C. P. Diehl在其一篇论文中提出的链接挖掘的概念及其相关理论基础8。5.1 链接挖掘理论在社会网络中,个体之间的关系被看作势一种特定的链接(link,这些链接通常展现出若干种

19、能够代表数据实例属性(如重要性、排名和范畴等的模型。当然,在很多情况下,并不是所有的链接都是显而易见的,所以我们也许对预测两个个体之间是否存在链接感兴趣。在一些其他领域,个体之间的链接可能会随着时间而发生变化,这时我们的目标可能就是预测某个已经观察到的链接在将来是否依然会存在。将链接考虑进来,会产生一些更加复杂的模型,这在我们聚焦于发现子结构(substructure时会产生一些更大的挑战,如群组和共同子图(common subgraphs等。相比较于主要关注数据实例的传统数据挖掘任务,链接挖掘更加注重对链接(关系的挖掘与分析,且在很多时候是整个挖掘任务的最重要目标。5.2 链接挖掘的研究和发

20、展历史链接挖掘(link mining是一个新兴的研究领域,处于链接分析(link analysis、超文本和页面挖掘(hypertext and web mining、关系学习(relational learning、归纳逻辑编程(inductive logic programming和图挖掘(graph mining等研究工作的交叉地带。近年来,已经有一系列的研讨会对链接挖掘相关的课题展开了讨论,其中最早的是国际人工智能协会(AAAI在1998年召开的人工智能及链接分析秋季研讨会,其他的还包括在关于统计关系学习(Statistical Relational Learning、多关系数据挖掘

21、(Multi-Relational Data Mining、LinkKDD、链接分析(Link Analysis、反恐及安全(Counter-Terrorism and Security以及图、树、序列挖掘(Mining Graphs, Trees and Sequences等方面展开的研讨会8。5.3 几种常见的链接挖掘任务链接挖掘所涉及到的数据挖掘技术在建立关于被链接的个体的描述型或者预测型模型时会重点考虑那些链接,文8提出了五种典型的链接挖掘任务,下面将做简单介绍。5.3.1 基于链接的对象排序作为链接分析领域的一个重要部分,基于链接的对象排序(Link-based Object Ran

22、k,LBR是最广为人知的链接挖掘任务,其目标是探寻图的链接结构以便对图内的对象进行排序或者确定优先级。目前已知的进行LBR任务的方法有PageRank、HITS以及它们的变种等,其中Google公司将PageRank方法应用在搜索引擎的网页排名中并取得了巨大的成功。5.3.2 基于链接的对象分类传统的机器学习注重对由相同结构的对象所构成的数据进行分类,而这些对象通常被假定为是独立同分布(Independent, Identically Distributed, IID的,但是现实世界中的许多数据集是不满足这样的假设的。在基于链接的对象分类(Link-based Object Classific

23、ation,LBC中,一个数据图G = (O, L由一个对象集合O和一个链接集合L组成,O中的各个对象之间通过L彼此互联。此时的任务是给O中的对象赋予属于某一个有穷集合的分类标签。LBC不同于其他传统的分类方法的特征之处在于,在许多情况下数据的分类也是彼此相关的。5.3.3 群体检测群体检测(Group Detection的目标是将图中具备共同特性的对象进行聚类,目前已经有一系列的技术方法被提出来解决此类问题。而当前最大的挑战是找到一种扩展性好的方法来对日益复杂的图进行结构剖析以协助知识发现的过程。5.3.4 实体解析实体解析(Entity Resolution是一类识别某一类领域中对象的任务

24、,其目标是判定数据集中的哪一个对象对应于现实世界中的实体。在数据库、自然语言处理、个人信息管理和一些其他领域中都能够找到该类问题的例子。5.3.5 链接预测 链接预测 （Link Prediction） 就是在对象的属性以及已观察到的链接的基础之上预测在两个实体之间是 否存在链接，例如预测某个团体中的两个人之间是否具备朋友关系；或者是在时刻 t 时已经观察到链接存 在的情况下预测在时刻 t+1 时链接是否依然存在。 该类问题可以被简单地视为二元分类 （binary classification） 问题：对于两个对象 oi 与 oj，预测 lij 是 1 还是 0（lij 指 oi 与 oj 之

25、间的链接） 。 6 社会网络发现的实际应用 社会网络发现是数据挖掘中侧重于从数据中发现对象与对象之间关系（这些对象及其之间的关系构成 了一个社会网络）的一个子领域，目前它已经在社会与经济生活中展开了实际的应用。例如购物网站对相 关人群的预测、从已知的通讯数据构建可能的犯罪关系网络、预测垃圾邮件并拦截等的商业与社会领域， 并且今后将在更多的领域展开应用。 中国移动深圳分公司是一家拥有大量客户数据的通信公司，从 2008 年下半年开始，该公司与 SAS 公 司展开合作对其所拥有的客户数据进行社会网络发现与分析，成功地挖掘出了若干的特定客户群，并在此 基础上开展了有效的业务推广，改善了客户的体验与满

26、意度，取得了良好的口碑效应10。 7 总结 社会网络发现是数据挖掘学科中的一个子领域，侧重于从数据中发现对象与对象之间的关系，并在此 基础上展开分析和应用。社会网络中的数据大多采用图的形式来表示，且具有结构化数据的特征。与传统 的数据挖掘任务相比，社会网络发现任务更加注重对象之间的关系，且我们不能假定这些数据是独立同分 布的。 目前已经有一些方法被提出用于进行社会网络的发现与分析，如基于相似度度量的方法、基于统计的 方法、基于 ILP 的方法、基于频繁模式挖掘的方法、基于图性质的方法等。链接挖掘是社会网络发现领域 中的有力工具， 本文简单介绍了链接挖掘方法的基础与理论背景， 并简要介绍了几种常

27、见的链接挖掘任务。 社会网络发现目前已经在很多的场合得到了应用，并且该领域正得到越来越多的关注与研究，今后必 将在更多的场合得到更加广泛的应用。 致谢 在本文结束之际，作者要感谢任课教师黎铭。黎老师在数据挖掘课堂上认真细致、深入浅出的 授课，使得作者对该门学科有了基础与感性的认识。此外，对于如何查阅外文文献以及组织论文的结构， 黎老师在其主页上给出了详细的提示，这对于作者完成本文具有特别重要的作用。同时，在本文的写作过 程中，作者数次向黎老师请教相关的问题，并有幸得到了他的耐心答复，才使得本文的写作能够顺利地进 行下去。此外，作者在与一些同学（如居然、王刚、刘玉龙等）的讨论中获得了一些宝贵的写作思路与研 究方法，在此对他们一并表示感谢。 References: 1 2 /wiki/Social_network , “Social Network from Wikipedia”, 2010. David Jensen, Jennifer Neville. Data Mi