（计算机科学与技术专业论文）关系马尔可夫网及其在社会网络中的应用研究.pdf

，-_1， 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) ： 一 学位论文作者签名： 闰角燕 导师虢僦磁 签字日期：卫h 年7 月午日签字日期：叫d 年，7 月形日 1 f 、 中图分类号：t p l 8 1 u d c ：0 0 4 8 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 关系马尔可夫网及其在社会网络中的应用研究 r e s e a r c ho nr e l a t i o n a lm a r k o vn e t w o r k sa n di t sa p p l i c a t i o ni n s o c i a ln e t w o r k s 作者姓名：闰海蓉 导师姓名：林友芳 学位类别：工学 学号：0 8 1 2 0 5 2 2 职称：副教授 学位级别：硕士 学科专业：计算机科学与技术研究方向：数据与知识工程 北京交通大学 2 0 1 0 年6 月 nii_r 埘。， 致谢 本论文的工作是在我的导师林友芳副教授的悉心指导下完成的，林友芳副教 授严谨的治学态度和科学的工作方法给了我极大的影响和帮助。在学习和科研上， 林友芳副教授对我严格要求，督促我不断进取。在生活中，林老师给予我无微不 至的关怀。在此衷心感谢三年来林友芳老师对我的关心和指导。 实验室的魏名元、韩升老师悉心指导我们完成了实验室的科研工作，在学习 上和生活上都给予了我很大的关心和帮助，在此向林友芳老师表示衷心的谢意。 万怀宇博士和武志吴博士对于我的科研工作和论文都提出了许多的宝贵意 见，在此表示衷心的感谢。 在实验室工作及撰写论文期间，王熙、黄昆、黎雷等同学对我论文中的研究 工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 i， i。r 摘要 在现实社会网络中存在着许多关系数据，这些数据集合由不同类型的实体构 成，实体之间广泛地存在着复杂的链接关系，对这些链接信息的挖掘可以为我们 提供关于这个社会网络更丰富更准确的信息。因此，研究如何充分利用数据间的 链接关系对数据进行分类在社会网络分析中具有重要的意义。 关系马尔可夫网是一种能够有效处理复杂关系数据的判别式概率图模型，由 马尔可夫网和关系模式结合产生。将该模型应用于社会网络数据分类任务中，可 以充分捕捉数据间的依赖关系，从而有效提高数据分类的准确度。 一 本课题对关系马尔可夫网模型的学习过程进行了一定的研究。其中，深入研 究了采用似然估计方法构造模型目标函数的过程。研究发现，随着数据规模的扩 大，该方法的时间复杂度越来越高。为了解决这一问题，引入了采用伪似然估计 方法代替似然估计方法来构造目标函数。在参数优化方面，研究了共轭梯度法、 梯度下降法和拟牛顿法等非线性最优化方法以及黄金分割法、牛顿法和 a r m i j o g o l d s t e i n 法等一维搜索方法。并且从分类准确度和时间复杂度两个方面比 较了各个算法的优缺点，力求给出一种较优的算法组合方案。 在实验过程中，针对c o r a 数据集和w e b k b 数据集分别采用关系马尔可夫网 进行了数据分类。实验证明采用伪似然估计方法构造目标函数在时间复杂度方面 比采用似然估计方法要低很多。在参数优化时，采用拟牛顿法和黄金分割法的组 合方案可以同时取得较高的分类准确度和较低的时间复杂度。 关键词：关系马尔可夫网；社会网络分析；最优化；似然估计；分类 分类号：t p l 8 1 j 丝塞交通太堂亟堂僮论塞垦墨! 至 a b s t r a c t t h e r ea r em a n yr e l a t i o n a ld a t ai nr e a l w o r l ds o c i a ln e t w o r k s t h e s ed a t a s e t s c o n s i s to fd i f f e r e n tt y p e so fe n t i t i e sw i t he x t e n s i v ea n dc o m p l e xl i n k s t h em i n i n go f t h e s el i n k sc a np r o v i d eu sr i c ha n da c c u r a t ei n f o r m a t i o no ft h es o c i a ln e t w o r k s t os t u d y h o wt ou s eo ft h e s el i n ka t t r i b u t e ss u f f i c i e n t l yi so fg r e a ts i g n i f i c a n c ei ns o c i a ln e t w o r k a n a l y s i s r e 1 a t i o n a lm a r k o vn e t w o r ki so n eo fd i s c r i m i n a t i v ep r o b a b i l i s t i cg r a p hm o d e l s t h r o u g ht h ec o m b i n a t i o no fp r o b a b i l i s t i ci n f e r e n c em o d e la n dr e l a t i o n a ls c h e m a ，i tc a l l d e a lw i t hc o m p l i c a t e dr e l a t i o n a ld a t ae f f e c t i v e l y a p p l y i n gt h em o d e lt os o c i a ln e t w o r k d a t a s e t sc l a s s i f i c a t i o nc a nf u l l yc a p t u r et h ed e p e n d e n c i e sa m o n gt h e m ，t h u se f f e c t i v e l y i m p r o v et h ea c c u r a c yo fc l a s s i f i c a t i o n t 1 1 i sp a p e rr e s e a r c h e st h el e a r n i n gp r o c e s so fr e l a t i o n a lm a r k o vn e t w o r k w e d e e p l ya n a l y s et h el i k e l i h o o da p p r o a c ht oc o n s t r u c tt h eo b j e c t i v ef u n c t i o n h o w e v e r , t h e e x p e r i m e n t sf o u n dt h a tt h et i m ec o m p l e x i t yb e c o m e sh i g h e ra n dh i g h e ra l o n gw i mt h e i n c r e a s i n go ft h es i z eo fd a t a s e t s t os o l v et h i sp r o b l e m ，t h i sp a p e r i n t r o d u c e s p s e u d o - l i k e l i h o o da p p r o a c hi n s t e a do fl i k e l i h o o da p p r o a c ht oc o n s t r u c tt h eo b j e c t i v e f u n c t i o n w 1 1 i l ei nt h ep a r a m e t e ro p t i m i z a t i o n ，w er e s e a r c hs o m ee f f e c t i v en o n l i n e a r o p t i m i z a t i o na l g o r i t h m s ，s u c h a s c o n j u g a t eg r a d i e n ta l g o r i t h m ，g r a d i e n t d e s c e n t a l g o r i t h ma n dq u a s i - n e w t o na l g o r i t h m a n dw ea l s or e s e a r c hs o m eo n e d i m e n s i o n a l s e a r c h a l g o r i t h m s ，s u c h a s g o l d e n s e c t i o n a l g o r i t h m ，n e w t o na l g o r i t h m a n d a r m i j o - g o l d s t e i na l g o r i t h m i na d d i t i o n ，t h i sp a p e rc o m p a r e sb o t ht h ea d v a n t a g e sa n d d i s a d v a n t a g e so fe a c ha l g o r i t h ma c c o r d i n gt ot h ec l a s s i f i c a t i o na c c u r a c i e sa n dt h et i m e c o m p l e x i t i e s ，a n dt h e ns e e k st op r o v i d ea no p t i m a lc o m b i n a t i o no ft h e s ea l g o r i t h m s w eu s er e l a t i o n a lm a r k o vn e t w o r kf r a m e w o r ko nac l a s s i f i c a t i o nt a s kw i t hc o r a d a t a s e ta n dw e b k bd a t a s e t a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h et i m ec o m p l e x i t y o fp s e u d o - l i k e l i h o o di sm u c hl o w e rt h a nl i k e l i h o o da p p r o a c h m i l ei nt h ep a r a m e t e r o p f i m i z a t i o n ，t h e c o m b i n a t i o no fq u a s i n e w t o na l g o r i t h ma n dt h eg o l d e ns e c t i o n a l g o r i t h mc a na c h i e v eh i g h e rc l a s s i f i c a t i o na c c u r a c ya n dl o w e rt i m ec o m p l e x i t y k e y w o r d s ：r e l a t i o n a lm a r k o vn e t w o r k s ；s o c i a ln e t w o r ka n a l y s i s ；o p t i m i z a t i o n ； l i k e l i h o o de s t i m a t i o n ；c l a s s i f i c a t i o n c i 。a s s n o ：t p l8 1 目录 摘要i i i a b s t r a c t i v 1引言1 1 1前言1 1 1 1 课题背景和意义_ ：1 1 1 2 国内外研究现状2 1 2论文主要内容一3 1 2 1 研究的目标和内容3 1 2 2 论文的组织结构4 2关系马尔可夫网在社会网络中的应用综述5 2 1引言5 2 2社会网络分析相关概念一5 2 2 1 社会网络的表示和数据特点：5 2 2 2 社会网络数据的分析任务8 2 2 3 关系数据的分类问题9 2 3统计关系学习方法及分类1 2 2 4基于关系马尔可夫网的社会网络数据表示1 3 2 5小结一1 3 3关系马尔可夫网模型1 5 3 1引言1 5 3 2马尔可夫网的定义1 5 3 2 1 基团的势函数1 6 3 2 2 马尔可夫网1 6 3 3关系马尔可夫网的定义1 8 3 3 1 条件马尔可夫网。1 8 3 3 2 关系基团模板18 3 3 3 关系马尔可夫网2 1 3 4关系马尔可夫网模型的学习2 1 3 5小结2 3 4关系马尔可夫网模型目标函数的构造方法2 4 4 1引言2 4 5 6 4 2最大似然估计方法2 4 4 2 1 似然关系模型2 4 4 2 2 最大似然估计方法。2 5 4 3最大伪似然估计方法2 6 4 4基于参数后验概率的估计方法2 7 4 5关系马尔可夫网络模型的推理算法2 7 4 6 小结。3 2 关系马尔可夫网的参数学习：3 3 5 1 引言3 3 5 2一维搜索方法。3 3 5 2 1 黄金分割法3 4 5 2 2 牛顿法3 5 5 2 3 a r m i j o g o l d s t e i n 法3 5 5 2 4 一维搜索方法对比总结3 6 5 3 共轭梯度法3 6 5 4 其他最优化方法。：3 7 5 4 1 梯度下降法3 8 5 4 2 拟牛顿法3 8 5 5 各个方法优缺点比较3 9 5 6 ，j 、结一4 0 基于关系马尔可夫网的关系数据分类与实验分析4 1 6 1 引言4 1 6 2 数据集介绍和预处理4 1 6 2 1 数据集介绍4 1 6 2 2 数据集预处理4 2 6 3 实验的总体设计4 3 6 3 1 实验目的4 3 6 3 2 实验总体设计4 4 6 4基于特定数据集构建关系马尔可夫网模型4 8 6 4 1 关系基团模板的定义4 8 6 4 2 构建关系马尔可夫网模型的相关算法4 9 6 4 3 目标函数参数优化算法5 4 6 。5实验结果5 9 6 6 实验结果分析。6 3 6 7 d 、结6 4 7 结论6 6 7 1论文工作总结6 6 7 2未来的研究工作6 6 参考文献6 8 作者简历7 1 独创性声明7 2 学位论文数据集7 3 ： 一 一 j 1 引言 1 1 前言 传统数据挖掘技术所处理的对象通常以“属性值的形式存在于单一关系之 中，这样的数据称为扁数据。但现实社会网络中存在着许多关系数据，这些数据 集合由不同类型的实体构成，实体之间广泛地存在着复杂的链接关系，它们并不 满足扁数据的独立同分布( i i d ) 假设。对链接信息的挖掘可以为我们提供关于这 个社会网络更丰富更准确的信息。如何充分利用数据间的链接关系以求得到更高 的预测或分类的准确度成为近来的研究热点之一。本章从总体上介绍了选题的背 景和意义、当前的研究现状、本文主要的研究内容以及论文的章节组织结构。 1 1 1 课题背景和意义 由于社会网络分析具有巨大的应用性价值，近年来成为数据挖掘的热门课题 之一，引起了越来越多研究人员的关注。社会网络是指社会行动者及其之间关系 的集合。社会行动者可以是个体或者集体性的社会单位，比如个人、家庭、组织、 村落、学校、社区、城市、国家等等。社会中人与人交往关系构成的网络，电信 通话网络，国家之间的贸易关系网络，生物信息学中分子相互作用构成的网络以 及计算机病毒传播网络，网页链接关系构成的网络，文章引用关系构成的网络等 等都是典型的社会网络【l 】。从数据挖掘的角度来看，社会网络是采用图模型表示的 异构多重关系的数据集合，节点表示对象，节点与节点之间的边表示对象之间的 链接关系【l j 。 社会网络中既包括了丰富的节点内容属性，还包含了丰富的链接属性，如何 将这两类属性结合起来，融合在一个统一的模型之中，充分利用内容与链接信息 来进行分类和预测任务，是一个正在被研究的热门课题。 关系马尔可夫网是一种重要的统计关系模型，与假定数据是相互独立、等概 率分布的传统数据挖掘方法不同，它通过将概率推理模型和关系模式结合起来， 充分利用数据间的依赖关系，可以得到更高的预测和分类的准确度【2 j 。因此，针对 社会网络建立关系马尔可夫网模型来进行数据分类或者进行其他社会网络分析任 务具有重要的研究价值和应用意义。例如，对电信通讯企业巨量的用户交往数据 进行分类，可以得到更为准确的分类结果，利于管理决策部f - i n 定针对性强，更 具个性化的服务；或者根据重要程度对用户进行排序，利于管理决策部门充分利 用重要客户的价值。另外，随着i n t e r n e t 的飞速发展，网上的各种信息，如：电子 文档以及电子邮件的信息量呈爆炸趋势，大规模的文本处理已经成为一个挑战。 利用关系马尔可夫网对这些信息进行文本分类，可以充分挖掘数据的链接结构， 将数据间的链接关系与数据的文本内容属性结合起来得到良好的分类精度，帮助 人们更有效地检索、查询、过滤和利用这些信息。尤其是对于w e b 页面分类来说， 采用关系马尔可夫网络模型不但可以捕捉非关系模型可以利用的内容信息，比如 页面中出现的词以及元数据标题中的词和链接锚等，还可以捕捉关联页面标 签之间的有用信息，比如学生页面大多数链接到课程页面，利用这些关系降低了 关系模型分类的错误率。 1 1 2 国内外研究现状 在社会网络数据中，实体之间的联系不仅复杂而且互相影响。为了提高数据 分类以及链接预测等任务的准确度，一种方法是把相互关联的实体结合起来预测。 但是该模型的应用在网络的链接图存在较多环路时会遇到一些问题。另外，该模 型经常被用来优化给定证据节点值和目标节点的联合概率。而分类问题等分析任 务需要在给定证据节点值的情况下，计算目标节点的条件概率。为了解决上述问 题，b e n t a s k a r 等【3 】于2 0 0 2 年提出了关系马尔可夫网络模型。该模型提出后，许 多学者开展了这方面的研究，并取得了一些研究成果，促进了关系马尔可夫网更 广泛的应用。 在国际上，关系马尔可夫网在各种类型的社会网络方面的应用成为近年来数 据挖掘领域热门的研究课题。 2 0 0 2 年，b e n t a s k a r 等【3 】构建关系马尔可夫网来解决w e d 页面分类的问题。 在模型训练方面，使用最大后验概率的方法定义目标函数，然后使用共轭梯度法【4 】 对目标函数进行参数优化。在推理算法方面，b e n t a s k a r 等采用信度传播算法 5 ，6 1 ( b e l i e f p r o p a g a t i o n ) 作为关系马尔可夫网络的推理算法。 2 0 0 3 年，b e n t a s k a r 等【7 】在链接预测领域上应用关系马尔可夫网，实验表明， r m n 的共同分类方法和链接标记上的子图模式比扁数据分类在预测精度上有显著 的提高。 2 0 0 3 年，e s e g a l 等人【8 】在生物信息学领域将朴素贝叶斯模型和关系马尔可夫 网结合起来构建统一的概率模型来发现分子路径。通过把基因表现和蛋白交互的 信息结合起来以提高准确率。 2 0 0 4 年，r , b u n e s c u 等人【9 】将r m n ( r e l a t i o n a lm a r k o vn e t w o r k s ) 框架应用在信 2 息提取领域。通过从生物医药学文本中抽取蛋白名称的实验表明，使用r m n 的信 息提取比同类方法有更好的性能。2 0 0 5 年，l i nl i a o 等uo j 在活动识别领域扩展了 r m n ，提出在r m n 中使用m c m c 方法进行学习和推理。 在国内，对于关系马尔可夫网特别是将关系马尔可夫网框架应用于社会网络 分析中的研究不是特别广泛。吉林大学的刘大有教授对于关系马尔可夫网在社会 网络领域的应用有一定的探索。孙舒杨博士对统计关系学习方法有一定的研究， 深入介绍了m a r k o v 逻辑网，并指出r m n 和m a r k o v 逻辑网的实质相同。 目前，对于关系马尔可夫网的学习方法，主要采用基于最大后验概率的方法 构造出目标函数，然后采用最优化方法对目标函数进行优化，其中，常用的最优 化方法是共轭梯度法。而在网络的推理算法方面，主要是采用近似推理算法，如： 信度传播( b p ) 算法和m c m c 算法等。然而，在学习过程中，需要采用最优化算法 进行迭代来一步步逼近最优解，每一次迭代过程，都需要重复多次调用近似推理 算法在网络中进行传播，这就导致关系马尔可夫的学习时间复杂度很高，学习时 间太长。当社会网络数据规模非常庞大时，时问复杂度是难以被接受的。 1 2 论文主要内容 1 2 1 研究的目标和内容 本论文的主要研究目标是分别针对c o r a 数据集以及w e b k b 数据集进行分析， 充分利用实体之间的引用关系来构建关系马尔可夫网，对数据集中的实体数据进 行分类，并将分类结果与采用传统方法进行数据分类的结果进行对比。另外，在 实验过程中，本论文还需要采用不同的目标函数构建方法以及参数优化方法，并 在准确度和时间复杂度方面对各种方法进行对比和提出改进。结合本论文的研究 目标，作者主要做了以下几个方面的工作： 在理论学习方面，需要研究有关统计关系学习和社会网络分析的理论、模型 和算法，以及数据挖掘中相关理论、算法和最优化理论等。 在模型学习方面需要重点研究关系马尔可夫网模型的构建方法，信度传播算 法以及非线性最优化的相关算法等。 在实验验证方面，首先，需要对数据集进行分析和预处理，将文本形式的数 据转换为具有关系模式的数据，即实体的类型、属性，及属性之间的关系都以表 结构的形式表示。然后，采用信度传播算法构建关系马尔可夫网模型，并采用基 于最大后验概率的方法定义目标函数。目标函数得到后，分别采用共轭梯度法、 梯度下降法以及拟牛顿法对目标函数进行参数优化，对不同方法得到的实验结果 进行分析和对比，给出一种整体效果较优的算法组合方案。最后，将基于关系马 尔可夫网络模型的分类结果和采用传统数据挖掘方法进行分类的结果进行比较， 总结模型特点和后续研究方向。 1 2 2 论文的组织结构 从整体结构上，本文一共分为七章。 第一章介绍了本课题的研究背景和意义，叙述了国内外的研究现状以及现有 研究方法存在的问题，介绍了本课题研究的目标和内容，以及所完成的工作。 第二章介绍了本课题的理论背景知识，包括社会网络数据的特点和分析任务、 关系马尔可夫网的特点以及将关系马尔可夫网应用于社会网络数据分析的优越 性，重点介绍了应用关系马尔可夫网进行关系数据分类的数据表示和方法。 第三章是本文的核心理论知识，介绍了马尔可夫网的定义、关系马尔可夫网 的定义以及其他相关概念的定义，然后重点介绍了关系马尔可夫网模型的学习过 程。 第四章详细介绍了关系马尔可夫网模型中目标函数的构造方法，包括基于似 然关系模型的构造方法和基于伪似然模型的构造方法，并且介绍了关系马尔可夫 网的近似推理算法。 第五章详细介绍了关系马尔可夫网中的参数优化算法，包括共轭梯度法、梯 度下降法和拟牛顿法，以及在参数优化算法中非常重要的一维搜索算法。同时对 各个算法的优缺点进行了比较。 第六章给出了本论文的实验过程和结果，针对特定数据集建立了关系马尔可 夫网并进行数据分类，实验结果表明分类结果与实际需求相符。 第七章总结全文，对本课题的研究工作做了分析和总结，并指出了不足，最 后给出本课题后续的研究内容和方向。 4 2 关系马尔可夫网在社会网络中的应用综述 2 1 引言 关系马尔可夫网是一种非常重要的统计关系模型，它通过将概率推理模型和 关系模式结合起来，捕捉和利用数据与数据之间的依赖关系来得到更高的预测或 分类的准确度。关系马尔可夫网由于其潜在的巨大应用价值和广泛的应用前景在 生物信息学、w e b 应用、地理信息系统、信息提取、自然语言处理和社会网络分 析方面取得了一些研究成果。与传统的数据挖掘只关注数据实例不同，社会网络 分析更侧重实体之间相互联系的分析和挖掘。因此，从数据挖掘角度来看，社会 网络分析又称为链接挖掘( l i n km i n i n g ) 或者链接分析( l i n ka n a l y s i s ) 。本章重点介绍 了社会网络数据的特点和分析任务、关系马尔可夫网的基本概念以及关系马尔可 夫网络在社会网络中的相关研究和应用。 2 2 社会网络分析相关概念 2 2 1社会网络的表示和数据特点 2 0 世纪3 0 年代，j a c o bm o r e n o 和哈佛大学的研究人员分别提出了采用社会网 络模型来分析社会学中的现象和问题。社会学家发现社会实体之间存在着相互的 依赖和联系，且这种联系对于每个社会实体都有着非常重要的影响。基于这样的 观察，他们采用网络模型来表示社会实体之间的关系，并进一步用来分析社会关 系之间的模式和隐含规律【9 j 。 传统数据挖掘的对象都集中于“扁数据”，即数据由结构相同的实体构成，并 且分布被假设为是“独立同分布l i d ”，然而在现实世界中存在着大量的半结构化 关系数据，除了每个结点自身的属性之外，更重要的是结点之间的联系。如超文 本、w e b 网页、w e b 图像、文章引用关系数据、教育资源等，这些数据集合由不 同类型的实体构成，其中每个实体类型由不同属性集合刻画，实体通过不同类型 的链接而彼此相关，而且链接结构是信息的重要来源。 早期由于数据收集方式的限制，社会网络局限于一个小的团体之内，网络规 模往往只有几十个结点。借助于图论和概率统计的知识，人工处理可以从中分析 出一些简单的性质和模式。但是，随着现代的信息技术的发展，越来越多的数据 5 被收集和整合在一起，现在的社会网络规模比早期庞大很多，通常包含几千或者 几万的结点，甚至有多达百万个结点的网络。面对这样庞大复杂的网络，简单的 数学知识和原始的人工处理已经不可能进行有效的分析，需要寻求更加有效地分 析模型和工具。 关系数据挖掘【1 1 , 1 2 1 是从包含多种对象并且对象间存在联系的数据中发现知识 的方法，该方法并不首先将关系数据转化为原来的单表模式，而是直接在这样的 数据中挖掘关系模式。关系数据挖掘所对应的数据类型，更为符合一般的关系数 据库中的应用的数据。因此，多关系数据挖掘可以更加有效的分析社会网络，尤 其是复杂庞大的网络。， 多关系数据挖掘有很多名称，侧重于关系知识表示的研究者称之为“统计关 系学习 ( s t a t i s t i c a lr e l a t i o n a ll e a r n i n g ，s r l ) ，侧重一阶逻辑知识表示的研究者称 之为“概率逻辑学习 ( p r o b a b i l i s t i cl o g i cl e a r n i n g ，p l l ) ，侧重于数据挖掘的研究 者称之为“多关系数据挖掘 或“关系学习 ( r e l a t i o n a ll e a r n i n g ，r l ) 。 为了进行有效地社会网络分析，首先要将社会网络数据形式化。社会网络模 型中不可缺少的工具是数学中的图论和概率统计。f r e e m a n 提出了社会网络分析必 须具备的四个特征【1 3 】： 1 社会网络分析更注重行动者( a c t o r ) 之间的联系，而不是行动者本身所具有 的性质； 2 关于行动者之间联系( t i e ) 的数据必须通过系统化的方法收集； 3 建立在图模型之上； 4 使用数学和计算工具来从这些关系中获取有意义的信息。 其中，第三点明确说明，图模型作为社会网络基本的表示是合适的【1 4 】。图模 型s = 由图的网络拓扑结构g 和图上的概率分布p 两部分组成，因此图模 型的学习可以被分解成两个子阶段： 1 网络拓扑结构的学习，简称为结构学习； 2 概率分布的学习，简称为参数学习。 进一步讲，结构学习就是找到和训练数据拟合得最好的网络拓扑结构，而参 数学习则是指在给定网络结构的情况下，通过训练数据学习得到网络中的概率分 布。 社会网络就是由行动者( 即图中的节点) 和行动者之间的联系( 即图中的链 接) 组成的，其中， 行动者( a c t o r ) ：社会实体，可以表示具体的个人，社团及其它集体社会单元。 联系( r d a t i o nt i e ) ：不同的社会实体通过联系连接在一起。在不同的网络中， 其意义也不同。例如：一个人对另一个人的评价，物质资料在实体间的转移，实 6 复杂的模式，包括： 二元组( d y a d ) ：由两个行动者及他们之间的关系组成，这是研究关系模式的基 本单位； 子e f l ( s u b g r o u p ) ：由网络中的一部分行动者和他们之间的关系组成，可以通过 子图来研究社会网络中的一个小团体所具有的特征： 图( g r a p h ) ：所有行动者及其之间的关系，分析社会网络的总体特征。 我们以- 一个描述了行动者和他们所参与事件的社会网络为例【1 5 1 ，如果用图结 构表示，一个自然地表示可以用二分图：一个集合包含行为者节点，一个集合包 含事件节点。连接这两个集合中的点的边表示了行为者的参与关系，即如果一个 行为者参与了一个事件，则这个行为者节点和这个事件节点之间就存在一条边， 反之则没有边。然而我们还可以从另一种视角看待这个社会网络，采用其他的表 示。如我们可以以行为者为节点，两个行为者之间的边则表示了这两个行为者参 与了同一个事件。这种表示使我们的分析能更加以行为者为中心。另一方面，如 果我们把事件作为节点，两个事件之间的链接表示了有行为者参与了这两个事件， 那么这种表示使我们的分析更加以事件为中心。对于存在多种节点和链接的社会 网络，这样的表示形式会更多。所以为解决一个具体社会问题，合理地选择社会 网络表示形式对于有效的社会网络分析是非常关键的。 从上面描述的社会网络的特点中可以看出，社会网络数据是一种结构化的关 系数据。数据的信息不仅包含在行动者本身，大量的信息包含在行动者之间的联 系中。因而，在对社会网络数据进行挖掘的过程中，必须注意同时考虑行动者的 属性及其于其它行动者之间的联系。 以超文本文件集合的分类为例，显然最简单直接的分类方法就是采用词袋模 型( ab a go f w o r d s ) ，利用出现在网页上的单词属性来对每个网页进行分类，但是 采用词袋模型根本没有考虑到超文本文件之间的复杂依赖关系：两个文件之间存 在着超链接，表明它们可能是主题相关的；每个文件有内部结构，例如一个文件 被分为几个部分，从文件的同一部分发出的超链接所指向的文件更可能类型相近。 当对文件集合进行分类时，这些都是非常重要的提示，它们可以帮助获得更好的 分类准确度。 总的来说，在对社会网络数据进行分析时要充分挖掘数据中蕴涵的大量联系 信息，才能建立更加准确的模型。 7 2 2 2 社会网络数据的分析任务 社会网络模型建立之后，根据分析的侧重点不同，可以大致总结出以下几种 社会网络数据的分析任务，如表2 1 所示【1 5 】： 表2 1 社会网络数据的分析任务 t a b l e2 1t a s ko fs o c i a ln e t w o r kd a t aa n a l y s i s 节点相关任务 基于链接的节点排序( l i n k b a s e do b j e c tr a n k i n g ) 基于链接的节点分类( l i n k b a s e do b j e c tc l a s s i f i c a t i o n ) 节点聚类( o b j e c tc l u s t e r i n g ) 链接相关任务链接预测( l i n kp r e d i c t i o n ) 图相关任务 子图发现( s u b g r a p hd i s c o v e r y ) 图分类( g r a p hc l a s s i f i c a t i o n ) 1 节点相关任务 基于链接的节点排序是社会网络分析中的一个核心分析任务【1 6 】，它是指通过 分析利用图中的链接结构，依据某种衡量节点重要性的度量标准来对图中节点进 行排序。例如：最有价值的用户【1 7 】对于商家具有不可忽视的地位，给予他们特别 的照顾往往能够取得巨大的受益。显然，通过将客户按照重要程度排序，提供不 同的服务，才能够使得商家取得最大的经济利益。 基于链接的节点分类与传统分类问题的最显著的不同在于节点的类别是彼此 相关的。在基于链接的节点分类问题中，一个数据图g - - _ - 表示了节点集合y 和他们之间的链接集合e ，我们的任务是将矿中的成员赋予某一类标签【1 5 1 。如何 设计合理的分类算法能有效地利用这些链接信息是研究者需要解决的重要问题。 例如：对巨量的电信通讯企业的用户交往数据进行分类，分析不同用户组的属性 特点，利于管理决策部门制定针对性强，更具个性化的服务；对网页信息、网上 电子文档以及电子邮件等信息进行文本分类，可以帮助人们更有效地检索、查询、 过滤和利用页面信息。 节点聚类又称为群体检测，它的目的是将有着共同的特征的节点聚类。首先 假设图中的节点和链接都属于同一种类。在这种假定下，群体检测的技术可以分 成聚合聚类和分裂聚类两种。在同一个类别当中的行动者具有相似的特征，而不 同类别当中的行动者应当具有一定的差异。这个在社学会的研究中有着非常重要 的作用，能够用于发现不同的社会阶层。 2 链接相关任务 链接预测是社会网络的一个主要任务，是指基于所链接节点的属性和已观察 到的链接关系来预测某链接是否存在。链接预测的应用非常广泛，包括预测社会 中人与人之间的朋友关系，电子邮件、电话联系，合作关系等。往往一些链接被 观察到，未被观察到的需要我们去预测；或者存在一个时间序列，在某个时间点t 的连接状态已知，要预测什1 时间点的链接状态【1 5 】。 3 图相关任务 子图发现也是一个重要的分析任务，是指从社会网络中找出一些频繁出现的 或者特别感兴趣的子图。频繁的子图往往代表了社会网络中频繁出现的模式，分 析这些子图能够加深对社会关系的理解。而另外一些特别的子图可能表征不同社 会网络的特点，发现它们对于社会网络的分类有很大帮助。 不同于基于链接的节点分类，图分类是一种试图将整张图用正或负标签来分 类的监督学习问题。这是最早的将机器学习和数据挖掘技术应用于图数据的任务。 三种用于图分类的主要方法有：基于图上特征挖掘，归纳逻辑编程( i l p ) 和定义 图核函数。 2 2 3 关系数据的分类问题 从应用角度来说，基于链接节点的分类又可称为关系数据的分类问题。分类 是社会网络分析中一项非常重要的任务，目前在商业上应用非常广泛。分类的目 的是通过学习得到一个分类模型，该模型能把数据库中的数据项映射到给定类别 中的某一个。 分类面向的对象是由类别己知的样本构成的数据集，数据集又分为训练集 ( t r a i n i n gs e t ) 和测试集( t e s ts e 0 。每个样本有多个属性( a t t r i b u t e ) 或称特征( f e a t u r e ) ， 属性既可以是连续属性，也可以是离散属性，其中有一个属性被称为类别属性( 又 称为标签或标注，l a b e l ) ，用来标注该样本所属的类别。 分类需要如下两个步骤来完成【l 8 】： 分类器训练过程：通过对训练集的学习，用样本的其它属性建立一个划分 类别属性的模型； 分类器测试过程：用测试集来评价模型的准确率。 被评价为准确的模型便可以用来对新数据进行分类，从而达到预测的目的。 分类实际上就是将训练数据间的共性与个性具体化、形式化，并给出一个确定的、 可操作的描述，整个训练和测试过程被称为分类器构造【1 9 】。在分类器构造中，测 试只是对模型的评估过程，而训练则是最为重要的。 分类器训练( t r a i n i n g ) 又分为三个步骤： 通过对训练集中样本数据的学习，尽可能从中得到事先未知的、隐藏于数 9 据中的重要信息分类判别函数； 选定一个参数模型，通过学习来确定模型的参数； 用模型来直接或间接地拟合或逼近分类判别函数。 之前提到社会网络中存在大量的关系数据，关系数据之间的链接和依赖关系 对关系数据分类来说是不可缺少的重要信息。 为了更好地对关系数据进行描述，首先介绍一个概念：s c h e m a 。 定义2 1 ：s c h e m a 是描述实体、实体属性以及实体之间关系的一个框架。一个 s c h e m a 定义一个关系域【2 0 】。 以超文本文件为例描述关系域。超文本就是一个关系域，其中有两个实体类 型：d o c 和l i i l l 【。若假设每个网页用词袋b w 来表示，则d o e 实体类型包含如下 属性：d o c l a b e l 和d o c h a s w o r d k ( k 为词袋中任意单词，即k b w ) ，其中 d o c l a b e l 为标签属性，表示网页的主题，其属性值取自类别值集合；d o c h a s w o r d k 为布尔属性，表示单词k 是否在该网页中出现。l i i l l 【实体类型包含两个属性： l i i l l ( f r o m 和l i n k t o ，它们的属性值都为d o c 实体。 形式化地讲，一个s c h e m a 指定一个实体类型集合占= 但t ，e 2 ，晟) ，其中每个 实体类型e 伴随着三个属性集合：内容属性e 彳( 例如d o c h a s w o r d k ) ，标签属 性e 】，( 例如d o e l a b e l ) ，和索引属性e r ( 例如l i l l l 【t o ) 。为了简便，标签属性 和内容属性的取值范围都为有限集合，索引属性包含一个特殊的唯一的关键属性 e k ，用来识别每个实体。 定义2 2 ：s c h e m ag 的实例( i n s t a n t i a t i o n