（计算机应用技术专业论文）email社会网络的社群挖掘和分析算法研究.pdf

中文摘要 随着互联网技术的发展，e m a i l 已日益成为人类日常生活中必不可少的通信方 式之一。人们之间的e m a i l 通信产生了大量的通信数据，从这些数据中挖掘出人类 社会的社群结构并且分析社会成员在社群的重要程度已成为一个重要的研究课 题，对该课题的研究和探索可以应用于犯罪网络挖掘、欺诈团伙检测等领域，对 于执法机关打击恐怖犯罪活动和提高执法效率具有重大的意义。 本文首先介绍了广义的社群概念和传统社会学中凝聚子群的概念，之后提出 了基于连接特性的社群定义。在此基础上，设计了基于连接特性的e m a i l 社会网络 社群挖掘算法，可以比较完整准确的挖掘出社群成员。在分析社群成员在社群中 重要程度的问题上，分别介绍了基于社会网络中心性指标的社群核心挖掘模型和 基于p a g er a n k 思想的社群成员重要程度评价模型，可以比较客观的评价社群成员 在社群中的重要地位。 e n r o ne m a i l 数据集是一个被广泛用于社会网络分析研究的e m a i l 通信数据集。 本文针对该数据集，采用本文所提出的数学模型和算法进行了社群挖掘和成员重 要性评价，实验结果表明本文提出的算法是有效的。 关键词：社会网络分析；数据挖掘；社群挖掘；链接挖掘；e m a i l 社会网络；安然 邮件数据集 分类号：t p l 8 2 a bs t r a c t w i t ht h ed e v e l o p m e n to fi n t e r a c tt e c h n o l o g y , e m a i lh a sb e c o m eo n eo ft h e i n d i s p e n s a b l ew a y so fc o m m u n i c a t i o ni no u rd a i l yl i f e e m a i lc o m m u n i c a t i o n sb e t w e e n p e o p l ep r o d u c eal o to fc o m m u n i c a t i o nd a t a a n di nr e c e n ty e a r s ，i th a sb e c o m ea s i g n i f i c a n tr e s e a r c hp r o j e c tt om i n et h es t r u c t u r eo ft h ec o m m u n i t ya n dt h ei m p o r t a n c e o fi t sm e m b e r sf r o mt h o s ed a t a t h er e s e a r c ho ft h es u b j e c tc a l lb ea p p l i e dt om i n i n g c r i m i n a ln e t w o r k s ，d e t e c t i n gf r a u dg r o u p s ，e t c i ti sa l s oo fg r e a ts i g n i f i c a n c ef o rl a w e n f o r c e m e n to r g a n i z a t i o n st of i g h ta g a i n s tt e r r o r i s m ，c r i m e sa n di m p r o v et h ee f f i c i e n c y o fl a we n f o r c e m e n t t h i sp a p e ra n a l y z e dt h ec h a r a c t e r i s t i c so ft h el i n kb e t w e e nt h ec o m m u n i t ym e m b e r s a n dt h e np r o p o s e dam a t h e m a t i c a lm o d e lb a s e do nt h el i n kc h a r a c t e r i s t i c s i ti sa b l et o m i n et h ec o m m u n i t ym e m b e r sc o m p l e t e l ya n da c c u r a t e l y t oa n a l y z et h ei m p o r t a n c eo f t h ec o m m u n i t ym e m b e ri nt h es o c i a ln e t w o r k ，w ep r o p o s e dt w om a t h e m a t i c a lm o d e l s o n ei sb a s e do nt h ec e n t r a l i t yc o n c e p t so ft h es o c i a ln e t w o r ka n a l y s i s ；t h eo t h e ri sb a s e d o nt h ep a g er a n ko fg o o g l e b o t hc a l lg i v ea no b j e c t i v ee v a l u a t i o no fi m p o r t a n c eo f m e m b e r si nt h ec o m m u n i t y e n r o ne m a i ld a t a s e ti saw i d e l yu s e dd a t a s e ti nt h er e s e a r c ho fs o c i a ln e t w o r k a n a l y s i s i n0 1 1 1 r e s e a r c h ，m a t h e m a t i c a lm o d e l sa n da l g o r i t h m sa r eu s e df o rc o m m u n i t y m i n i n ga n dt h ee v a l u a t i o no fi m p o r t a n c e t h er e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o d s a l ee f f e c t i v e k e y w o r d s ：s o c i a ln e t w o r ka n a l y s i s ；d a t am i n i n g ；c o m m u n i t ym i n i n g ；l i n k m i n i n g ；e m a i ls o c i a ln e t w o r k s ；e n r o ne - m a i ld a t a s e t c i a s s n o ：t p 】8 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：夕蓥 导师签名： 签字日期：2 z , - o3 年7 月少e t 辩醐洲年7 月7 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月日 1 引言 通信技术和互联网技术的发展引发了新的网络生活形态，越来越多的虚拟社 会呈现在人们面前，比如e m a i l 通信形成的人际关系网络、互联网上形成的虚拟社 区等，透过这些网络来得到现实社会的一些结构特点和规律成为近来的研究热点 之一。本章从总体上介绍了选题的背景和意义、当前的研究现状、本文主要研究 的内容以及论文的章节组织结构。 1 1 研究的背景和意义 社会网络分析由于其巨大的应用价值成为近年来数据挖掘热门的课题之一， 受到了越来越多研究人员的关注。社会网络是指由个体以及个体之间的关系构成 的满足社会结构特点的网络，社会中人与人交往关系构成的网络，国家之间的贸 易网络，网页链接关系构成的网络，电信通话网络，生物以及计算机病毒传播网 络，文献引用关系构成的网络等等都是典型的社会网络。从数据挖掘的角度来看， 社会网络是由图表示的异构多重关系的数据集合，节点表示对象，边表示对象之 间的关系。 社群是社会网络中一组具有相同属性的个体集合。在各种社会网络中挖掘社 群具有重要的研究价值和意义。例如，从互联网上进行w e b 社群挖掘，可以找出 相同主题的w e b 网站，建立面向主题的搜索引擎，为用户提供更好的导航服务； 从科学文献引用数据集中进行社群挖掘，可以帮助研究人员找出相同研究领域的 文献等。其中，在e m a i l 通信数据集上进行社群挖掘并且评价社群成员在社群中的 重要程度是一个重要而又意义的研究课题。在各种著名大型网络公司，如网易、 新浪、g o o g l e 等公司，都提供了免费邮箱服务，这些服务所积累的数亿网民的e m a i l 通信记录，具有许多潜在用途。例如，对于执法机关而言，在这些数据中发现犯 罪或者恐怖团伙、欺诈团伙并且分析这些团伙的层次结构，挖掘出其中的核心首 领对于打击犯罪和恐怖活动具有重大的研究意义，可以极大的提高执法效率。因 此，在该背景下本论文对e m a i l 社会网络的社群挖掘和分析算法进行了研究，提出 了e m a i l 社会网络中基于连接特性的社群定义和社群挖掘算法、基于社会网络中心 性指标的社群核心挖掘算法以及基于p a g el a n k 思想的社群成员重要程度评价算 法。之后，本论文在e n r o ne m a i l 数据集上进行了实验，实验结果证明本论文所提 出的算法是有效的，可以比较准确完整的挖掘出社群成员和客观的评价社群成员 在社群中的重要程度。 1 2 国内外研究现状 在国际上，各种社会性网络的社群挖掘成为近年来数据挖掘领域热门的研究 课题。数据挖掘著名学者j i a w e ih a n 教授的研究工作集中在异构多重关系社会网 络的社群挖掘【2 1 ，微软亚洲研究院的w e n j u nz h o u 等人提出了一种新的社群挖掘 数学模型一同心圆模型【3 1 ，在w e b 社群挖掘的工作有g a r yw i l l i 锄f l a k e 等人【4 1 ，在 科学文献社群挖掘主要有r y u t a r oi c h i s e , h i d e a k it a k e d a 等人【5 1 。 目前，国内在社会网络分析特别是在社团挖掘和分析方面的研究和应用才刚 刚起步。四川大学唐常杰教授基于邮件通信网络在社团挖掘和分析方面做了一定 的探索【6 j l 。 在社群分析方面，在社会网络分析中有很多相关的研究工作，主要集中在中 心性分析【8 】，在搜索引擎的研究中有很多重要而有意义的研究成果，相关的工作主 要集中在根据网页之间的链接关系挖掘出权威网页【9 j 。把社会网中一些计算中心性 的方法用来发现网络中的重要节点的做法在文献【2 3 】可以看到，m n e w m a n 把中介 性指标用在合著网中来衡量作家的重要性。s v i r h i t e 【2 4 提出了网络中“最重要节点 的概念，他们罗列了一系列挖掘社会网络中“最重要节点 的方法，其中就包含 了著名的g o o g l ep a g er a n k 算法p j 。 1 3 研究的目标和内容 对e m a i l 通信记录数据的研究和利用存在很多和个人隐私相关的问题，因此， 在法律上可能并不允许针对数亿网民e m a i l 实际通信数据的研究和分析，这些数据 只能在国家安全部门得到法律许可的条件下进行研究和分析。因此，本论文在不 侵犯个人隐私和法律允许的条件下提出以下的研究目标和内容。 本论文的研究目标之一在于对e m a i l 社会网络社群的性质和特点进行分析，给 出形式化的e m a i l 社会网络社群定义，建立e m a i l 社会网络的社群挖掘数学模型， 设计e m a i l 社会网络的社群挖掘算法。 e m a i l 社会网络社群成员重要程度的分析模型和算法是本论文另一个重要的 研究目标，目的在于建立e m a i l 社会网络社群成员重要程度的评价模型，可以客观、 准确的评价e m a i l 社会网络社群成员节点的重要程度。 e n r o ne m a i l 数据集【2 0 j 是目前被广泛用于社会网络分析和文本挖掘的一个 e m a i l 数据集，本文的研究目标之三在于在e n r o ne m a i l 进行社群挖掘和社群分析 的实验以验证本文数学模型和算法的准确性。 2 1 4 本论文研究的成果和创新点 本论文的成果和创新点主要有： 1 ) j i a w e ih a n 的研究集中在多重关系社会网络的社群挖掘【2 】，传统的社群挖掘 研究工作集中在w e b 链接网络【4 】和科学文献网络 s l ，本论文的研究对象是e m a i l 社会网络； 2 ) 本论文根据社会网络中社群的性质和连接特点，提出了基于连接特性的社 群定义，设计了相应的挖掘算法，可以比较精确的挖掘出e m a i l 社会网络中的社群； 3 ) 分析了e m a i l 社群成员的连接关系特点，提出了基于社会网络分析中心性 指标的社群核心挖掘算法，以及基于p a g er a n k 思想【9 】的社群成员重要程度评价算 法，可以比较客观的评价社群成员在社群中的重要程度； 4 ) 对e n r o ne m a i l 数据梨2 0 】的数据模型进行了介绍，给出了e n r o ne m a i l 数据 集构造e m a i l 社会网络的算法，在此基础上进行了社群挖掘和社群成员分析的实验 并给出了实验结果。 1 5 论文的组织结构 从整体结构上，本文一共分为六章。 第一章我们将介绍本文的研究背景和意义、国内外的研究现状、本文主要的 研究内容和目标、论文的研究成果和创新点以及本文的组织结构。 第二章对社会网络分析在数据挖掘中的相关研究和应用方向进行一定的综 述。 第三章首先介绍广义的社群概念和传统社会学中凝聚子群的概念，之后提出 基于连接特性的社群定义，在此基础上，设计了基于连接特性的社群挖掘算法。 第四章首先介绍社会网络分析中心性分析的相关概念，之后我们给出基于中 心性指标的网络核心成员挖掘模型，最后分析了e m a i l 社会网络社群成员连接关系 的特点，根据g o o g l e 的p a g er a n k 算法【9 】建立社群成员重要程度的评价模型。 第五章首先介绍了e n r o ne m a i l 数据集，之后介绍了该数据集的数据模型以及 社会网络的构建算法并给出了社群挖掘和社群成员分析的实验结果。 第六章对本文的研究工作进行了总结，分析了目前研究存在的缺点，提出以 后的研究内容和方向。 2 社会网络分析方法在数据挖掘的应用综述 社会网络分析方法由于其巨大的应用价值而被广泛的应用于现代社会学、管 理学、经济学、心理学、信息科学等各个学科。将社会网络分析应用于数据挖掘 当中成为数据挖掘热门的研究方向之一。与传统的数据挖掘不同，社会网络分析 侧重个体之间相互联系的分析和挖掘，所以，从数据挖掘的角度来看，社会网络 分析也称为“链接挖掘 ( l i n km i n i n g ) 或者“链接分析( l i n ka n a l y s i s ) 。本章重点 介绍了社会网络分析的基本概念以及社会网络分析在数据挖掘的相关研究和应 用。 本章的组织如下：在2 1 节介绍了社会网络分析的基本概念；在2 2 节从数据挖 掘的角度分析了社会网络数据的表示形式和以及社会网络分析的主要任务；在2 3 节对现有的社会网络分析在数据挖掘中的研究方向和应用做了分类介绍；在2 4 节 介绍了一个社会网络数据的知识发现系统的体系结构设计；在2 5 节对本章作了一 定的总结。 2 1 社会网络分析的基本概念 2 0 世纪3 0 年代，j a c o bm o r e n o 和哈佛大学的一组研究人员分别提出了社会网络 模型来分析社会学中的现象和问题。现代社会学主要研究现代社会的发展和社会 中的组织性或者团体性行为。社会学家发现社会实体之间存在着相互的依赖和联 系，并且这种联系对于每个社会实体有着重要的影响。基于这样的观察，他们通 过网络模型来刻画社会实体之间的关系，并进一步用来分析社会关系之间的模式 和隐含规律，这就是社会网络分析。和以往社会学研究的方法不同，它提供了一 种形式化、概念化的途径来看待“社会这个研究对象的性质和发展进程，是一 种应用性很强的社会学研究手段，有很多的应用n 们。当社会学家建立一个准确一 致的社会网络模型之后，就可以通过逻辑推理的方式来研究社会的性质1 。 由于数据收集方式的限制，早期的社会网络局限于一个小的团体之内，往往 仅包含几十个结点。借助于图论和概率统计的知识，人工处理可以从中分析出一 些简单的性质和模式。但是，随着现代的通信技术的发展，越来越多的数据被收 集和整合在一起，建立一个大的社会网络成为可能。例如，可以通过电子邮件的 日志来建立使用者之间的联系网络，或者通过网络日志及网络通讯录等方式将用 户提交的联系人信息建立社会网络。所以，现在的社会网络规模比早期网络庞大， 通常包含几千或者几万的结点，甚至有多达百万个结点的网络。面对这样庞大复 4 杂的网络，简单的数学知识和原始的人工处理已经不可能进行有效的分析。 数据挖掘是从巨量数据中发现有效的、新颖的、潜在有用的并且最终可理解 的模式的非平凡过程。数据挖掘就是为了解决当今拥有大量数据，但缺乏有效分 析手段的困境而出现的研究领域。目前，已经在包括生物信息学，自然语言处理 等许多方面发挥了巨大的作用。 传统的数据挖掘采用“属性一值”的单表形式来表示数据。数据以向量的形 式表示，向量的每一维对应一种条件属性的取值。学习到的规则基于命题逻辑， 以析取或合取的方式表示为“如果- n 句型。社会网络数据是结构化的关系数 据，除了每个结点自身的属性之外，更重要的是结点之间的联系。这些联系之中 包含了很多信息。向量形式表示假设了结点间独立，忽略这些联系必然不能很好 地从中发现知识。因此，分析社会网络数据必须通过新发展起来的多关系数据挖 掘的方法来解决。 关系数据挖掘研究n 2 儿1 3 1 从包含多种对象并且对象间存在联系的数据中发现知 识的方法，并不首先将关系数据转化为原来的单表模式，而是直接在这样的数据 中挖掘关系模式。关系数据挖掘所对应的数据类型，更为符合一般的关系数据库 中的应用的数据。因而更能满足当前数据分析的要求，受到了数据挖掘研究者的 重视，许多有效的算法被提出。 社会网络分析是关系数据挖掘的主要应用n 制。关系数据挖掘的发展为社会网 络分析提供了更有力的工具，促进了社会网络分析的发展。 2 2 社会网络数据的特点和分析任务 在这一节中，我们首先介绍社会网络数据的表示，然后从数据挖掘的观点来 看待它具有怎样的特点，在挖掘过程中必须注意那些问题，最后结合实际应用对 主要的分析任务进行介绍。 2 2 1 社会网络的表示 数学是社会网络分析的不可缺少的工具，社会网络模型所需要的主要数学基 础是图论和概率统计。其中图论既为社会网络提供了合适的表示形式，也同时提 供了一系列形式化分析社会网络的概念。f r e e m a n 提出了社会网络分析必须具备的 四个特征n 引： 1 ) 社会网络分析更注重行动者( a c t o r ) 之间的联系，而不是行动者本身所具有 的性质； 5 2 ) 关于行动者之间联系( t i e ) 的数据必须通过系统化的方法收集； 3 ) 建立在图模型之上； 4 ) 使用数学和计算工具来从这些关系中获取有意义的信息。 从这里我们可以看到，社会网络采用图作为基本的表示n 。社会网络就是由 行动者和行动者之间的联系组成的，其中： 行动者( a c t o r ) ：社会实体，可以表示具体的个人，社团及其它集体社会单元。 联系( r e l a t i o nt i e ) ：不同的社会实体通过联系连接在一起。在不同的网络中， 其意义也不同。例如：一个人对另一个人的评价，物质资料在实体间的转移，实 体间的行为互动，两者的合作关系等等。 除了以上两种基本元素之外，由于社会学的关注角度和层次，还同时定义了 以下几个概念： 二元组( d y a d ) ：由两个行动者及他们之间的关系组成，这是研究关系模式的基 本单位； 三元( t r i a d ) ：由三个行动者及他们之间的关系组成； 子图( s u b g r o u p ) ：由网络中的一部分行动者和他们之间的关系组成，可以通过 子图来研究社会网络中的一个小团体所具有的特征； 图( g r a p h ) ：所有行动者及其之间的关系，分析社会网络的总体特征。 社会网络除了图模型表示之外，还有其社会学表示和代数形式的表示1 。因 为在数据挖掘中使用图的表示方式，这里仅介绍了图模型表示。 2 2 2 社会网络数据的特点 从上面描述的社会网络分析的特点中可以看出，社会网络数据是一种结构化 的关系数据。数据的信息不仅包含在行动者本身，大量的信息包含在行动者之间 的联系中。传统的数据挖掘的数据以向量的形式表示，向量的每一维对应一种条 件属性的取值。在挖掘的过程中，很多算法都是基于各个数据之间是独立的。社 会网络数据显然不满足这样的假设。因而，在对社会网络数据进行挖掘的过程中， 必须注意同时考虑行动者的属性及其于其它行动者之间的联系。 例如，预测一个人是否有吸烟的习惯，仅从这个人本身的状况出发，我们可 以得到一些分类的依据。对于两个状况基本相同的人，我们没有办法进一步地区 分。将两个人的朋友的状况也一起来分析，我们将得到更为精确的分类模型。因 为经验告诉我们，朋友通常具有相同的嗜好和习惯。如果一个人的朋友中大部分 人都吸烟，而另一个人的朋友中只有很少的人吸烟，这样，后者吸烟的概率将小 于前者。 6 社会网络数据中蕴涵了大量的联系信息，充分挖掘这些信息是数据挖掘的重 要目标。因而，我们不但不能简单地假设样本是独立的，还要充分利用这些联系 来建立更加准确的模型。 2 2 3 社会网络分析的任务 社会网络模型建立之后，可以从中分析出很多有用的信息。下面将按照对于 社会网络不同层次的观察角度对各种分析任务做一个简单的分类。 1 ) 行动者 根据行动者本身的一些属性以及其与网络中其它行动者之间的联系，来预测 该行动者的行为和属性。这类任务的应用比较广泛，比如商家可以通过这样的方 式来找到潜在的用户来有针对性地进行宣传；如果是关于流行病的传播网络，可 以找到哪些人属于易感人群，及早采取合适的预防措施。 对于行动者在网络中重要程度的排序。最有价值的用户n 町对于商家具有不可 忽视的地位，给予他们特别的照顾往往能够取得巨大的受益。显然，通过将客户 按照重要程度排序，提供不同的服务，才能够使得商家取得最大的经济利益。 行动者辨别( a c t o ri d e n t i f i c a t i o n ) 是判断网络中的不同结点表示的行动者是否 代表同一个行动者。例如在个人信息管理中，识别出一组信息的不同形式的表示 是否实际上指向同一个人。 行动者聚类( a c t o rc l u s t e r i n g ) 是指根据行动者本身的性质及他们同其他行动 者之间的联系，将行动者分为若干个不同的类别。在同一个类别当中的行动者具 有相似的特征，而不同类别当中的行动者应当具有一定的差异。这个在社学会的 研究中有着非常重要的作用，能够用于发现不同的社会阶层。 2 1 联系 基于行动者的属性以及网络中已观察到的行动者之间的联系，来预测行动者 之间是否存在这样的联系是社会网络的一个主要任务。如判断两者是否是朋友， 两者是否会共同参与同一项活动等等。 另外，当已知两者之间存在联系，但是不确定是存在哪一种联系时，根据网 络中已有的信息来预测这个关系的类型也十分有必要。例如在一个公司内部的社 会网络中，将彼此能够有效合作的员工放在同一个项目组中有利于工作的顺利进 行。 3 ) 子图 从社会网络中找出一些频繁出现的或者特别的子图也是一个重要的分析任 务。频繁的子图往往代表了社会网络中频繁出现的模式，分析这些子图能够加深 7 对社会关系的理解。而另外一些特别的子图可能表征不同社会网络的特点，发现 它们对于社会网络的分类有很大帮助。 4 ) 图 对于整个社会网络进行挖掘，找出社会网络所呈现出的一些性质，也有是对 于整个网络是否具有某种性质做出一个判断。例如发现一个人最多通过六个人的 中转可以联系到世界上其他的任何一个人。还有，对多个不同团体的社会网络如 何准确地做出分类，例如从正常的公司的社会网络关系中发现恐怖组织所具有的 模式对于打击恐怖组织很有帮助。 2 3 社会网络分析在数据挖掘中的应用 链接挖掘包括了很广泛的任务n 钉，主要可以分为六种，具体如表2 1 所示。 表2 i 常见的链接挖掘任务及其分类 t a b l e 2 1t h ec o m m o nt a s ko fl i n km i n i n ga n dc l a s s i f i c a t i o n 基于链接的节点排序( 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 i l l ( p 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 ) 基于链接的节点排序是社会网络分析中一个核心分析任务，它的目的是通过 分析利用图中的链接结构，根据某种衡量节点重要性的度量来对图中节点进行排 序。 传统机器学习中的分类问题是基于数据实例( 节点) 是独立同分布的假设，然 而很多现实问题不满足这个假设。在基于链接的节点分类问题中，一个数据图伊似 剀表示了节点集合d 和他们之间的链接集乱，我们的任务是将d 中的成员赋予某一 类标签。基于链接的节点分类与传统分类问题的最显著的不同在于节点的类别是 彼此相关的。如何设计合理的分类算法能有效地利用这些相关信息是研究者所面 临的挑战。基于链接的节点分类与传统分类问题的最显著的不同在于节点的类别 是彼此相关的。 节点聚类又称为群体检n ( g r o u pd e t e c t i o n ) ，它的目的是将有着共同的特征的 节点聚类。首先假设图中的节点和链接都属于同一种类。在这种假定下，群体检 测的技术可以分成聚合聚类和分裂聚类两种。社会网络分析中块建模( b l o c k m o d e l i n g ) 的任务是将社会网络分割成个体的集合，这种集合称为位置( p o s i t i o n ) ， 显示了在网络中相似链接的集合。 链接预测是基于它所链接的节点属性和已观测到的链接来预测某链接是否存 在。链接预测的应用非常广泛，包括预测社会中人与人之间的朋友关系，电子邮 件、电话联系，合作关系等。往往一些链接被观察到，未被观察到的需要我们去 推测；或者存在一个时间序列，在某个时间点芒的连接状态已知，要预测什l 时间 点的链接状态。 不同于基于链接的节点分类，图分类是一种试图将整张图用正或负标签来分 类的监督学习问题。这是最早的将机器学习和数据挖掘技术应用与图数据的任务。 图分类一般不要求像节点、边分类中要求的集体推断。这是因为图一般是假设独 立的。三种主要方法有：基于图上特征挖掘，归纳逻辑编程( i l p ) 和定义图核函 数。 此外，还有一些其它的研究热点和方向，从总体上讨论如下。 1 ) 数据挖掘在建立社会网络中的应用 互联网的发展使得人们联系地更加紧密，而网上的交流也成为人们互相交流 的重要方式。同时，网络上的交流，例如电子邮件和聊天室等，都有适当的日志 信息，十分便于信息的收集。从这些交流方式中来建立社会网络将极大地丰富社 会网络研究的数据。 但是，这样的网络往往包含大量的结点，其日志信息也包含多方面的来源， 如何从中抽取出合适的表示，建立出社会网络模型是一个重要的研究课题，近年 来有一些工作就是围绕这个方向展开n 铂n 引。 2 ) 社会网络的方法并不仅限于挖掘社会学领域的问题 社会网络模型采用了网络模型。其实很多关系复杂的数据都可以采用网络模 型，比如互联网上的网页与它们之间的链接；生物信息学中各个分子与它们之间 相互作用。例如，搜索引擎中使用对页面的排序算法p a g er a n k ，也是在同样的网 络模型上进行的。和社会网络中的对象排序属于同一种任务。 从数据挖掘的角度看，社会网络模型是一种网络模型。虽然它有着自身的特 点，但是用来分析它的很多方法可以应用在其它领域的数据上面；同时，其它问 题的解决方案也可以通过适当修改应用在社会网络分析中。因而，关注在数据挖 掘在不同领域中应用，既有助于发现新的数据挖掘问题，也有利于将某个方面取 得的成果转化到其它领域之中。 3 ) 社会网络挖掘可以帮助其它数据挖掘应用 电子邮件日益成为人们交流的一个重要手段，有些人每天需要较多的时间来 处理各种邮件。垃圾邮件的泛滥加重了人们的负担，浪费了宝贵的时间。因此， 自动识别出垃圾邮件一直是数据挖掘的一个重要应用。简单凭借邮件本身的内容 9 无法进行高精确度的分类。于是，有的方法尝试通过分析由电子邮件日志建立起 来的社会网络，来帮助识别出哪些邮件是垃圾邮件。由于考虑了客户的社交圈子， 能够更加准确地进行分类。同样，社会网络分析可以为其它需要考虑社会实体之 间联系的应用提供信息和帮助。 2 4 社会网络数据的知识发现系统体系结构 本小节我们将主要介绍一个社会网络数据集的知识发现系统的体系结构设 计。该系统的设计初衷是设计一个通用的社会网络数据集的数据挖掘系统，可适 用于各种社会网络数据的知识发现，包括电信通话数据，e m a i l 通信数据等各种通 信数据集。在文献【冽中，详细的介绍了系统的整体设计工作。 2 4 1 设计目标 该系统的设计思想是结合社会网络分析的方法对各种社会网络数据集进行知 识发现，在该平台上，不但可以验证各种社会网络分析算法，而且可以很容易的 扩展成为具有实际价值的应用系统。从用户的角度出发，他们希望从抽象的数据 集中获取有价值的信息和形象化的结果展示。因此，该系统从设计的角度，提出 以下目标： 1 ) 有效集成社会网络分析方法； 2 ) 注重通用性与普适性，可以对不同形式的交往数据集进行分析； 3 ) 良好的扩展接口，便于增加新的功能； 4 ) 操作方便、界面友好； 5 ) 能够帮助用户找到关键个体或者发现小团体，提供有价值的参考信息； 回附加统计分析等传统方法，提供多样化的结果展示。 2 4 2 总体架构 根据社会网络数据的特点和社会网络分析需求，该系统将整个社会网络数据 集的知识发现系统分为如图2 1 所示的四个层次，包括数据预处理、数据本地化、 数据分析和数据展示。 在数据预处理中，该部分根据不同的应用需求定制，在多维分析中的基本事 实表和维表的概念指导下，将细粒度级的记录表统计成粗粒度级易于分析的基于 维的事实表，以供进一步使用。数据预处理完成后，系统将根据用户的设定建立 本地模型，将用户所关心的数据取到本地来。接下来将运用社会网络分析的各种 方法对多维空间中的关系数据进行研究，最终将分析结果通过某种可视化方法展 现在用户面前，为应用提供决策支持。系统的模块如图2 2 所示： 图2 1 社会网络数据集的知识发现系统框架图 f i g u r e2 1t h ef r a m e w o r ko f c o m m u n i c a t i o n d a t a s e tk n o w l e d g ed i s c o v e r y 图2 2 系统模块图 f i g u r e2 2t h em o d u l eo f p r o t o t y p es y s t e m 其中，通用类库定义了系统内部需要处理的各种类型并提供了调用接口，如 社会、组织等。通用显示窗体动态链接库实现了可调整的窗口控件类，用于作为 显示容器。通用画图空间动态链接库则实现了个体、关系等的画图功能，用于数 据展示层的调用。主程序中则涵盖了系统中的众多功能，其模块组成图如图2 3 所 示。 图2 3 主程序功能模块图 f i g u r e2 3f u n c t i o nm o d u l e so fm a i np r o g r a m 对社会、组织、图的描述如下： 社会( s o c i e t y ) ：将从数据源获取的交往数据集形象化为“个体”与“关系 形 成的社会，社会就是一个集合了原始数据集并对其进行封装转化成本地数据集的 容器。 组织( c r o u p ) ：在社会中抽取出来的一个子集，其所涉及的个体集是社会中个 体集的子集。 图( g r a p h ) ：在指定维度下从组织中抽取出来的一个分析层，在该层上，个体 转化为图中的点，可以综合运用社会网络分析方法进行分析。 2 5 小结 社会网络分析是一种应用性很强的社会学研究手段，能够用来描述社会具有 的性质，也能够解决许多实际问题。社会网络数据的大量收集，既给该领域带了 前所未有的机会，也同时对数据分析技术提出了巨大的挑战。数据挖掘作为一种 帮助人们从大量数据中发现有用的知识的工具，经过不断地发展，已经能够处理 像社会网络这种结构化的网络数据。因而，采用数据挖掘技术作为社会网络分析 的手段对于两个领域的发展都有益处。 社会网络采用了图模型作为表示形式，数据具有结构化的特征，并且强调行 动者之间的联系比行动者本身的性质更具有价值。因而，必须采用关系数据挖掘 1 2 的方法，充分考虑联系的重要作用，才能够很好地完成分析任务。 本章主要介绍了社会网络分析的概念、社会网络数据的特点和分析任务、数 据挖掘和社会网络分析相关的研究方向和应用。除了本章所介绍的用于社会网络 分析的许多应用之外，社会网络分析也可以有助于完成一些其它数据挖掘应用。 加强社会网络分析在不同学科研究领域之间的交流，对数据挖掘和各个领域的发 展都十分有利。 3e m a i l 社会网络社群挖掘的数学模型和算法 在本章中，在3 1 节我们首先将介绍广义的社群概念，之后介绍社会网络分析 中凝聚子群的概念，最后提出e m a i l 社会网络中基于基于连接特性的社群定义；在 3 2 节我们对传统的社群挖掘算法以及相关扩展问题作了分类介绍；在3 3 节介绍 基于连接特性的e m a i l 社会网络社群挖掘算法，该算法包括三个主要组成部分：社 群种子成员选取、社会s 的生成以及社群成员的生成；最后，在3 4 节对本章内容 进行总结。 3 1 社群的定义 3 1 1 广义的社群概念 社会是指个体以及个体之间关系的集合。从广义上来讲，社群是社会的一个 子集，该子集成员的属性具有某种相似特点或者成员之间满足某种特定的关系【l 】， 可以用形式化的语言描述如下。 定义3 1 社会s o c i e t y ( 巧目表示个体集合矿以及个体之间的关系集合e ，社群 定义为社会的一个子集，该子集成员的属性具有某种相似的特点或者成员之间满 足某种特定的关系。社群可以表示为三元组c o m m u n i l y = 2 时很难给出n 派系的社会 学的解释，其次是n 派系作为一个子图当某些边被去掉之后其直径可能比n 还大， 最后是一个n - 派系可能会是一个不关联图f 8 1 。 图3 3 规模为4 的n 派系 f i g u r e 3 3n - c l i q u e so f 4n o d e s 3 ) n 宗派 n 一宗派( n - c l a n ) 也是建立在距离基础上的凝聚子群，它是指任何两点之间在子 图中的距离最大不超过n 的子图。如图3 4 所示，为2 宗派。 图3 4 规模为5 的2 - 宗派 f i g u r e 3 42 - c l a n so f 5n o d e s n 宗派的概念比n - 派系要严格，也更加具有实际意义，因为它克服了n 一派系 在应用方面的后两个局限性，但是当n 2 时，我们仍然难以给出n 宗派的社会学 解释【8 1 。 4 ) k 一丛 k - 丛( 1 ( p l e x ) 是建立在点度基础上的凝聚子群，它是指满足如下条件的子图， 即该子图中任何一点都至少与子图中除了k 个点之外的其他所有点直接相连。也 就是说，如果一个凝聚子群的规模为n ，那么只有当其所有点的度数都不小于n - k 时，该凝聚子群才是一个k 丛【8 1 。如图3 5 所示，为一个3 丛。 在e m a i l 社会网络中，如果有5 个人a 、b 、c 、d 、e ，那么只有当每个人都跟 其它2 个人有过通信时，这5 个人是一个3 丛。k 丛在一定程度上反映了群体中个 人与其它人联系的紧密程度。 5 ) k 核 1 6 k 核( 1 【一c o r e ) 是指满足如下条件的子图，即该子图中任何一点都至少与子图中 的k 个点直接相连。也就是说，k 核中任何一点的度数都不小于k 【8 1 。图3 5 所示 也是一个3 核。 图3 53 丛 f i g u r e 3 53 - p l e x 3 1 3 基于连接特性的社群 社会网络分析中定义了多个凝聚子群( 详见第3 1 2 节) 的概念，下面我们将分 析用这些概念来定义e m a i l 社会网络的社群从而进行社群挖掘的可行性。 派系是指一个图中至少包含三个节点的最大完备子图；n 派系是指任何两个节 点之间在总图中的距离最大不超过n 的子图；1 1 宗派是指任何两点之间在子图中的 距离最大不超过n 的子图；k 丛是指子图中任何一点都至少与本子图中除了k 个点 之外的其它所有点直接相连的子图；k 一核是指子图中任何一点都至少与子图中的k 个点直接相连的子图。 在社会网络分析中所定义的这些凝聚子群都比较直观，计算也相对容易，但 是如果以这些凝聚子群的概念来定义e m a i l 社会网络中的社群，社群的挖掘结果是 不太理想的，因为最大的问题在于这些定义过于严格，并且这些定义的现实社会 意义不大，所以我们应该探求新的概念从而重新定义e m a i l 社会网络中的社群，进 而进行挖掘。 在w e b 社群挖掘文献h 1 中，w e b 社群定义为w e b 页的集合，相比于社群外的w e b 页，这些w e b 页面对社群中的页面有更多的链接。这个定义描述了社会网络中社群 成员在连接关系上的一个特性，即社群中的成员总是倾向于更多的与社群内部的 成员发生联系，反映了社会中“物以类聚，人以群分 的特点。在e m a i l 社会网络 1 7 中，该特点也是比较明显的，因此，根据该特点形式化的给出e m a i l 社会网络社群 的定义是合理的，但是单纯的以社群内链接数量和社群外的链接数量大小关系判 断个体是否为社群成员，有一定的缺点，主要是参数不够灵活，不能够通过调节 参数控制判断个体是否社群成员的尺度。所以，本文对该定义进行了一定修改。 定义3 2s e e d 表示一个节点集合，e m a i l 社会网络中的社会s ( s e e d ，刀) 定义为 从s e e d 出发，在e m a i l 通信记录集广度优先扩展，l 层生成的个体集合以及个体之 间的通信关系集合。 定义3 3 在e m a i l 社会网络中的社会s 中，个体v 与社群c 联系的相关度表示 个体1 ，与社群c 联系的紧密程度，定义为a ( v ，c , s ) = l i n k i l i n k a u ，l i n k i t l 定义为个体 y 和社群c 中个体的连接数量，砌舷。定义为个体和社会s 中所有个体的连接数量。 如图3 6 所示，社群包括a 、b 两个成员，与社群成员的相关度为口= 2 5 = 0 4 。 参数口是一个0 到1 之间的实数，其值越小，说明个体和社群的相关性越低， 个体属于社群成员的概率比较小，如果其值越大，那么个体和社群的相关性越高， 个体很可能属于这个社群的成员。 引入参数口不仅能够客观的反映个体和社群的联系程度，在进行社群挖掘的 时候，也可以很容易的通过参数口的调整来控制判断个体是否社群成员的尺度。 图3 6 个体v 与社群的相关度 f i g u r e3 6r e l e v a n c eo f a c t o ra n dc o m m u n i t y 定义3 4e m a i l 社会网络中基于连接特性的社群是社会s 的子集c c s ，对于 个体v e s - c ，如果满足条件口( 1 ，c ，s ) 0 ，0 定义为个体与社群c 的最小相关度， 那么y c 。 这样，有了e m a i l 社会网络社群的形式化定义，我们首先选取一组社群的种子 成员c ，扩展一定的层数，生成社会s ，之后在集合争c 中，选取个体，如果满 足a ( v ，c ，s ) 0 ，那么个体v c ，通过这样的方法不断扩展社群c 的个体集合， 可以得到最终的社群成员个体集合。在3 3 节我们介绍基于连接特性的e m a i l 社会 网络社群挖掘算法。 1 8 3 2 传统的社群挖掘算法介绍 传统的社群挖掘算法大多都是基于数据挖掘中聚类的思想，将社会网络中具 有某些共同特征的对象聚类到一起，形成一些具有现实意义的社群结构。总体可 以分为图分割法和g n 算法两类。本节主要对这两类方法进行分类介绍。我们将 在3 2 3 节对相关扩展问题及其进展进行一定的介绍。 3 2 1图分割法 计算机科学中一个经典问题是如何