（计算机应用技术专业论文）基于sna的网络核心及社团结构挖掘研究.pdf

摘要 摘要 社会网络指的是社会行动者及其问的关系集合。也可以说一个社会网络是由多个点 ( 社会行动者) 和各点之问的连线( 行动者之间的联系) 组成的集合。因此社会网络分析不 同于单个的语义分析，是注重于关系数据的分析。 本文主要围绕应用于网络信息安全的社会网络分析法这一方向展开，研究了基于邮 件的社会网络分析，在广泛阅读了国内外文献的基础之上提出了一种基于邮件挖掘社会 网络核心层的新方法，本文的主要工作主要有以下两个方面： ( 1 ) 为了挖掘出完整的社会网络核心层的成员，提出了基于邮件挖掘社会网络核心层 的新方法。在用邮件数据构建出了社会网络之后，首先删除节点度小于一定阈值的节点， 再运用社团结构挖掘及中心度分析找出部分网络核心成员，最后结合已删除的节点得出 完整的网络核心层。实验结果显示，该方法可以找出全部的网络核心成员，且在一定程 度上解决了大型网络不容易计算的问题。 ( 2 ) 为了更精确的评价社团结构，本文提出了一种新的评价标准社团凝聚度，定 义社团外部链接数与内部连接数的比值为社团凝聚度，并在此基础上提出了基于局部社 团凝聚度增量的社团结构挖掘算法。首先选择初始节点定义为一个社团，然后比较网络 中每个节点加入到社团后的凝聚度增量，选择局部社团凝聚度增量增长最快或者减少最 慢的节点作为社团成员加入，重复选择合适节点加入社团直到社团凝聚度达到指定阈 值，或者发现完全封闭的社团。最后比较挖掘出社团的凝聚度可以确定哪些为社团，哪 些则可以作为孤立点。 针对本文提出的算法编写程序，应用于计算机生成网络和一个虚拟企业网络，实验 结果表明算法是高效的和实用的。 关键词：社会网络；社团结构；核心层；凝聚度 人造交通人。i ：学硕p 何论文 a b s t r a c t s o c i a ln e t w o r kr e f e r st ot h ea c t o r sa n dt h es o c i a lr e l a t i o n s h i pb e t w e e na c t o r s t h a ti st o s a yt h a tas o c i a ln e t w o r ki sas e tc o m p o s e do fan u m b e ro fp o i n t s ( s o c i a la c t o r s ) a n dt h e c o n n e c t i o nb e t w e e np o i n t s ( t h el i n kb e t w e e na c t o r s ) t h e r e f o r e ，s o c i a ln e t w o r ka n a l y s i si s d i f f e r e n tf r o mas i n g l es e m a n t i ca n a l y s i si st of o c u so nt h er e l a t i o n a ld a t aa n a l y s i s t h i sa r t i c l ea p p l i e st on e t w o r ki n f o r m a t i o ns e c u r i t ya r o u n dt h es o c i a ln e t w o r ka n a l y s i s s t a r t e di nt h i sd i r e c t i o n t h i sp a p e rs t u d i e st h es o c i a ln e t w o r ka n a l y s i sb a s e do ne - m a i l i nt h i s p a p e r , e x t e n s i v er e a d i n ga th o m ea n da b r o a db a s e do nt h el i t e r a t u r ep r e s e n t sas o c i a ln e t w o r k b a s e do ne x c a v a t i o ne - m a i ln e wm e t h o df o rt h ec o r el a y e r t h ei n n o v a t i o no ft h i sp a p e r m a i n l yi nt h ef o l l o w i n gt w oa s p e c t s ： ( 1 ) i no r d e rt ot a pt h ec o r eo fc o m p l e t es o c i a ln e t w o r kl a y e rm e m b e r s ，t h i sp a p e r , m i n i n g s o c i a ln e t w o r k sb a s e do ne - m a i ln e wm e t h o df o rt h ec o r el a y e r u s i n ge s t n a i lt h ed a t at ob u i l d o u tas o c i a ln e t w o r k ，t h ef i r s td e l e t et h en o d ei sl e s st h a nac e r t a i nt h r e s h o l dv a l u eo ft h en o d e ， t h e nt h eu s eo fc o m m u n i t ys t r u c t u r em i n i n ga n da n a l y s i sc e n t e r , p a r to ft h en e t w o r kt o i d e n t i f yt h ec o r em e m b e r so ft h ed e l e t e dn o d el a s t ，c o m et oac o m p l e t en e t w o r ko fc o r el a y e r e x p e r i m e n t a lr e s u l t ss h o wt h a t t h i sm e t h o dc a ni d e n t i f ya l lo ft h ec o r em e m b e r so ft h e n e t w o r k ，b u ta l s ot os o m ee x t e n ti sn o te a s yt os o l v el a r g e s c a l en e t w o r kc o m p u t i n gp r o b l e m s ( 2 ) i no r d e rt om o r ep r e c i s e l ye v a l u a t et h ed e g r e eo fp o l y m e r i z a t i o na s s o c i a t i o n s p r o p o s e di n t h i sp a p e rb a s e do nt h ed e g r e eo fc o m m u n i t yc o h e s i o no ft h ec o m m u n i t y s t r u c t u r eo fi n c r e m e n t a lm i n i n ga l g o r i t h m t h ed e f i n i t i o no fc o m m u n i t ye x t e r n a lw e bl i n k c o u n t sa n di n t e r n a lc o n n e c t i o n sf o rt h ec o m m u n i t yc o h e s i o nr a t i oo ft h en u m b e ro fd e g r e e s ， f i r s ts e l e c tt h ei n i t i a ln o d ei sd e f i n e da sas o c i e t y , a n dt h e nc o m p a r et h en e t w o r ke a c hn o d e a d d e dt ot h ed e g r e eo fc o m m u n i t yc o h e s i o na f t e rt h ei n c r e m e n t ，s e l e c tl o c a lc o m m u n i t y c o h e s i o nd e g r e ei n c r e m e n t su pt ot h ef a s t e s to rt h es l o w e s tn o d et or e d u c ec o m m u n i t y m e m b e r sa sar e p e a ts e l e c t i o nt of i n dt h es m a l l e s tn o d ej o i nt h ec o m m u n i t yu n t i lt h es p e c i f i e d n u m b e ro fm e m b e r so ft h ec o m m u n i t y , o rf i n dc o m p l e t e l yc l o s e ds o c i e t i e s c o m p a r i n gt h e f i n a le x c a v a t e dt od e t e r m i n ew h a td e g r e eo fc o m m u n i t yc o h e s i o na sas o c i e t y , a n dw h i c hc a n b ea si s o l a t e dp o i n t s t h i sp a p e rp r e s e n t sa na l g o r i t h mf o r p r o g r a m m i n ga p p l i e d t oc o m p u t e rg e n e r a t e d n e t w o r k sa n dav i r t u a le n t e r p r i s en e t w o r k ，e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi s c f f i c i e n ta n dp r a c t i c a l k e yw o r d s ：s o c i a ln e t w o r k ；c o m m u n i t ys t r u c t u r e ：c o r el a y e r ：d e g r e e o fc o h e s i o n i i 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太蓬塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名： 矽翻p 嗡 日期：年月 日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太整銮通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太蓬塞通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整壅通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太董塞通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：匀身毯叩，去 日期：年月 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱： 导师签名：砩 日期：年月 日 电话： 邮编： 第一章绪论 1 1 研究背景和意义 国际互联网i n t e r n e t 的发展和普及，使人类出现了一种新的生存状态和存在方式， 同时也构建了一种新型的网络互动方式和新型的网络社会。它具有i n t e r n e t 的丌放性及 信息的迅速扩散性，除了j 下常信息外，还随时可能出现不良信息，政治谣言、犯罪、恐 怖、暴力、色情、民族情绪等，还有一些则涉及到商业、企业与经济信息安全等问题。 这种具有全球性、传染性、信息爆炸等特点的新型信息社会，任何对信息内容监管的疏 忽都可能导致国家乃至社会的不安定，中国工程院院士何德全在谈到网络信息安全时指 出“没有信息安全，就没有完全意义上的国家安全，也没有真正的政治安全 。国家信 息化领导小组第二次会议上提出要“全面强化管理，建立健全信息安全保障体系和防范 机制”。这些都说明信息安全越来越受到我们国家政府和各界人士的重视。 我国在信息内容监控方面走在世界的前沿，从互联网建立开始，我国政府就对信息 内容监控高度重视。早在2 0 0 2 年国家8 6 3 项目中专题二、信息安全综合防御关键技术 中出现有这样一个专题：网络信息内容分析与监控技术( z t 0 2 0 3 ) ，研究“对网络中传输 的特定信息进行智能分析、识别的技术和方法 ，其中主要研究内容有“智能化网络内 容分析监控技术，主要针对因特网中特定内容的自动检索和分析，包括基于语义的快速 识别，高效多关键字扫描过滤算法、内容分析的高速实现”( 2 0 0 3 年1 2 月) 。在中科院 计算技术研究所的一系列科研项目中，其“网络信息安全攻防技术”项目中已经明确的 把内容安全分析列为一个重要的课题：“内容安全分析及保障技术研究 。基于以上研 究国内已经开发出了一系列的监测分析系统。这些监控系统能把大量网络信息忠实的记 录下来，着重强调信息安全过滤的方法研究，但还不能从多重关联的角度向管理决策人 员提供有害文本与人员、单位或地区等其他关系数据因素之间的联系，以及有害人物可 能在不同组织机构中的特别意义及特定动向。 这些安全过滤的方法对于监控公共信息网络，防止传播反动言论和有害信息，防止 被敌对势力进行信息渗透，发挥着重要作用。然而信息内容安全监测的研究已经不仅仅 驻足于安全过滤领域。 这方面最显著的例子是9 1 1 恐怖袭击事件。美国有遍布世界的信息内容监控网络， 对流经各主干通讯节点的敏感内容都能即时做出判断与反应，却仍然没能发现恐怖分子 的真实意图。调查结果显示，袭击策划组织中产生的部分可疑片段已经在数据库中，调 查人员想要任何一个恐怖分子的近期情况及其与其它成员间的联络信息内容都没有问 人连交通人：i 硕 ：何论文 题，关键是分析人员没能从全局着眼把各个成员的合法活动关联起来调垒。这说明，仅 仅实现对单个信息流的语义理解是很不够的，还要能把表而上毫无联系的信息内容关联 起来，发现和理解新的信息内容和以前获取的信息内容之阳j 的重要联系，辅助分析人员 从更高的层次上理解它们的真正含义。 社会网络分析法( s o c i a ln e t w o r ka n a l y s i s ，s n a ) 是能强化内容安全关联分析的重要 方法之一，其目的是通过正确判读社会网络组织，加强对内容预测的能力，以协助在社 会网络组织内对个人或组织的行为及决策的预测。社会网络分析主要是研究社会实体间 的关系连结以及这些连结关系的模式、结构与功能，同时也可用来探讨社群中个体间的 关系以及由个体间关系所形成的结构及其意义。换言之，社会网络分析的主要目标是从 社会网络的潜在结构( 1 a t e n ts t r u c t u r e ) 中，分析发掘其中团体之间的关系动态。 在研究信息安全与警觉( a w a r e n e s s ) 方面，社会网络分析( s n a ：s o c i a ln e t w o r k a n a l y s i s ) 以及连接分析( l i n ka n a l y s i s ) ，受到美国国家科学基金会( n s f ) ，美国国防部 ( o o o ) 、国防高级研究项目署( d a r p a ) 和中央情报局( c i a ) ，美国海军部，以及多个重要 研究机构的大力扶持。众多的研究机构投入其中并成立了专门的研究工作联盟。说明这 项研究受重视的程度和重要性。 冷战时，连接分析技术被c i a 用于对东部的外交官和潜在的间谍网进行跟踪。结束 后，英国的m 1 5 用他们称为的m o v e m e n t sa n a l y s i s 技术来对付i r a ( 爱尔兰共和军) 。它 包括一套数据采集系统和一套统计分析系统来分辨某个人在网络中的位置和他们的主 要作用。 然而目前的社会网络分析法应用于内容安全关联分析的研究还不成熟，还有很大的 局限性，该研究领域具有的挑战性如下： ( ，1 ) j t l 何从海量的信息中详察筛选出少量的能够指示危险性活动的子图，以及这些子 图之间的联系，互联网上有些活动被认为是可疑的，往往不是由单个对象的个性决定的， 而是由众多对象相互作用引起的，而且安全问题是由有威胁的和无害的活动交织在一起 的。目前分析人员尚缺乏有力的工具从看似无关的大量信息中去定位那些相对稀少的、 有关联的信息，以便预防、探测和响应。 ( 2 ) 人类的活动以至于人际间的交流具有内容和层次上的多元性和复杂性。我们要做 的就是发现这些多层次或多元迭加交错的网络关系，并利用一种更好的可视化表现形 式，揭示社群中每一个特定的领域内的关系网络自身的结构特性，以及不同领域的社群 结构对网络整体结构的影响。 2 绪沦 1 2 国内外研究现状 社会网络分析专注的分析对象是网络结构。在文献调研中发现，在当代科学分类体 系中这种侧重于连接结构分析研究的领域主要有以下几个：一个是社会学中的社会网络 分析；一个是人工智能领域的l i n ka n a l y s i s ；一个是数据挖掘中的l i n kd i s c o v e r y ；数学学 科的图论是它们共同的基础之一。当然还有经济统计领域和医学领域在该方面的研究。 而这几个领域因研究方向侧重点不同，主要解决的问题不同，方法各有所长，所以往往 互相借鉴。社会网络分析在众多领域有着广泛的应用，而我们则着眼于信息安全领域的 社会网络分析研究。社会网络分析模型早在2 0 世纪9 0 年代就已经被一些国家应用在 e m a i l 安全领域，而在国内则刚开始起步，主要在一些既定的事实上作分析，对于决策 的支持则比较少。 1 2 1 国外研究 社会网络分析在信息内容安全过滤方面的应用最早可以追溯到1 9 8 2 年d e n n i n g 首 先提出“信息过滤”的概念，其过滤目的在于拓宽传统的信息生成与信息收集的讨论范 围。他描述了一个信息需求的例子：对于实时的电子邮件，利用过滤机制，识别出紧急 的邮件和一般例行的邮件，主要通过一个“内容过滤器来实现过滤，提出了个基于 社会网络分析的电子邮件过滤方法，查全率和查准率得到有效的改善。 随着互联网技术的快速发展，信息过滤的研究也进入了一个新的阶段，出现了许多 新的内容安全过滤系统，主要有：s i t e s c o p e 是一个u r l 内容监控器，用来发现用户访 问特定u r l 的内容，写入日志。o l s 系统主要用于学校判断学生的邮件是否健康，健 康则放行，否则删除或不发送给学生本人。m a i l c e n s o r 是一个完全的实时邮件检查和监 控软件。可疑邮件将被纪录在数据库中。其目的是防止公司保密信息泄漏，过滤有害信 息( 例如色情信息) 和不适宜的信息。s o n i c w a l l 内容过滤允许各种组织维护适合自己需 求的i n t e r n e t 访问策略，它支持u r l 过滤，关键词过滤和c o o k i e 、j a v a 、a c t i v e x 阻 塞。c y b e r s i t t e r 是一个主要用于家庭、教育、小企业使用的网站过滤软件。 1 9 9 8 年，俄罗斯的f s b 内务部( 前身是苏联k g b 的国内主要董事会) 发布了s o r m 工程【1 1 。这个工程计划实时监控俄罗斯的互联网，包括每一封电子邮件消息。所有互联 网服务接入商都必须在他们的设备中安装监控设备，并与f s b 的互联网控制中心建立高 速数据连接。尽管对公众私人邮件的内容监听是有法律限制的，但这种交流结构的隐私 却不受法律保护。这套系统能很好完成任务而不必对加密邮件进行复杂的解密工作。 n s f 支持的r p i ( r e n s s e l a e rp o l y t e c h n i ci n s t i t u t e ) 计算机科学部p e t r o sd r i n e a s ， m u k k a is k r i s h n a m o o n h y ，m i c h a e ld ，s o f k a 在缺失语义信息的情况下对电子邮件情报进 3 人迮瓮通人- j j i j 硕p ：o 伊论艾 行检测和分析研究( 项目编号# 0 3 2 4 9 4 7 ) 。他们提出了一系列方法用j ：以电二子邮件为基础 的组织结构和交流模式的识别。如通过电子邮件关联图的邻接矩阵和低秩矩阵1 2 j 进行交 流模式的识别。 1 2 2 国内研究 由于社会网络分析本身在国内的研究仍处于起步阶段，所以用于安全领域的成果比 较少，主要集中在社团挖掘方法研究和对于邮件和聊天室的监控和分析。四川大学的温 粉莲、唐常杰、乔少杰等小组在对于邮件数据挖掘犯罪集团核心研究中提出了一种挖掘 网络核心的算法c n k m 。在国家自然科学基金资助项目( 6 0 2 0 4 0 0 9 ) ；国家“9 7 3 计划 基金资助项目( 2 0 0 4 c b 3 1 8 1 0 9 ) ；中科院复杂系统与智能科学重点实验室开发基金资助项 目f 2 0 0 4 0 1 0 4 ) t 扣高鹏、曹先彬通过分析聊天室数据的时序关系，推断出聊天用户间的社 会网络关系，根据社会网络蕴含的用户交流特点判断并过滤出噪声。社团挖掘方法是社 会网络分析的热点，有段丹、郭绍忠的基于邮件分类的敏感社团挖掘技术；王立敏、高 学东的基于相对密度的社团结构探测算法；朱大勇、侯晓荣的遗传聚类的社团结构发现 等。 社会网络分析在其它领域发展如下： 国家社会科学基金项目2 0 0 4 年度课题指南中第二十个课题就是关于社会网络的基 本理论与方法的研究。包括社会网络分析的基本理论、研究方法、主要流派、最新进展 和前沿问题；社会网络分析在中国社会学研究中的应用1 3 j 。 由国家自然科学基金优秀创新研究群体基金资助项目和国家自然科学基金资助项 目支持的，西安交通大学管院做的对比社会网络分析技术与其它方法研究网络破坏与安 全防护即如何进行攻击能够对网络给以毁灭性打击或如何防护能保障网络安全等问题 f 4 】。西安交通大学管院与美国卡耐基梅隆大学社会与决策科学系建立了合作关系，在网 络节点( 集) 重要性度量指标方面的研究在国内处于领先地位。 中国人民大学经济科学实验室。主要研究方向为：社会网、复杂网与互联网。采用 了多主体建模技术，发布了多主体建模软件r e p a s t 3 0 。r e p a s t 3 0 ，提供的多种应用开发 接1 ：3 也满足不同技能的人的需求，从最简单可爱的p y t h o n ，到大众流行的j a v a ，到微软 系统的忠实用户们喜欢的d o t n e t 甚至l i s p p r o l o g 等用户，都可以选择自己熟悉喜爱的 方，以统一的逻辑来设计模型。 2 0 0 2 年6 月成立的上海交通大学复杂系统与智能管理研究中心。提出社会网络的智 能管理是知识经济时代的新课题，也是现代管理的基本内容。社会网络的智能管理是对 一类特殊系统的特殊管理活动。它既具有管理的一般属性，也有其特殊的方面。 4 绪论 用社会网络分析对企业家及企业家网络构建的理论做分析；研究社会网络理论的核 心观点以及社会网络与企业成长的关系，在此基础剖析社会网络分析的基本单位( 关系 联结) v 2 及网络形成与演进的两种模式，对社会网络理论与企业问题研究可能的结合领 域进行了分析与探讨1 5 6 1 。 在复杂系统理论研究中借鉴社会网络分析；分析把社会学网络分析与自组织联系起 来的动态图理论。把社会网络引入到对经济社会现象的分析之中，对经济学的解释进行 补充，为社会关系被结合进经济模型提供途径【7 j 。 把社会网络分析运用到知识管理中1 8 】。i b m 知识研究所f 9 , 1 0 l 进行的研究使管理者可 以想象并理解，一些可能推动或阻滞知识创新和传播的相互关系。信息在一个组织内部 如何流动，人们会向谁求助，有没有出现合并后的下级组织不能有效共享信息的情况， 显示社群关系的模式和个体( 或组织) 之间的相对位置，加强知识管理。研究新知识和创 新技术的扩散。建立在社会网络层面的创新扩散模型。 1 2 3 国内外采用的网络分析软件 对于网络分析而言，正是由于数学方法的广泛运用，才得以让网络分析的术语很快 占领众多研究领域。除了使用s p s s 、s a s 、r s t a t a 对有关网络数据( 主要是自我中心网 络数据) 进行处理之外，根据网络分析的原理，目前，已经设计了大量的网络分析软件， 包括从数据录入到建模、画图与生成报告等一系列的功能。 目前在研究中主要使用的网络分析软件有： u c i n e t ：研究者使用较多的网络分析软件【1 1 j 。由博卡提、埃维瑞特以及弗里曼制作 的u c i n e t 。 p a j e k ：免费的大型网络分析软件包，参考材料较为丰富1 1 2 】。p a j e k ( 斯洛文尼亚语， 意指蜘蛛1 是3 2 位视窗系统中用于大型网络分析的应用软件程序，诞生于1 9 9 6 年，在 几位热心人士的培育完善下成长到今天这个( v e r s i o n o 9 9 ) 版本。p a j e k 是自由扩散非商业 用途的软件，可以自由下载，在本地选择目录简单安装后就能方便运行。 n e g o p y ：历史最为悠久的网络分析软件之一，比较容易使用。 b l a n c h ：使用属性以及关系两种分析方法来进行研究，可以生成网络动力学模型并 进行模拟，它以节点、链接和方程构成的系统，描述链接的强度和节点的属性随着时间 变化而变化的规律。 s o c i o m e t r y p l u s ：根据莫雷诺的思想设计的社会测量软件，提供建立群体继而分析 群体关系以及生成矩阵报告的功能。 s o c i o m e t r i c as u i t e ：是评估、构建和分析社会网络数据的软件包，目前j 下在研发当 5 j o 迕交通人1 ：硕十学f _ 论史 中。s o c i o m e t r i c al i n k a l y z e r 是其中的第一个成分，它从面向自我的数据，依据被提名 者的属性进行匹配，给社会网络图增加节点，从而构建出社会测量数据。 1 3 本文所做工作 在上述背景下，主要对社会网络核心的挖掘及社团挖掘算法进行了研究，本文的主 要内容有： ( 1 ) 对当前挖掘网络核心成员的方法进行分析提出了一种基于邮件挖掘社会网络核 心层的方法，该方法首先删除节点度小于一定阈值的节点，再运用社团结构及中心度分 析找出部分网络核心成员，最后结合已删除的节点得出完整的网络核心层。实验结果显 示，该方法可以找出全部的网络核心成员，且在一定程度上解决了大型网络不容易计算 的问题。 ( 2 ) 分裂方法和凝聚方法是寻找社会网络中社团结构的一类传统算法，本文集中于研 究凝聚方法，提出了新的社团评价标准并在此基础上给出一种挖掘社团结构的新方法， 定义社团内部节点链接数于外部链接数的比值为社团凝聚度，通过比较节点加入到社团 中前后社团凝聚度的变化来选择适合作为社团成员的节点加入社团，通过社团凝聚度的 变化还可以很容易地找到社团的边界，最后通过比较凝聚度可以确定哪些能作为社团哪 些只是分散的节点。 1 4 论文组织结构 本文按以下方式进行组织 第一章绪论 首先介绍本课题的研究背景，然后介绍了国内外的研究状况，分析了国内在社会网 络分析应用于网络安全方面的不足，并介绍了国内社会网络在其他领域的发展。最后， 列出了国内外主要应用的社会网络分析软件。 第二章社会网络分析概念与常用方法 首先介绍了社会网络基本的概念，其次介绍了常用的三种社会网络分析测度：社团 结构、中心性以及角色分析，然后重点分析社团结构分析的两种方法分裂法和凝聚法， 以及在这两种方式中前人所作的算法研究，接着介绍了可重叠的、遗传聚类的和基于相 对密度的社团结构挖掘算法，最后介绍了在网络安全领域( 尤其是电子邮件) 的一些研究 成果。 第三章社会网络核心挖掘研究 6 绪论 首先，由网络安全问题引出了社会网络分析的重要性，然后介绍了前人所作的部分 研究，并对此进行了分析，最后根据分析结果提出了一种基于邮件挖掘社会网络核心层 的算法，并用实验验证了算法的正确性。 第四章社团挖掘算法研究 首先，分析当日玎流行的一些社团挖掘算法引出局部社团挖掘的必要性，然后提出一 种衡量局部社团凝聚力的指标局部社团凝聚度。在此指标基础上提出了一种基于局 部社团凝聚度的社团挖掘算法，最后通过实验验证算法是正确的和有效的 总结 对本文工作的总结和对未来工作的展望。 7 人近交通人j ：l ，7 硕卜0 j ? 伊论文 第二章社会网络分析概念与常用算法 社会网络分析主要是研究社会实体i 日j 的关系连结以及这些连结关系的模式、结构与 功能。社会网络分析同时也可用来探讨社群中个体i 刈的关系以及由个体问关系所形成的 结构及其意义。换言之，社会网络分析的主要目标是从社会网络的潜在结构( 1 a t e n t s t r u c t u r e ) r p ，分析发掘其中团体之间的关系动态【l 引。全球信息网( w o r l dw i d ew e b ) 的兴 起，让人类的许多社会活动从此能够在网一卜进行，而这些网上的社会活动也产生了大量 的数据。例如：在虚拟的计算机信息网络中，计算机中介沟通( c o m p u t e r - m e d i a t e d c o m m u n i c a t i o n ，c m c ) 系统，如：u s e n e tn e w s g r o u p s ，e m a i ll i s t s ，o n l i n ec h a t s 等等，促 进了大规模的人际交流与沟通，同时也产生了大量的这些人际沟通活动的详细记录。这 些详细记录的数据，正可以用来分析及可视化这些只存在于在线论坛的社会关系网络。 这些分析与可视化在线人际交流与沟通详细资料的努力，往往可以改善我们对人际沟通 机制的理解，同时也可导致c m c 系统的加强与改良。如果能对这些数据深入分析，不 仅能让我们对目前的网络使用现象有深入的了解，也可对未来人类社会的发展趋势有所 掌握。 2 1 社会网络 在社会学中，网络研究通常有两种视角：第一，将网络视为一种分析工具，凭借这种 工具可以理清行动者之间、行动者与其环境之间的关系；第二，将网络视为由行动者之间 的关系所构成的社会结构，此时关系本身成为研究的对象【1 4 l 。但实际研究中这两种视角 通常难以截然分开，两者你中有我、我中有你的局面往往使网络研究既全面深入又错综 复杂，网络分析就是其典型。在网络分析中，“网络 被认为是联结行动者的一系列社 会联系或社会关系f 1 5 j ，它们相对稳定的模式构成社会结构。这暗示着网络分析应当具 有两个基本要素，即行动者和社会关系( 社会联系) 。前者一方面是有意识的行为主体， 另一方面其行为又不得不受社会网络的制约；后者则是在行动者之间因某些特定的关系 而发生互动的基础上积累起来的联系模式。 网络结构通常指网络内部各行动者之间相对稳定的关系模式或“结构洞”模式，尤 以后者为重。伯特( b u r t ，1 9 9 2 ) 1 1 6 j 是最早系统阐述“结构洞 这个概念的学者，用它来 指称网络中某些行动者之间关系( 联系) 缺乏的现象。按照伯特的观点，当网络中人们之 间没有直接关系或关系缺失时，网络就会出现空洞，即所谓的“结构洞 。“结构洞”之所 以重要，是因为“结构洞 通常构成了网络中信息折射和资源流动的“阀门”，是否折 射或流动、如何折射或流动，这一切都可以掌控在占据“结构洞”的行动者手罩。因此， 8 葡：章社会嘲络分析概念! j 常川方法 在网络中占有的“结构洞”越多， j 二动者在结构上所占的优势就越大，通过这些优势获 得回报的可能性就越高。社会网络分析用于描述和测量行动者之间的关系或通过这些关 系流动的各种有形或无形的东西，如信息、资源等【1 7 1 。自人类学家b a r n e s ( 1 9 5 4 ) i 1 8 l 首次使 用“社会网络”的概念来分析挪威某渔村的社会结构以来，社会网络分析被视为是研究 社会结构的最简单明朗、最具有说服力的研究视角之一。2 0 世纪7 0 年代以来，除了纯 粹方法论及方法本身的讨论外【1 9 l ，社会网络分析还探讨了社团结构、中心性、角色分 析以及组织内部的网络、市场网络等特殊的网络形式i2 0 1 。这些讨论逐渐形成了网络分析 的主要内容。 根据分析的着眼点不同，社会网络分析可以分为两种基本视角：关系取向和位置取 向1 2 1 】。关系取向关注行动者之间的社会性粘着关系，通过社会联结本身如密度、强 度、对称性、规模等来说明特定的行为和过程。按照这种观点，那些密集的且相对 孤立的社会网络可以促进集体认同和亚文化的形成。与此同时，位置取向则关注存在于 行动者之间的、且在结构上相处于相等地位的社会关系的模式化，讨论的是两个或以上 的行动者和第三方之间的关系所折射出来的社会结构，强调用“结构等效 来理解人类 行为。 我们已经知道社会网络分析的对象是实体及其之间的联系，那么这些对象以及它们 之间的联系是以什么方式存储的呢? 在此有必要解释一下社会网络的数据存储方式。 数据主要分为“属性数据”和“关系数据 两类f 2 2 1 。属性数据( a t t r i b u t e ) 指涉及能动 者( 社会网络分析的实体对象) 的态度、观点和行为方面的数据，它们被视作为能动者的 个人或者群体所具有的财产、性质、特点等。例如，通过调查和访谈收集得到得资料常 常被简单的看成是特定个体的一些属性，并且可以利用许多现有的统计程序对这些数据 进行量化分析。适用于分析属性数据的方法主要是“变量分析法( v a r i a b l ea n a l y s i s ) ”，这 些方法把各种属性测量为一些特定变量( 收入、职业、教育程度等) 的取值。 另一方面，关系数据( r e l a t i o n a ld a t a ) 贝o 是关于接触、联络、关联、群体依附和聚会 等方面的数据，这类数据把一个能动者与另外一个能动者联系在一起，因而不能还原为 单个行动者本身的属性。关系不是行动者的属性，而是行动者系统的属性；这些关系把 多对行动者联系成一个更大的关系系统。 2 2 社会网络分析测度 社会网络分析的主要内容有社团结构、中心性、角色分析等。 2 2 1 社团结构分析 社团结构( c o m m u n i t ys t r u c t u r e ) 也称为小团体( c l i q u e s ) 就是团体中的一小群人关系特 9 人连交通人学lj 学颂 j 伊论文 别紧密，以至于结合成一个次级团体。社团结构叮以比拟为一个个的派系，这是一个网 络总体的结构指标，而且在研究组织行为时，是一个特别有用的概念，这是社团结构的 自参照定义。而强社团、弱社团的定义则是比较型定义，强社团：社团中每个节点与社 团内节点的链接数都大于与社团外节点的链接数，弱社团则反之。 计算社团结构的方法有两类，一类是以节点程度来计算，一群相连的节点视为一个 社团结构l 矧。三种以节点程度来计算的分析方法：k p l e x ，k c o r e 以及l a m b d as e t s 。 k p l c x 的定义是：包含了g s 节点的子图形，在该图形中，每一个节点都与同一图 形中的g s k 个节点有相连的关系。表示一个团体中有g s 个人，其中每个人都至少与该 社团结构的其他成员保持g s 减k 条的关系。 k c o r e 的定义：如果对所有的n 。来说，d 。( i ) = k ，则子图形g s 是k c o r e 。其中d ，( i ) 指称相连的节点数目。这个定义与k p l e x 大同小异，表示一个团体有g s 个人，其中每 个人都至少与该社团结构的其他成员保持k 条的关系。 入集合的概念比较复杂，先看看什么是两个节点的线段性相连。线段相连性就是如 果要把这两个节点的最后一条路径删掉，也就是使两个节点不再相连，需要删去几条线 的数量，代号是琊，j ) 。线段相连性越高，表示两个节点相连的路径越多，而且还会有 关键的桥，必须要删掉很多线段，才能使他们不相连。入集合的定义：一个九集合t 是 n 的子集合，对所有子集合内的节点i ，j ，k 而言，存在有一子集合外的节点l ，则九( i ， j ) m k ，1 ) 。 此一定义指，入集合中的内部任两个节点的线段相连性都要高于内部的一点与外部 的一点的线段相连性。现实的意义就是，社团结构的定义在于内部的紧密而关系不易断 裂的程度要高于内部的人与外人的紧密程度。 以距离为基础计算社团结构的方法：1 1 c l i q u e ，n c l a n ，n c l u b 。 图2 1 社团结构 f i g 2 1s o c i a ln e t w o r k 1 0 笫：争十 会1 t - ，3 分析 c 念j 常川7 j f 左 n c l i q u e 也就是此社团结构内每两个人之i j 的距离要小于等于n ( d ( i ，j - n ，订， 刀，) 。d ( i ，j ) 是i 与j 两点| 、日j 的距离，以图2 1 为例，2 - c l i q u e s 有两个： 1 、2 、3 、4 、 5 】和 2 、3 、4 、5 、6 。n c l a n 定义一个n c l a n 是一个n c l i q u e ，而且所有捷径都必须包在 子图形内。图2 1 中，2 c l a n 有一个： 2 、3 、4 、5 、6 ) 。n c l u b 指子图形的直径要小于或 等于n ；2 - c l u b 有三个： 1 、2 、3 、4 ) ， 1 、2 、3 、5 ) ， 2 、3 、4 、5 、6 ) 。 2 2 2 中心性 中心性是网络中重要个人的结构位置指针，评价一个人重要与否，衡量他她的职务 的地位优越性或特权性，以及社会声望等常用这一指针。中心性分成三种形式：局部中 心度( 1 0 c a lc e n t r a l i t y ) 、中心势( c e n t r a l i z a t i o n ) 、中介性( b e t w e e n n e s sc e n t r a l i t y ) 。 局部中心度与中心势是计算一个人在一个团体的网络中最主要的两项个体结构指 针。局部中心度是我们最常用来衡量谁在这个团体中成为最主要的中心人物。这样的人， 在社会学的意义上，就是最有社会地位的人；在组织行为学上，则是最有权力的人。拥 有高中心性的人，在这个团体中也具有一个主要的地位。 衡量局部中心度的公式如下，公式( 2 1 ) 为绝对数值，公式( 2 2 ) 为标准化数值。( 2 1 ) 就是把某人的关系数加总，( 2 2 ) 是将其除以该网络最多关系数，好做不同网络间之比较。 c d ( n i ) = d ( n ；) = = x 一 ( 2 1 ) c ，。2 篱 ( 2 2 ) x i j 是0 或1 的数值，代表行动者是否承认与行动者i 有关系，g 是此一网络中的人数。 在社会网中，局部中心度即是一个人的关系数量的总和，因为每一个图形中节点数量不 一，大的社会网络人数多，关系数也多，所以标准化过程要除以某一节点在社会网中最 大可能的关系数，即是g 1 条关系。 中心势，又名群体局部中心度( g r o u pl o c a lc e n t r a l i t y ) 公式： c 。薹竺竺：兰 m a x 艺【c d ( n 宰) 一c 。( n t ) 】 ( 2 3 ) c d ( n 宰) 是c ( n ) 中最大的局部中心度，它与其他c d ( n 宰) 相减所得差额的相加总和，即 为群体中心性。分母是此一数值的最大可能值。这是一个网络的整体结构指针，公式的 人连交通人学l 学硕十学伊论文 含义是，一个图形中，局部中心度最高的那个人其局部中心度与其他人局部中心度i 日j 的 差距。他与别人的差距越大，则群体局部中心度的数值也越高，表示此一团体权力过分 集中，有一个人特别重要。群体局部中心度最高的图形是星形图形。 无方向性图形中星形网络的群体中心性是( g 一1 ) ( g 一2 ) ，所以分母是( g - 1 ) ( g - 2 ) 。此时公 式变为： 罗【c d ( n 木) c d ( n ；) 】 乙。2 面丽 ( 2 4 ) 具方向性图形则有一些不同，分外向局部中心度( o u t 1 0 c a lc e n t r a l i t y ) 与内向局部中心 度( i n - l o c a lc e n t r a l i t y ) ，外向局部中心度是一个节点承认对外关系数量的总和，其公式如 下： )