《EMAIL社会网络的社群挖掘和分析算法研究》由会员分享，可在线阅读，更多相关《EMAIL社会网络的社群挖掘和分析算法研究（50页珍藏版）》请在金锄头文库上搜索。
1、北京交通大学硕士学位论文Email社会网络的社群挖掘和分析算法研究姓名：尹盛申请学位级别：硕士专业：计算机应用技术指导教师：林友芳20080701A BS T R A C TW 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 ei 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
2、u n i c a t i o n sb e t w e e np 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 eas 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 eo fi t sm e m b e
3、 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 gc 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 we 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
4、 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 yo 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 sa 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
5、 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 om 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 ft 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
6、 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 do 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
7、 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 ka 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 ym i n i n ga n dt h ee v
8、 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 sa 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 kM 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
9、nE - m a i lD a t a s e tC I A S S N O ：T P 】8 2学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：夕蓥导师签名：签字日期：2 z , - o3 年7 月少E t辩醐洲年7 月7 日独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特
10、别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日1 引言通信技术和互联网技术的发展引发了新的网络生活形态，越来越多的虚拟社会呈现在人们面前，比如E m a i l 通信形成的人际关系网络、互联网上形成的虚拟社区等，透过这些网络来得到现实社会的一些结构特点和规律成为近来的研究热点之一。本章从总体上介绍了选题的背景和意义、当前的研究现状、本文主要研究的内容以及论文的章节组织结构。1 1 研究的背景
11、和意义社会网络分析由于其巨大的应用价值成为近年来数据挖掘热门的课题之一，受到了越来越多研究人员的关注。社会网络是指由个体以及个体之间的关系构成的满足社会结构特点的网络，社会中人与人交往关系构成的网络，国家之间的贸易网络，网页链接关系构成的网络，电信通话网络，生物以及计算机病毒传播网络，文献引用关系构成的网络等等都是典型的社会网络。从数据挖掘的角度来看，社会网络是由图表示的异构多重关系的数据集合，节点表示对象，边表示对象之间的关系。社群是社会网络中一组具有相同属性的个体集合。在各种社会网络中挖掘社群具有重要的研究价值和意义。例如，从互联网上进行W e b 社群挖掘，可以找出相同主题的W e b
12、网站，建立面向主题的搜索引擎，为用户提供更好的导航服务；从科学文献引用数据集中进行社群挖掘，可以帮助研究人员找出相同研究领域的文献等。其中，在E m a i l 通信数据集上进行社群挖掘并且评价社群成员在社群中的重要程度是一个重要而又意义的研究课题。在各种著名大型网络公司，如网易、新浪、G o o g l e 等公司，都提供了免费邮箱服务，这些服务所积累的数亿网民的E m a i l通信记录，具有许多潜在用途。例如，对于执法机关而言，在这些数据中发现犯罪或者恐怖团伙、欺诈团伙并且分析这些团伙的层次结构，挖掘出其中的核心首领对于打击犯罪和恐怖活动具有重大的研究意义，可以极大的提高执法效率。因此，
13、在该背景下本论文对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 教授的研究
14、工作集中在异构多重关系社会网络的社群挖掘【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 。在社群分析方面，在社会网络分析中
15、有很多相关的研究工作，主要集中在中心性分析【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 通信记录数据
16、的研究和利用存在很多和个人隐私相关的问题，因此，在法律上可能并不允许针对数亿网民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 进行社群挖掘和社群分析的实验以验
