（计算机应用技术专业论文）关联网络的社区发现研究.pdf

摘要 皇量鼍蔓寡曼曼曼曼曼曼寡曼! ! 曼皇曼曼曼曼曼曼曼鼍曼曼曼曼曼曼曼曼曼寰i i 皇曼曼曼曼曼皂苎曼曼曼皇毫寰曼曼曼皇曼烹曼皇曹量曼曼曼曼! 曼皇曼曼 关联网络的社区发现研究 计算机应用技术专业硕士研究生阎艳 指导老师邱玉辉教授 摘要 现实世界中的许多系统都可以用关联网络表示，如w w w 、引文网络、股票 关联网络、蛋白质关联网络、神经网络等等。尽管这些网络有着不同的描述对 象，它们却有许多共同点。社区结构是关联网络的普遍性质之一。社区是网络 的缩影，是理解网络结构和分析网络性质的基础。从不断变化的网络结构中， 有效地发现社区结构及其变化过程，有助于分析网络结构性质，了解整个网络 的动态，预测网络变化，从而为实现网络结构优化、资源搜索、资源推荐等提 供方法。近年来，社区结构以及进化过程的发现开始成为关联网络领域的研究 热点之一，并被应用在各种现实关联网络的分析中。 然而，现有社区发现方法往往只是提取并列关系的社区结构，这些社区或 相互独立，或部分重叠，并没有考虑社区之间可能存在的层次关系。此外，n 社区的进化过程中，社区层次会不断发生改变，单一层次的社区发现难以确侏 得到合理的社区结构，从而可能无法准确发现社区的进化过程。不仅如此，现 有的社区进化类型判断标准很难满足社区变化的复杂性。针对这些不足，本文 提出了一种改进的关联网络发现方法：引入社区层次结构，在社区结构层次结 构的基础上，寻找社区的进化过程。利用该方法，对d b l p 文献标题的单词关 联网络进行社区发现分析。 本文研究的主要工作包括这样几个方面： 第一，分析了传统社区提取方法和现有社区进化发现方法，针对其不足， 提出了一个关联网络的社区发现框架，阐述了社区发现的基本流程，引入带时 间属性的关联网络、关联网络片段、社区层次结构、社区进化图等概念，并进 行形式化描述。 第二，讨论了社区发现方法。包括：对社区层次结构的构建进行研究： 分别从社区的拓扑结构和社区的内容性质出发，讨论基于社区凝聚度的社区层 两南人学硕十簟位论文 次结构和基于关联本体的社区层次结构，芳给出了构造社区层次结构的算法描 述。提出了一种利用各个时间片段的社区层次结构寻找社区进化过程的方法t 定义了社区进化的基本类型以及社区进化的度量标准，给出了利用社区相关度 构建社区进化图的算法描述。 第三，将上述方法应用到2 0 0 0 2 0 0 7 年d b l p 文献标题的单词关联网络， 发现该网络的社区结构及其进化过程，分析各社区成员和变化的特点，通过比 较现有方法，以验证其可行及有效性。实验结果表明，通过构建关联网络各个 时间段的社区层次结构，寻找社区的相关状态，和现有方法相比，在一定的程 度卜，能够更有效地发现关联网络中的不同凝聚度的社区结构及其进化过程。 关键词：关联网络社区层次派系过滤社区进化单词关联网络 a b s t r a c t r e s e a r c ho nc o m m u n i t yd i s c o v e r yi n a s s o c i a t i o nn e t w o r k m a j o r ：c o m p u t e ra p p l i c a t i o n p 0 s t g r a d u a t e ：y a ny a n s u p e r v i s o r ：p r o f q i uy u h u i a b s t r a c t a s s o c i a t i o nn e t w o r ki st h ea b s t r a c t i o no fe n t i t i e sa n dt h e i rr e l a t i o n s h i p s i t sw i d e l y u s e di nt h es t u d yo fm a n yr e a lw o r l ds y s t e m s c o m m u n i t y ，a l s om e n t i o n e da sm o d e l ， g r o u pe t c i sac o m m o np h e n o m e n o ni na s s o c i a t i o nn e t w o r k ，w h i c he x i s t s a sa r e d u c t i o no ft h ew h o l en e t w o r k d i s c o v e r i n gc o m m u n i t i e sf o r md y n a m i cn e t w o r k a n dd e t e c t i n gt h e i re v o l u t i o np r o c e s si so fg r e a ti m p o r t a n c ei na n a l y z i n gt o p o l o g y f e a t u r e sa n dd y n a m i cc h a r a c t e r i s t i c s r e c e n ty e a r sw i t n e s sa ni n c r e a s i n gi n t e r e s ti n t h es t u d yo fc o m m u n i t yd i s c o v e r y s of a r ，c o m m u n i t yt e c h n i q u e sh a v eb e e na p p l i e d t on e t w o r ko p t i m i z a t i o n ，r e s o u r c ed i s c o v e r ya n dr e s o u r c er e c o m m e n d a t i o n h o w e v e r , e x i s t i n gc o m m u n i t yd i s c o v e r y m e t h o d sh a v et h e f o l l o w i n g l i m i t a t i o n s f i r s t l y , t h ee x t r a c t e dc o m m u n i t i e sa l eo ft h es a m el e v e l ，e i t h e rd i s j o i n t o rp a r t l yo v e r l a p p i n g ，w h i l ec o m m u n i t i e st e n dt ob eh i e r a r c h i c a l ，i e al a r g e c o m m u n i t ym a yf u r t h e rf a l l i n t os e v e r a ls u b - c o m m u n i t i e s d u et ot h el a c ko f c o m m u n i t yi n f o r m a t i o n ，i ti sh a r dt og e taf u l lo u t l i n eo ft h ew h o l en e t w o r ka n d f u r t h e re f f e c t i v e l yd e t e c tt h ec h a n g e so fc o m m u n i t i e s m o r e o v e r , t h ee x i s t i n g c l a s s i f i c a t i o no fe v o l u t i o nc a t e g o r i e sc a n ts a t i s f yt h ec o m p l e x i t yo fp o s s i b l e v a r i a t i o n t oo v e r c o m ea b o v ep r o b l e m s ，t h i st h e s i sp r o p o s e sa l la p p r o a c ht o c o m m u n i t yd i s c o v e r ya n da p p l i e si t t ow o r da s s o c i a t i o nn e t w o r kf r o md b l p b i b l i o g r a p h yt i t l e s t h er e s e a r c hw o r ki n c l u d e st h ef o l l o w i n g a s p e c t s ： f i r s t l y , b r i e f l yi n t r o d u c e sa n da n a l y z e st h es t a t e o fa l _ t s ；t h e n p r e s e n t s a f r a m e w o r kf o rc o m m u n i t yd i s c o v e r yi na s s o c i a t i o nn e t w o r k ；g i v e st h ef o r m a l d e s c r i p t i o n o fa s s o c i a t i o nn e t w o r kw i t ht e m p o r a lf a c t o r ，a s s o c i a t i o nn e t w o r k s e g m e n t ，c o m m u n i t yh i e r a r c h ys t r u c t u r ea n dc o m m u n i t ye v o l u t i o ng r a p h 1 1 1 p q 南人导：7 ，员十。7 ：何论文 s c c o n d l y ，d e t a i l sh o wt od i s c o v e r h i e r a r c h i c a lc o m m u n i t i e sa n di d e n t i f y c o m m u n i t ye v o l u t i o np r o c e s s i na s s o c i a t i o nn e t w o r k ，i n c l u d i n gb a s i ci d e ao f c o m m u n i t yh i e r a r c h yo nc o h e s i o na n da s s o c i a t i o nl e v e lo n t o l o g y , a l g o r i t h m sf o r c o m m u n i t yh i e r a r c h yc o n s t r u c t i o n ，c l a s s i f i c a t i o no f e v o l u t i o nc a t e g o r i e s ，m e t r i c so f e v o l u t i o n a r yd e g r e e ，a n da l g o r i t h mt oi d e n t i f ye v o l u t i o np r o c e s s t h i r d l y , c o n s t r u c t saw o r da s s o c i a t i o nn e t w o r kf r o md b l pb i b l i o g r a p h y d a t a s e t ；u s e st h ep r o p o s e dm e t h o dt od i s c o v e ri t sc o m m u n i t ys t r u c t u r ea n da n a l y z e s t h er e s u l t t h eo u t c o m es u g g e s t st h a tt h i sa p p r o a c hp r o v i d e saf e a s i b l ea n de f f e c t i v e m e t h o df o rc o m m u n i t yd i s c o v e r y k e yw o r d s ：a s s o c i a t i o nn e t w o r k ，c o m m u n i t yh i e r a r c h y ，c l i q u ep e r c o l a t i o n m e t h o d ，c o m m u n i t ye v o l u t i o n ，w o r da s s o c i a t i o nn e t w o r k 独创性声明 学位论文题目：吏殛因豳趁壁笈塑固疃 本人提交的学位论义足在导师指导下进行的研究f ：作及取得的 研究成果。论文中引用他人r 2 , 经发表或出版过的研究成果，文 t 已加 了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同 仁在文中作了明确说明并表示衷心感谢。 学位论文作者：( 朗乡己j 签字日期：z 。尸年y 月z c l f 日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权两南大学研究生院( 筹) 可以将学位 论文的伞部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫批等复制手段保存、乳：编学位论义。 ， ( 保密的学位论文在解密后适用本授权书，本论文：耐不保密， 口保密期限至年月止) 。 学位论文作者签名：( z 刁毙之 签字日期： z 一 9 年歹月z 叮日 导师签名： 签字嗍：1 耵月7 日 第1 章引言 第1 章引言 本章对论文研究的背景、国内外相关研究现状、研究的内容和意义以及沦文 的内容安排予以说明。 1 1 背景 现实世界中的许多系统都可以用关联网络抽象表示，网络中的节点代表系统 中的个体，网络中的边代表个体之间的某种联系。这种表述方法被用在多种系统 的研究中，如w w w 、对等网络、科学家合作网络、引文网络、股票关联网络、 蛋白质关系网络、神经网络等等。w w w 中，每个节点对应一个页面，网页间的 超链接为节点间的边；科学家合作网络中，每个节点表示一个科学家，节点间的 边表示科学家间的合作关系；神经网络中，每个节点表示一个神经元，节点问的 边对应神经元间的相互作用。越来越多的研究表明，尽管这些网络有着不同的描 述对象，涉及不同的学科领域，它们却有着许多共同的统计特性，如小世界性、 无标度性、聚类特性等等。 随着对网络性质的物理意义与数学特性研究的深入，人们发现许多父瞅i x x j 络 都具有社区结构性质，即网络是由若干个社区构成的，社区内部的节点f 1 1 j 连接较 为紧密，而社区之间的连接相对稀疏 1 。通常，i 司属于个社区的节点土i 有相似 或相关的性质。在w w w 中，同一个社区内的页面往往涉及相关的主题；在神经 网络中，一个社区通常对应一个功能组；在科学家合作网络中，同一个社区内的学者 大多有着近似的研究兴趣。发现网络中的社区结构，对于理解网络结构和分析网 络性质尤为重要。社区的发现技术，从最初的图分割方法、w - h 算法、层次聚类 法、g n 算法等基本算法，逐渐发展和改进，形成了包括改进o n 算法、派系过 滤算法、局部社区算法和w e b 社区发现方法在内的更具可操作性的方法。这些方 法被用于各种关联网络的分析中 3 】。对于大规模网络，时间复杂度和准确性仍然 是社区发现方法所面临主要问题。 现实关联网络通常具有动态性。一方面，网络的连接结构会随时问改变，不 断有节点、边产生或删除，例如，w w w 中的页面和链接每天都在更新：男”方 面，节点间的边的性质( 如权重、方向、类型) 也会发生变化，例如，神经系统 中的突触有强有弱，时而抑制，时而兴奋。这些改变会引起社区的变化。l 删络- 1 ， 随时会有新的社区涌现，也会有社区消亡；社区的规模町能膨胀，也i , j 能缩小： 在社区内部，成员间的联系可能更加紧密，也可能变得松敞；社区可能合并，也 曲南人。：硕十。学位论文 可能分解。发现动态l 叫络中的社区及其变化过程，有助于人们了解整个网络的动 态，预测例络的变化趋势，从而为实现刚络结构优化、资源搜索、资源推荐等提 供依据。近几年，动态网络的社区发现开始受到研究者的关注。目前，社区进化 发现主要针对w w w 、社会网络、对等网络、b l o g 网络等等。由于网络结构的复 杂性和变化的不确定性，如何有效的发现网络中的社区结构及其进化过程是当前 关联网络社区发现的难点之一。如何合理地解释、评价所发现的社区及其变化也 是社区分析需要解决的问题。 1 2相关领域及研究现状 1 2 1 社区提取技术 发现关联网络的社区结构是揭示网络结构和功能之间关系的重要基础。网络 的 t ：i x l 宝 构分析营f 魁关联网络研究的热点课题之一，它与计算机科学中的图划 分( g r a p hp a r t i t i o n ) 和社会学中的分级聚类( h i e r a r c h i c a lc l u s t e r i n g ) 有密切的联 乏 j 、o 图划分问题旨存将图中的节点划分为若干个子集，要求划分后各子集间所连 接的边数最少。该问题是一个n p 难题，人们提出了多种启发式算法以求得问题 的近似解。其中，包括两类著名算法k e m i g h a n l i n 算法和谱平分法( s p e c t r a l b i s e c t i o nm e t h o d ) 。k e m i g h a n l i n 算法 5 】是一种基于贪婪算法原理将网络划分为2 个已知大小的社区的二分法，算法要求必须事先知道社区的大小，这一缺陷使该 算法在实际网络中难以应用。基于l a p l a c e 矩阵特征值的传统谱平分法算法【6 和 基于电阻网络电压谱的w u h u b e r m a n 算法 7 】复杂度较低，但它们都要求事先知 道网络的社团数目，然而在实际网络分析中，社区的数目往往是未知的。为克服 该缺陷，c a p o c c i 等人在传统谱平分法基础上进行改进，提出基于标准矩阵的谱 平分法 8 】，该算法刘。社区结构不太明显的网络也能取得较好的效果。上述方法的 共缺陷在f ，算法每次只能将网络一分为二，如果要将网络分为多个社区，就 必须埘j i 丰 ：区多次重复该算法。 分级聚类是社会网络中的社i 錾：发现的一类传统方法，它基于各个节点之间连 接的相似性或强度，对网络进行划分。分级聚类算法分为两大类：分裂算法和凝 聚算法。g n 算法【9 是分裂算法的代表，其基本思想是不断从网络中移除介数( 即 网络中经过每条边的最短路径的数量) 最大的边。g n 算法主要有两个缺陷，一 是对缺少对社区结构的量的定义，二是需要重复计算。人们在g n 算法的基础上 提出了多种改进或衍生的算法。n e w m a n 等人引入模块度( m o d u l a r i t y ) 【1 0 1 作为 第1 章引言 衡量网络划分的质量标准，克服了g n 算法必须借助附加信息判断社区结构是否 有意义的缺陷。t y l a r 等人提出用某个节点集，而不是用网络中所有节点，来计算 边介数，从而加快了计算速度i 1 1 】。r a d i c c h i 等人提出一种自包含g n 算法 ( s e l f - c o n t a i n e dg na l g o r i t h m ) ，引入强社区和弱社区作为社区结构的衡量标准，克 服了模块度 1 0 】计算复杂的缺点；采用边聚类系数取代边介数，相比g n 算法， 算法速度有很大提高；该算法成功应用在科研合作网络 1 2 1 。z h o u 等人提出一种 基于相异性的分裂算法，并应用在酵母菌的蛋白质网络中 1 3 】。f o r t u n a t o 等人提 出一种采用信息中心度的算法 1 4 】，采用信息中心度墩代g n 算法中的边介数。 z i v 等人用信息瓶颈来定义网络模块性，并提出了一种社区发现方法 1 5 】。n e w m a n 快速算法 1 6 是一种基于贪婪思想的凝聚算法，它适用1 二大规模的复杂网络。 c l a u s e t 等人对n e w m a n 快速算法进行改进，采用堆结构计算和更新模块型函数， 成功地对a m a z o n 网上书店的网页链接关系网络进行了分析i 1 7 1 。 无论是分裂算法还是聚类算法，都是将网络划分为相互分离的社区【1 】。然而， 网络中的社区很多时候是相互关联、重叠的。p a l l a 等人提出派系过滤方法 1 9 2 0 】 ( c l i q u ep e r c o l a t i o nm e t h o d ，c p m ) ，该方法可以发现相互重叠的社区结构，被应 用在合著网络、词汇关联网络、蛋白质网络、通讯网络的社区分析中。g r e g o r y 在g n 算法的基础上，引入分裂介数的概念 2 5 1 ，通过对分裂介数最高的节点进 行分裂( 复制) ，可以得到重叠的社区。文献 2 6 提出了一种利用模糊c m e a n s 聚 类的重叠社区发现方法，实验结果表明该方法可以有效获取准确的社区。 在无向网络的研究基础上，研究者还将社区发现算法扩展到有向网络以及异 构网络中。为了有效利用有向网络中边的方向信息，p a l l a 等人z ec p m 的壤础i ：， 引入有向派系的概念，提出有向派系过滤方法 2 2 】。文献 2 7 】针对w w w 这样的 有向网络，提出了一种将网络转换为二部图，利用信息瓶颈寻找网络的最优膻缩 的方法，并将该方法应用到单词联想网络中。异构网络中存在不止一类节点，节 点间的关系也不止一种。文献 3 l 】对学术网络进行了研究，该网络包含科学家、 文献、会议等3 类节点，以及引用、合作、作者、录用、隶属等5 种关系。诸葛 海在文献 2 3 】中提出了3 类方法，分别用于发现语义链网络( s e m a n t i cl i n k n e t w o r k ，s l n ) 中的推理约束、规则约束和分类约束的语义社区。 尽管社区发现研究已经取得了一定成绩，时间复杂度和准确性仍然是大规模 关联网络社区分析算法面临的两个主要问题。如何针对不同类型网络的特点找到 快速而且可靠的社区发现算法，是社区发现研究领域需要解决的主要问题。 硝南火学硕十学何论文 曼j l i 一：一 ： i i 曼皇曼曼曼曼曼! 曼皇曼! 舅曼! 曼曼曼曼曼曼! 曼曼鼍曼曼曼! 曼皇曼! ! 曼皇! 皇曼! 曼曼! 曼曼曼曼曼曼曼皇苎蔓曼曼曼苎! 鼍曼 1 2 2 社区进化发现 脱仃例络分析以及可视化的：】二具，如s t o c n e t 、u c i n e t 、p a j e t 、c f i n d e r 等等，针刈的是静念剐络，没有考虑网络本身的时态变化，而一些用于分析动态 网络的i ：具，如s o n i a 2 9 】、t e c f l o w 3 0 等等只是从节点、边的角度分析网络的 变化。最近，一些研究者注意到网络动态变化与社区进化之间的联系，试图从社 区的层次上，分析、解释以及预测动念网络的结构和性质。社区的进化过程反应 了整个网络的变化。为了从动态网络中提取出合理的社区结构，社区发现方法开 始引入时间( t e m p e r a l ) 属性。目前，社区进化发现主要用于分析w w w 、社会 网络、对等网络等等。相关研究工作有： t o y o d a 等人研究了w e b 社区的进化 3 2 】。一个w e b 社区( w e bc o m m u n i t y ) 由若干网页构成，网页之间由密集的超链接相连，这些网页通常关于同一话题， 社区的变化直接反应了w 曲话题的演变。通过分别对1 9 9 9 、2 0 0 0 、2 0 0 1 、2 0 0 2 年的网页存档构建网络并提取社区，从而建立社区图( c o m m u n i t yc h a r t ) ，分析 w e b 朴k 的进化过彩和涌现现象。在分析社区进化时，引入了一系列度量标准， 如增k 率( g r o w t hr a t e ) 、稳定性( s t a b i l i t y ) 、新颖度( n o v e l t y ) 、消失率( d i s a p p e a r a n c e r a t e ) ，融合率( m e r g er a t e ) 、分裂率( s p l i tr a t e ) 等等，对复杂的社区变化进行描 述。炙验发现，社区大小以及社l 莲的各种变化都满足幂律分布。 “ k u m a r 等人对b l o g 网络的社区变化进行了分析 3 7 】，该网络覆盖了2 5 万个 b l o g 和7 5 万条链接。引入了时间图的概念对传统网络图进行扩展，利用剪枝 ( p r u n i n g ) 和扩展( e x p a n s i o n ) 算法提取社区，进而分析网络中的突发( b u s t ) 现象。研究发现，b l o g 网络中社区结构的数量和规模都有明显的增加。 p a l l a 等人研究了两类社会网络的社区进化 1 8 】。其中，合著网络( c o a u t o r s h i p ) 包含约三万个作者的合作关系，时间跨度为1 4 2 个月；通话网络包含约四百万个 手机用户的通话记录，时间跨度为5 2 周。首先，基于c p m 算法从各个时间段的 网络图中提取社区。然后，对相邻两个时间段构建一个公共网络( j o i n t n e t w o r k ) ， 借助该网络找出相邻时间段的社区的对应关系，从而得到社区的进化过程，并引 入相关性( c o r r e l a t i o n ) 、固定性( s t a t i o n a r i t y ) 对社区的进化进行度量。实验表明， 在社会网络中，大社区的成员变化率更高，而小社区的成员变化较小，甚至保持 4 i 变， y l 卜r ul i n 等人摊出f a c e t n e t 框架 3 3 l 用于分析动念网络中的社区及其进化， 并对2 0 0 5 年8 月到2 0 0 6 年9 月的n e cb l o g 数据集，以及1 9 9 7 到2 0 0 6 年数据 库、数损l 挖掘和人工智能领域的d b l p 合著数据集分布进行了分析。和传统方法 不同，f a c e t n e t 框架将社区发现和进化发现作为一个整体，用t 1 时刻的社区结构 4 第1 章引言 来调整t 时刻的社区结构，从而克服噪音的影响。并引入社区网、进化网等概念， 对产生的社区及其进化过程进行度量，确定社区之间的一致性。 b a u m e s 等人提出v i s a g e 3 8 系统用以模拟分析社会网络中的社会团体的进 化，研究社会网络的涌现性质及现象，通过学习预测可能的变化。v i s a g e 包含 四类模型：参与者及社区模型，定义了各个参与者以及社区的相关性质；资源模 型，定义参与者之间相互作用的条件；成员模型定义了参与者如何加入或者离开 一个社区；行为评价模型，定义个体、社区之间的关联机制。在模拟过程中，社 区的数量是默认的，没有新社区产生，也没有旧的社区消亡。 b a c k s t r o m 等人通过对l i v e j o u r n a l 和d b l p 两个数据集中的虚拟社分析发 现，个体是否加入一个社区、一个社区是否增长，取决于网络的结构 4 0 】。例如， 一个个体是否加入某个社区，不仅取决于他有多少“朋友”属于这个社，也墩 决于这些朋友之间的连接方式。个体在社区之间的运动问接反映了社区内部的主 题变化。 a s u r 等人从事件的角度，分析了d b l p 合著网络和从临床实验数据构建的病 患关联网络中社区和个体的变化【4 1 】。定义了5 类关于社区基本事件：延续 ( c o n t i n u e ) 、k - 合并( k m e r g e ) 、k 分裂( k s p l i t ) 、形成( f o r m ) 、瓦解( d i s s o l v e ) 以及4 类关于个体的事件：出现、消失、加入、离开。通过从连续且不相重叠的 时间段的网络图中提取事件，分析社区的变化过程和个体行为对社区变化的影响。 由于网络结构的复杂性和变化的不确定性，如何有效的发现网络中的社区结 构及其进化过程是当前网络分析的难点之一。如何解释所发现的社区及其变化也 是网络社区分析需要解决的问题。 1 3研究内容 发现关联网络中的社区，通常是一件十分困难的事情。其中的一个玛i 队；“r 网络本身的复杂性。现实关联网络往往规模巨大，动辄包含数j 个甚至数l ，i 力。个 节点，且节点之间的关系错综复杂。很多时候，网络中没有明掘的社区当构，网 络中社区的数量是未知的，各个社区内的成员个数事先也难以确定。不仅如此， 社区之间的关系也是多样的：社区可能相互独立，也可能相互重叠；一个社区可 能包含若干个子社区。此外，现实关联网络常常随时间发生变化，网络中的社区 结构也会随之改变，可能有新的社区涌现，也可能会有旧的社区消亡；社区内部 的成员可能会不断变动。这些现象亦增加了社区发现的难度。 在现有的社区发现方法中，存在一些问题如下： ( 1 ) 现有社区提取方法所得到的社区或相互独立，或部分重叠，这些社区是并 州 幸j 人学硕- 卜学何论文 列的，位于i 列一层次上。而事实上，社区结构有时候会呈现层次特性，一 个社区可以进一步划分成几个子社区。 ( 2 ) 在分析不同时间的网络的社区结构时，为了在同一条件下比较社区的变化 过程，采用固定参数标准进行社区提取。然而，在社区的进化过程中，社 区的内聚度和强度会不断发生改变，固定参数标准难以保证得到合理的社 区结构，并准确发现社区的进化过程。 ( 3 )社区的进化类型划分不够合理。很多时候社区变化是复合的，很难单用增 大、缩小、合并、分解等方式进行准确描述。此外，社区的进化类型的界 定过于绝对，没有充分考虑社区中变化部分和静止部分对社区变化类型的 影响。 在现有研究的毖砒上，本文提出了一种改进的关联网络发现方法，引入社区 层次结构，并在社i x 结构层次结构的基础上，寻找社区的进化过程，通过考虑质 变i 冒变的关系，发现涌现的社i 錾：结构。本文研究的主要工作包括这样几个方面： ( 1 )分析现有社区提取方法和现有社区进化发现方法，针对存在的一些不足， 提 j 了一个关联网络的j 叶= 区发现框架。 ( 2 ) 研究了社区层次结构的发现方法。 ( 3 ) 提出了基于社区层次结构的社区进化发现方法，定义了社区进化类型及度 量方法。 ( 4 ) 构建一个关联网络，并用本文提出的方法对该网络进行社区发现，从而验 证本文方法的可行性及有效性。 1 4研究意义和创新点 社区是网络的缩影，是理解网络结构和分析网络性质的基础。社区发现研究 对分析网络结构性质以及整个网络的动态趋势等等具有重要意义，它可以为实现 网络结构优化、资源搜索、资源推荐等提供方法。本文的研究工作具有一定理论 价值和l 、t 川意义： ( 1 )理论意义。 刚络统计特性研究一直是众多研究者关注的课题。网络的宏观特性基于整个 网络，微观特性基于网络中的节点。社区结构是一种介于宏观和微观之间的网络 特性，反映了网络的结构和功能之间的关系，社区的变化体现了整个网络动向的 某些方面。社区之间有的相互独立，有的相互重叠；网络的社区结构呈现出层次 特性。发现社区的层次结构以及各个社区的变化过程，对于分析网络结构特性， 理解节点在网络中的作用以及节点之间的关系，起着不可或缺的作用。 6 第1 章引言 ( 2 ) 应用意义。 关联网络是对相互关联的实体集合及其关系的一种抽象表示。这种表述方法 被用在多种系统的分析研究中，如w w w 、对等网络、科学家合作网络、引文网 络、股票关联网络、蛋白质关系网络、神经网络等等。社区发现具有广泛的应用 范畴，可以为实现网络结构优化、高效资源搜索、个性化资源推荐、领域发展分 析预测等等提供方法。 本文主要的创新点包括： ( 1 ) 引入社区层次结构对关联网络中的各个社区进行组织，并设计社区层次结 构的发现方法。 ( 2 ) 在社区层次结构的基础上进行社区进化发现，定义了社区进化的类型以及 度量标准。 ( 3 ) 构建d b l p 文献标题单词关联网络，通过发现单词关联网络的社区结构， 在一定程度上揭示计算机领域的相关研究话题及其变化情况。 1 5论文结构 本论文共六章。分别如下： 第一章为论文的绪论，简述了论文研究内容的发展现状以及论文所作工作的 创新性； 第二章为论文研究采用的相关理论，介绍了本研究所涉及的相关理论，包括 关联网络，社区，派系过滤方法和本体理论等等； 第三章给出了关联网络的社区发现的体系结构，主要对社区发现的总体框架 和具体工作进行阐述，并对相关概念进行形式化定义； 第四章分别就社区层次结构发现和社区进化过程的发现方法分别进行了深入 详细的介绍。 第五章为实验系统及实验评估，通过构建单词关联网络进行社区发现，检验 本文提出的方法； 第六章为全文的总结与未来工作展望。 第2 章相关理论 第2 章相关理论 本章主要简要介绍关联网络的社区发现的褶关理论，包括关联网络的基本 概念、形式化表示、类型、拓扑性质，社区的概念和性质，派系过滤方法的原 理以及本体理论等等。 2 1关联网络 2 1 1 基本概念 现实生活中，涉及多个体和多个体相互作用的系统都可以抽象为关联网络， 其中每一个个体对应网络的一个节点，个体之间的联系或相互作用对应连接节 点的边，如w w w 、对等网络、科学家合作网络、引文网络、股票关联网络、 蛋白质关系网络、神经网络等等。关联网络可以用图的形式表示g = 彤助，其 中，矿表示节点集，e 表示边集。e 中每条边都有v 中的一对节点与之对应。 a c 霉b 舔 露d 静 图2 1不同类型的关联网络 a 无向网络b 有向网络c 加权网络d 异质网络 根据e 和v 的性质，关联网络有多种划分方式( 见图2 1 ) 。如果任意符点 对( f ，) 与( ，0 对应同一条边，则称该关联网络为无向网络( u n d i r e c t e dn e t w o r k ) ： 否则，称之为有向网络( d i r e c t e dn e t w o r k ) 。典型的无向网络有：合作网络、i u 话通话网络、单词搭配网络、电力网、铁路网等等：典型的有向网络有：w w w 、 引文网络、食物链网络、邮件投递网络、神经网络等等。e 每条边都可以用某 9 婀南人! 孚：硕十学停论文 j i 。与楷盹进 j ：标u ，如灭i l j 的类型、权重等等。如果对每条边赋予一个权值，则 称陔关联网络为加秘网络( w e i g h t e dn e t w o r k ) ；否则，称之为无权网络 ( u n w e i g h t e dn e t w o r k ) ，无权网络也可以看作等权网络。权值的大小表示关联 的程度。例如，在合作网络中，权值表示个体间合作的次数；在神经网络中， 权值表示神经元间的作用的强弱。有的关联网络包含多种不同类型的节点和边。 例如，在数据网络( w e bo fd a t a ) 包含来自不同数据集的各类资源和多种关系 类型，网络中的一个节点代表一个资源，节点间的边代表资源之间的r d f 链 ( r d fl i n k ) 。这类网络称为异构网络( h e t e r o g e n e o u sn e t w o r k ) 。 2 1 2 相关特性 大量研究发现，关联网络具有与随机网络不同的结构特征。 l 小世界效应( s m a l l w o r l de f f e c t ) 般来说，关联例络具有小世界效应。尽管网络的规模巨大，网络的平均 路禾f ：k 度却j 怍常r r - j 4 , 。网络的平均长度定义为网络中任意弧个节点之间的距离 的- 、r 均值， 扛南吾叱 西，表示节点i 和节点j 的距离，为连接两节点的最短路径上的边数。 小世界论断最早是由匈牙利作家ek a r i n t h y 于1 9 2 9 年提出的。他认为，地 球上的任何两个人都可以通过一条平均由六位联系人组成的连线联系起来 【4 3 】。1 9 6 7 年，美国哈佛大学的社会心理学家m i l g r a m 利用连锁信件实验，证 实了社会网络的小世界特性，正式提出了著名的“六度分离 理论( s i xd e g r e e s o fs e p a r a t i o n ) 4 5 。他从招募到的志愿者重随机选择出三百多名，请他们通过 认谚 的人，用他们认为最少传递的次数，将邮寄转寄给某个股票经济人。出人 意料的足，有六十多封信最终到达了指定目标，并且这些信函经过的中间人的 、 ，均数门只有5 个。也就是说，世界上任意两个陌生人之间的平均距离是6 。 此后，人们还仗丹j 了其他的方法来检验“六度分离”的假说。t j a d e n 和 w a s s o n ( 1 9 9 7 ) 设计的k e v i nb a c o n 游戏 4 6 ，通过计算k e v i nb a c o n 数，验证了 电影演员合作网络中的小世界特性。一个演员的b a c o n 数( b a c o nn u m b e r ) 为 该演员到k e v i nb a c o n 的最短路径长度。如果一个演员和k e v i nb a c o n 合作过， 则该演员的b a c o n 数为1 ：如果他没有与k e v i nb a c o n 合作过，但与b a c o n 数 为1 的演员合作过，则该演员的b a c o n 数为2 ；如此类推。统计显示，在这个 l o 第2 苹相芙理论 覆盖6 0 万演员以及关于3 0 万部电影的合作关系的电影演员合作例络中，演b ! 最大k e v i nb a c o n 距离为8 ，平均k e v i nb a c o n 数为2 9 4 4 。类似的，奥克? 皇人 学的g r o s s m a n 教授提出的e r d 6 s 数项目( e r d 6 sn u m b e rp r o j e c t ) 4 7 检验了数 学家合作网络的小世界现象。e l m a c i o g l u 等人研究了基于d b l p 数据集构建的 学者合作网络的六度分离现象 4 8 】。 所有这些研究都表明，在庞大的网络中，个体之间的距离实际上是非常 “近”的。“六度分离”试验验证了网络捷径的存在性，即大规模网络的“小世 界特性”。在网络全局信息缺乏的情况下，仅仅利用局部信息就可以找到网络捷 径。 2 聚类特性 关联网络中，一个节点f 通过边和其他岛个节点直接相连，我们称节点f 与这岛个节点相邻。这岛个节点之间往往存在相邻关系。这种属性叫做网络的 聚类特性。例如，在朋友关系网络中，一1 个人的两个朋友很可能彼此也是朋友。 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 是网络的熏要度量参数之一。在无权网络 中，节点z 的聚类系数g 定义为 。2 e ， o2 莉 ，i 凡一ij e f 为与i 相邻的薪个节点闯边的数量。加权网络中，节点f 的聚类系数g 定义为 g 2 南丢掣叩椭 矿g ) 为与节点f 相邻的节点集。网络的聚类系数c 定义为网络中所有节点的 聚类系数的平均值( 见图2 2 ) 。 小。邑晶 00 图2 2 无权网络的聚类系数 显然，如果网络中的所有节点相互孤立，则网络聚类系数为0 ；如果网络中任 伯南大学硕十学何论文 意两个节点相邻，即例络为完全图，则网络聚类系数为l 。对于一个含有n 个 ：饥_ 的e r 随机吲，随肴节点数n 的增大，c = o ( u l 。但事实上，在很多关 联刚络中，随着例络舰模的增加，网络的聚类系数趋近某个非零常数。这意味 营火联网络与随机网络的无序状态截然不同，呈现出“物以类聚、人以群分” 的特点。 3 无尺度( s c a l e f r e e ) 性 网络中，节点的度定义为与该节点相邻的节点的数量。在大规模随机网络 中，节点的度服从正态分布；在规则的网络结构中，节点的度是固定的。以上 两类网络的节点度分布都有规则可循，被称作有尺度的网络。在这些网络中， 节点的度分布在某个范围内，度数远远大于平均度的节点是不存在的。 空 i 咨 c a ) 3 叮 尘 l l d e g r e ek 图2 3e m a i l 网络的节点度分布 5 0 o 大量研究表明，现实生活中的许多关联网络，如w w w 4 9 、e m a i l 网络 5 0 】、 数据包传输网络 5 1 】、合著网络等，其节点度满足幂律分布尸( 七) o ck ，即无尺 度分布( s c a l e f l e ed i s t r i b u t i o n ) 。我们称这些网络为无尺度网络。当节点度分布 满足幂律分布p ( k ) o c 尼，积累度分布函数符合幂指数为y 一1 的幂律。 尸 = p ( k ) o ck 州 k ： 劁2 3 描述了e m a i l 网络中悔点度的分和情况。该网络中，一个节点代表 个e ，m a i l 地址，每条边代表两个e m a i l 之l 、日j 的通信关系。该网络的节点度服 从幂律分布，p 伙) o ek 一一。 难看出，网络大多数节点的度数较小，存在个别 节点度数很大。 第2 章相关理论 2 2社区 l 社会学中的社区 “社区”一词最初来自德国社会学家f t o n n i e s l 8 8 7 年出版的( ( g e m e i n s c h a t t u n dg e s e l l c h a f t ) ) ( 社区与社会) 一书。“g e m e i n s c h a f t ”也可译为社区、社团、 公社、集体、共同体等等，表示任何就