（计算机应用技术专业论文）基于半监督学习的社团划分算法研究.pdf

辽宁师范人学硕十学位论文 摘要 i y l t l t l l l i 7 t l n 95 i n o l 9 l l l 4y 17 9 5 0 9 4 自然界中存在的大量复杂系统都可以通过各种各样的嘲络进行描述。近年来，复杂 网络的研究受到了越来越多的关注，并渗透到从自然科学到： 程科学甚至社会科学的多 个领域。研究所涉及的网络主要有：生命科学领域的各种网络、i n t e r n e t w w w 网络、 交通网络、社会网络、科学家合作网络和语言学网络等等。随着对网络性质的深入研究， 人们发现许多网络具有一个共同的性质一社团结构。诸多学者从不同角度对如何发现网 络中的社团结构问题进行了研究。而当复杂网络中存在已知标记节点时，如何更好的利 用已知标记和未知标记节点训练出优秀的分类器进行社团划分成为了重点问题。而! 仁h f 督学习方法恰恰是针对大量无标记节点集与有标记节点集共同进行训练，以得剑衙p t i j 匕 以及较好泛化能力的学习器。因此，半监督学习的方法能够更好的解决仃往已j m4 c , j i 址1 了 点的复杂网络社团划分i u j 题。本文从半监督学习角度出发提出了鹏种算法，旨4 ：解决叫1 网络中存在有标记节点时的社团划分问题。 基于信息传递模型的划分算法：信息从已知标记节点丌始通过节点问的边在网络巾 进行传播，直到每一个未知标记节点接收到所有已知标记节点的信息为止。然后算法分 析每一个无标记网络所接收的每一类已知标记节点的信息量，最终根据分析结果对每一 个未知标记节点进行标记。信息在传递过程中，为了更好的模拟现实中信号衰减现象， 算法利用信号衰减公式来控制衰减程度。此算法为线性时问复杂度，刚此运行速度较快。 实验结果表明，在对一一些网络进行社团划分时，此算法与g n 、w u h u b e r m a n 、n e w m a n 等算法有着相同的准确率，在个别网络中，其准确率要更高一些。 基于引力模型的划分算法：该算法把节点看作引力实体，然后将物理学中的万仃引 力定律引入社团划分算法中。首先计算已知标记节点与未知标记节点之i 【j j 的引力作川值 的大小，然后分析并比较每个己知标记节点对未知标记节点引力作用值的大小，最后根 据一定的规则将未知标记节点进行标记。在实验中，利用此算法对- 止匕实际网络进行分 析，结果表明虽然运行速度比信息传递模型算法有所下降，f i l 精度有所提商。而与传统 算法柏比，虽然其时i h j 复杂度相对较高，f e i 足精度棚义较高。 本文所提出的两个算法均为半监督学习算法，通过已知标记与未知标记节点孙d 训 练出学习器。运用统计学理论可以证明当无标记节点数量越多时，可以对模型参数“i i 计 越准确，进而提高学习器准确性。算法在局部与整体体现了比较好的一致性，避免了局 部最优化对划分精度的不良影响。通过对实验结果的分析可知，算法在时间和窄f h j 复杂 度方面均比较低，而在准确性方面相对较高。 关键词：复杂网络、社团结构、半监督学习、信息传递、引力模型 “哼t 一 氧： n o d e sa r et h et a r g e t t h ei n f o r m a t i o no fl a b e l e dn o d e sd i s s e m i n a t et ot h e i rn e i g h b o u r sw h i c h m u s tb et h et a r g e t t h ea l g o r i t h mc a n ts t o pu n t i lt h ei n f o r m a t i o no fa l ll a b e l e dn o d e ss p r e a d t o e v e r yu n l a b e l e d n o d e s t h e ne v e r yu n l a b e l e dn o d ec o n t a i n s e v e r yk i n d so fl a b e l i n f o r m a t i o n ，a n dc o m m u n i t ys t r u c t u r ew i l lb ef i n dt h r o u g hc o m p a r i n gq u a n t i t yo fe v e r yk i n d s i n f o r m a t i o n d u r i n gt h e i n f o r m a t i o nd i s s e m i n a t i o np r o c e s s ，t h ea l g o r i t h mc o n t r o l s i g n a l a t t e n u m i o nt os i m u l a t er e a ls i g n a la t t e n u a t i o nt h r o u g ht h ea t t e n u a t i o nf u n c t i o n c l a s s i f i c a t i o n a c c u r a c yo f t h i sa l g o r i t h mi sr e l a t i v e l yh i g h ，t a k i n gu pl e s ss t o r a g e t h es e c o n da l g o r i t h mi sb a s e do nt h eg r a v i t ym o d e l a l ln o d e sa r es e e na sg r a v i t a t i o n a l e n t i t i e sa n dt h el a wo fg r a v i t yi su s e di n t ot h ea l g o r i t h m b yc a l c u l a t i n gt h eg r a v i t a t i o n a m o n ga l ln o d e s ，c o m m u n i t ys t r u c t u r ew i l l b ef o u n d e x p e r i m e n t ss h o wt h a tg r a v i t a t i o n r e d u c e sa st h ed i s t a n c ei n c r e a s e s t h ef a rn o d e sa r ea f f e c t e dw e a k l y ，b u tt h ed i s t a n c ei sn o t t h eu n i q u ef a c t o r a n o t h e rf a c t o ri st h ea t t r a c t i o no fan o d e t h el a r g e ri ti s ，t h es t r o n g e rt h e g r a v i t a t i o ni s t h et w oa l g o r i t h m si nt h i sp a p e rt r a i ng o o dl e a r n e r so nb o t hu n l a b e l e da n dl a b e l e d n o d e s i ti sp r o v e di ns t a t i s t i c st h a tu n l a b e l e dn o d e sc a ni m p r o v et h ea c c u r a c yo ft h el e a r n e r a l g o r i t h m se m b o d yt h el o c a la n dt h eg l o b a lc o n s i s t e n c y ，a v o i d i n gt h el o c a lm a x i m a 7 f h c e x p e r i m e n ts h o w st h a tc o m p l e x i t yo f t h et w oa l g o r i t h m si sr e l a t i v e l yl o w k e y w o r d ：c o m p l e xn e t w o r k ；c o m m u n i t ys t r u c t u r e ；s e m i s u p e r v i s e dl e a r n i n g ； i n f o r m a t i o nt r a n s f e r ；g r a v i t ym o d e l i i 何论文 i 。i i l 1 1 1 ：! ：2 6 6 1 3 2 社团结构划分7 1 4 本文研究的主要内容一l o 1 5 文章组织结构l o 2 社团划分经典算法12 2 1 社团结构划分算法1 2 2 1 1k e r nig h a n lin 算法12 2 1 2 谱评分法1 2 2 1 3 w u - h u b e r m a n 算法1 3 2 1 4g n 算法l4 2 1 5n e w m e n 快速算法15 2 1 6k 均值算法15 3 信息传递算法17 3 1 基本思想17 3 2 算法描述18 3 3 实验及分析19 3 3 1z a c h a r y 宅手道俱乐部关系网络：1 9 3 3 2 大学足球网络2 2 3 3 3 科学家合作网2 3 4 引力模型算法2 5 4 1 基本思想2 5 4 2 算法描述2 6 4 3 实验与分析2 7 基丁半监督学习的社团划分算法研究 4 3 1 二三社团网络2 7 4 3 2z a c h a r y 网络2 9 4 3 3 大学足球网络3 l 结论3 3 攻读硕士学位期间发表学术论文情况一3 4 一 参考文献3 5 致谢4 0 辽j 。师范人学硕卜学位论文 1绪论 1 1 问题的背景 自然界中存在的大量复杂系统都可以通过各种各样的网络进行描述，例如，社会学 中的人际关系网络、生物学中的蛋白质网络、交通网络等。网络与人类发展有着密f i 可 分的关系，因此对这些复杂网络的性质与功能进行研究就显得相当重要。随着科技的进 步，人们对复杂网络的研究变得越来越深入。复杂网络中社团结构作为研究复杂网络几 大重要分支之一，越来越受到人们的重视。在研究过程中，诸多学者提出了许多卡 = | 卅结 构划分的算法。而在传统的社团结构划分中，网络中的节点没有类标记，因此很多的= i ： ： 团划分算法都足针对这一特点提出的，它们属于无监督学刊的范畴。当网络t ，出王见l 知 标记的节点时，传统的社团结构划分算法已经i 、= 能很好的解决这一一类问题，而这时我们 需要提出一种基于半监督学习的算法来解决网络中存在已知类标记节点时的社闭划分 问题。 1 2 半监督学习 半监督学习的基本思想是介于有监督学习和无监督学习之间。有 l f 督学爿 ( s u p e r v i s e d e a r n i n g ) ：用已知类别的样本训练分类器，以求对训练集数据达到某种 最优，并能够对新数据的分类：无监督学习( u n s u p e r v i s e dl e a r n i n g ) ：样本数抓类 别未知，需要根据样本问的相似性对样本集进行分类( 聚类，c l u s t e r i n g ) 。- i i 数据集中 同时出现已知类别和未知类别的数据时，就需要运用半监督学习的思想，即同h 埒u h j 已 知类别和未知类别的数据训练分类器。 1 2 1 起源 普遍认为，半监督学习的相关研究始于b s h a h s h a h a n i 和d l a n d g r e b e 的i ：作。 d j m ill e r 和h s u y a rp i 认为，由于当时的机器学爿领域中主流技术对九标签数捌 的考虑相对困难，因此才使得半监督学习的研究起步棚对较晚。随着数据采集和打储技 术的高速发展，收集大量无类别标记的数据已经变得相当容易，而获得已知类别枷：记的 数据则变得相对困难。例如在计算机辅助医学图像分析中，可以从医院获得人鞋的医学 图像作为训练例，但如果要求医学专家把这些图像中的病灶都标识出来，则 往足f it 叮 能完成的任务。在现实世界中，绝大多数问题通常存在大量的末标记数拂0 而有标址数 据则比较少。例如，在进行淘宅网宝贝收藏时，需要用户收藏哪止匕宝贝是他感兴趣的， 但是很少会有用户愿意花大量的时间来提供收藏，因此有收减标汜的襄贝比较少，f i 淘 宝网上存在着无数的未收臧宝贝，它们都可作为未标圯数据来使用。随着利用未标址j 例这一需求的日渐强烈，半监督学习才在近年来逐渐成为一个研究热点。 基丁斗，监督习的社团划分算法研究 1 2 2 半监督学习中未知标记数据的价值 由于仪仅利用已知标记的节点或者数据很难训练出性能好的学习器，因此一止匕学者 早在上世纪8 0 年代末，就注意到了无标记数据的价值【列。他们针对未标记节点或者数据 是否能帮助提高学 - - j 器的性能做了一些分析。例如，d j m i l l e r t f l i h s u y a r1 7 2 1 从数据分 布估计的角度给出了一个直观的分析。 半监督学习的基本假设：给定一个来自某未知分布的有标记数据集 l = ( x - ，y 一) ，( 石z ，y ：) ，( 一。 ，y l 。1 ) ) 以及一个未标记数据集u = x ：，x ；，x i ，p ，通过学爿 得到函粉x 一】，期望可以准确地对数据x 预测其标记y 。这罩x ，x 。，x 均为d 维向 量，y ，y 为数据x ，的标记，h 和l 【，1 分别为l 和u 的大小，即它们所包含的示例数。 假设所有数据服从于由上个高斯分布混合而成的分布，即 ， f ( xl 口) = 口，f ( xb ) ( 1 1 ) ，= l 正 其中口，= 1 为混合系数，0 = 岛) 为参数。这样，标记就一叮视为一个“ 选定的混合成分 = i m ，和特征向量x ，以概率尸= ( c ，ix im ，) 决定的随机变量。于是，根据最大后验概率似设， 最优分类由式1 2 给出： 办( x ) = a r gm a x ，p ( c ，= km ，= _ ，x ，) 尸( m ，= jx i ) ( 1 2 ) 其中p ( m ，= jx 。) = 口，f ( x ，lo j ) a ，f ( x ，l 研) 1 = 1 这样，学习目标就变成了利用训练例来估计p ( c ，= km ，= ，x ，) 和p ( m ，= jx ，) 。这 两项中的第一项与类别标记有关，而第二项并不依赖于示例的标汜，因此，如果订人畦 的未标记示例可用，则意味着能够用于估计第二项的示例数显著增多，这会使得第：项 的估计变得更加准确，从而导致式2 更加准确，也就是说，分类器的泛化能力得以提高。 此后，t z h a n g 和f j o l e s1 7 3 1 进一步分析了未标记示例在半监督学 - j 中的价值，并指 h 如果一个参数化模型如果能够分解成p ( x ，y0 ) = p ( yix ，o ) p ( x0 ) 的形式，那么木标记 示例的价值就体现在它们能够帮助更好地估计模型参数从而导致模型性能的提高。 1 2 3 半监督学习算法的种类 根据学习模式n 丁以将半监督学习分为：主动式半监督学习和被动式、扛监督学爿。 j 动式半j i f 督学习是指半监督学习算法采用主动式的学习模式，在整个的学爿过程中，鲐： 法仅仅使用有类别标记和无类别标记的训练数据集，而不涉及训练数据集之外的新数 据。例如早期的基丁图的方法，往往是主动式的半监督学习。相反的，被动式半监饼学 辽j 。师范人学硕 ：学位论文 习算法则是采用被动式的学习模式，在整个学习过程中，算法既使用训纫：数掂集也使j j 新数据。例如主动式支持向量机( t s v m s ) ，由于最终的分类器被定义在整个的数捌窄 间，所以它实际上是一种被动式的半监督学习。 半监督学习算法按照工作方式可分为四类：生成式模型算法、自我训练算法、协同 训练算法和基于图的算法。 ( 1 ) 生成式模型算法 生成式模型算法是早期的半监督学习算法【4 1 ，它假设一个模，理： p ( x ，y ) = p ( y ) p ( x l y ) ，其中p ( x i y ) 为可识别的混合分布，例如高斯分布。当未知标汜 的数据量变得很大时，分布中的每一个混合成份将能够被谚 别。存在个理想状态：舀： 每一个混合成分中我们仅仅需要一个已知标记的数据就能完全准确地计算h 棚j 妊的概 率分布。 在生成式模型算法中有几个比较关键的j u j 题：模型的可谚 别性、模型假设的旷确性、 e m 局部最大化问题、使用聚类算法代替生成式模型算法的问题和数掘集转化 u j 题。 模型的可识别性：是指在理想状态下混合模型可以被识别或者说是具有识别能力 的。一般的， p 目) 是一族分布，口是参数向量。如果o i 0 2jp 8 p 融则口为可识别的。 如果模型是可识别的，那么理论上我们可以通过学习目得到混合分布哏的每一个成分。 r a t s a b y 与v e n k a t e s h 、c o r d u n e a n u 与j a a k k o l a 做了一些关于半j ：i 督学习【j 丁i , x 另i j 。 ，t 的研 究f5 1 。 模型假设的正确性：早在1 9 9 5 年，c a s t e l l i 等人就对模型的i f 确性进行了系列的 讨论 4 j 1 6 j 1 7j ，他们指出：如果一个混合模型的假设是币确的，那么无类标记数据就会提 高学习器的精度，反之则会降低学习器的精度。另外，被组建的混合模型是行能反映客 观事实也是相当重要的，例如在文本聚类中，一个标题i 叮能包含多个子标题，冈此建沈 一个多项式模型要比单项式模型效果好得到引。 e m 局部最人化：根据生成式模型算法理论可知混合模型中的每个成分足被e m 算 法所谚 别的1 9 】。尽管当一个混合模型的假设是m 确的，但未知类标记数据未必会捉岛学 习器的精度。分析其原冈可知：e m 算法倾向于局部最大化，如果局部最人化j 个。0 最 大化相差很大，这时未知类标记数据可能会再次降低学习器的精度。 使用聚类算法代替生成式模型算法：我们也可以不使用生成式混合模型这种方 法，而是采用其他一些聚类算法对整个数据集进行聚类，最后使用已知类标址数抓埘每 个簇进行标记【1 0 】【l lj 。当这些聚类算法与真实数据分布相匹配时，它们的结果通常很令人 满意。由于这类方法不同于生成式模型算法，它们并没有给出一个具体的模型假设，i 大j 此我们很难分析这些特殊算法的性质。 数据集转化：生成式模型方法中的另一类算法是通过， ：成式模，艘将原数捌转化为 系列新的特征表现，然后将他们带入一个标准的分类器中进行分类。h o l u b 等人将这 基丁半监督学习的社团划分算法研究 一方法应用到了图像分类中【1 2 】。首先训练一个生成式模型，每一个混合成分属于一个类 别，这时应用e m 算法将无类标记数据合并；然后这个方法并不使用，七成式模型进行分 类，而是将每一个被标记数据转化为一个固定长度的f i s h e r 评分向量( 对数似然度的派 生物) ，最后将这些向量带入一个有判别力的分类器中进行分类，例如s v m 。 ( 2 ) 自我训练算法 自我训练方法是半监督学习中很普遍的一个方法。在自我训练过程中，首先使用 小部分己知类标记数据训练一个分类器，然后使用这个分类器对未知类标记数据进行分 类。置信度高的未知类标记数据和他们的预测类标记被一起加入训练集中，之后分类器 重新训练，如此重复下去。但是当错误地选择了未知类标 己数据或者类标记产生分类误 差时，在反复训练的过程中这个误差很可能会被扩大。为了避免分类误蔗的发乍，+ i j f s 芒 者试图寻找有一些方法避免这样的情况发生，例如算法含弃某些预测。- ，j 信度低于某闽 值的数据点来避免误差的产生或扩大。 自我训练方法有着广泛的应用。例如在一些自然语言处理工作中，y a r o w s k y 把它应 用到了语言辨别解疑( w o r ds e n s ed i s a m b i g u a t i o n ) c t b j ，例如，在给定j ：下文的情况f 辨别单词“p l a n t ”的含义到底是生命有机体还是一个工厂。r i l o 鹧人运用它上识别j i 观名词l | 4 】；为了判断一段对话属于有情感的类别还是无情感的类别，m a e i r e i z o 等人利j j 自我训练方法对所有数据进行情感分类【l5 1 。自我训练方法还被应用到了分析与计算机翻 译领域。图像物体探测系统中，基于半监督学习技术的自我训练方法s t a t e o f - t h e a r t 探 测器性能不相上下l i6 | 。 虽然自我训练算法中的许多技术很难进行定性或者定最的分析，但是对于一些特殊 的学习器，仍然可以进行一些关于收敛性的理论分析【1 7 1 1 1 8 i 。 ( 3 ) 协同训练算法 最初的协同训练算法( 或称为标准协同训练算法) 是a b l u m 和t m i t c h e l l 在1 9 9 8 d - 提 的。他们提出了协同训练中的三个假设f j9 j 特征集i ，丁以被分为两个子集，即允分= ，c 余视图每一个特征子集都能够训练出一个性能很好的分类器给定类别时，两个j 厂集 条件独立。他们发现充分冗余视图的三个条件在很多任务中是可以满足的。例如，布：给 一种商品进行优劣分类时，可以根据商品本身的各项参数属性进j ，分类，同时也可以根 据其他使用者对它的评价进行分类，这样的商晶数据就有两个充分冗余视图，第一个视 图为商品本身包含信息的属性集，第二个视图为其他人对它评价的属性集。他们提的 算法首先在两个视图上利用有标记数据分另j j i ) l l 练出一个分类器，然后在协同训练过程 中，每个分类器从未标记示例中挑选出若干标记置信度( 即对数据赋予i f 确标记的胃信 度) 较高的数据进行标记，并把标记后的数据加入另一个分类器的有标记训练集中，以 便对方可以利用这些新标记的数据进行更新。协同训练是一个迭代的过程，直到达到某 个停止条件。 辽r j 。师范人学硕十学佗论文 n i g a m 和g h a n i 将协同训练算法与生成式混合模型算法和e m 算法进行比较| 2 0 1 ，他 们发现如果条件独立假设确实充分，协同训练算法实验结果更好。另外他们还发现如果 使用某种概率分布对整个无标记数据集进行标记要比仪对个别置信度高的数掘进行标 记效果要更好。他们把这种方法称为协同e m 算法( c o e m ) 。c o l l i n s 和s i n g e r 以及j o n e s 将协m i ) l l 练算法、协同e m 算法应用到了文本信息提取问题中【2 2 1 。b a l c a n 和b l u m 指 出，在这种仅仅使用一个有标记数据进行分类的极端条件下，协同训练往往更为有效【2 引。 z h o u 等人于2 0 0 7 年提出了一种基于典范相关分析( c a n o n i c a lc o r r e l a t i o na n a l y s i s ) 的 协同训练算法1 2 4 j 。 ( 4 ) 基于图的方法 基于图的方法首先定义一个图，其中节点代表数据集中的已知标记和未知标记数 据，边代表了数据之间的相似度。这类方法假设标记在整个图f ：是甲滑的力：一l r t 它具备厂 无参数、有判别力和主动式学习等特点。许多基于图的方法可以看作足在一个图f ：评估 一个函数厂的过程。人们希望函数f 同时满足两个条件：1 ) 在己知标记钌点j ：，它应 该是接近标记y ，的，2 ) 在整个图上，它应该是平滑的。 在基于图的算法可以采用不同的衰减函数和j 下则化项，其中比较著名的方法何： 基于m i n c u t 的半监督学习算法：b l u m 和c h a w l a 在2 0 0 1 年提j h 该算法| 2 5 i ，他们将半 监督学习看作是图分割问题。在二元事件中，j 下标签节点为源头，负标签节点为，目标； 这一方法的目的是找到一个最小边集合，当集合中的所有边都移除时，就完令阻碍了源 头节点与目标节点之间的连接。这时，与源头节点相连的节点标记为正，与r 标：钳点相 连的节点标汜为负。m i n c u t 算法存在一个问题：它仅仪给出了硬性分类，并没订给 十h 应的筲信度。后人对其做了适当的改进并应用剑很多问题中。例如：b l u m 等人通过义寸边 权值加入随机噪声对图进行扰动的方法对m i n c u t 算法进行改进【2 引。p a n g ) f t ll e e 则将 m i n c u t 算法应用到对句子主客观分类问题中并对原始算法进行改进，他假设棚邻的句f 更可能具有相同的类别l z7 1 。 谐函数方法：由于计算离散马尔可夫随机域的边缘概率是一种很网难的办法。人| 此一些研究者使用高斯随机域和谐函数| 28 】代臀离散马尔可夫随机域进而降低计算难度。 它被看作是具有无穷大权值的二次损耗函数。g r a d y 和f u n k a l e a 将谐函数方法引入剑多 媒体图像分割中1 2 9 1 ，用户可以使用少量的点击将图像中不同的组织分类。l e v i n 等人使 用等价的谐踊数将灰度图像转化为彩色图像【3 0 1 ，用户同样只需要少最对劁像的点击即- ， 得到需要的颜色。在转化过程中图像其余部分被视为未知标记数据并且标记通过| ! j 5 j 像进 行传播。基于协函数的标记传播算法被n i u 等人应用到了语言辨别问题中【3 1 l 。在电影分 级预测中，g o l d b c r g 和z h u 运用这个算法对影片中人物语言4 情感和态度进行了分析【3 2 l 。 其他一些方法：这类方法都是都采用不同的损耗函数和诉则化项来进行半监督学 习。例如：局部与全局一致性方法f 3 3 】、t i k h o n o v i l ( 贝q 化力法1 3 4 1 、多样式i t ! n 化方法1 3 5 儿3 6 1 。 基丁半监督学习的卒十团划分算法研究 s i n d h w a n i 等人给出了个半监督核函数1 3 ，它并不受未知标记数击| i j 的限制，而是被定 义在r 整个输入数据空问上，因此它具备了应付新数据的能力。可以说这个核函数是多 样工i i j ! l l l j 化方法的令新诠释。 许多基于图的半监督学习算法都属于主动性学习算法，它们很难扩展到已知标记数 捌集与未知标 已数捌集以外的数据。近些年来，这个f 廿j 题逐步得到了学者们的重视，通 常做法是：将整个图同定在已知标记数据集与未知标记数据集上，这样一来新加入的节 点则4 i 能改变原有图的结构，因此更容易对这些新加入的节点进行分析。2 0 0 3 年z h u 等人提出利用新节点在原图中的邻居进行分类1 38 1 。如果无标记数据集足够大，那么这种 做法是卜分适合的。c h a p e l l e 提出利用一个有标记节点与无标记节点的线性组合来近似 一个新节点的方法p9 | ，类似的，d e l a l l e a u 等人在2 0 0 5 年提出通过新节点的相邻节点类 别术确定新节点的类别1 4 。 半监督学习方法在许多领域中都有着广泛的应用，在复杂网络社团划分中也不例 外。传统的复杂网络中节点是由现实中的数据抽象而成，这些数据均为无类标记数据。 连接它们的边代表着数据f p l j 的某种相似性度量。而当用来构成复杂网络的数掘集中存在 少谴l 二知类标址数据时，相应的复杂网络中的某些节点也同样具有类标记，那么这时半 j 僻学习方法的思想，能够更好的帮助我们解决存在已知类标记节点的网络社团划分问 题。测此本文提出了新的基于半监督学习的社团划分算法，来解决存在已知标记节点的 嘲络社团划分| l j j 题。为了更好的理解新方法的特性以及与传统社团划分算法存在的区 别，小文将伍下一竹以及第二章重点介绍传统复杂网络社划分问题和一些经典算法。 1 3 复杂网络及其社团结构划分 1 3 1 复杂网络的起源与发展 随着复杂网络越来越受到人们的重视，使得学者们开始广泛关注网络结构的复杂性 及其与网络行为之间的关系。图作为一种数学工具被用来研究复杂网络一些重要的性 质。每个网络都呵以看作是由一些节点以及连接它们的边组成的系统。用图抽象的表 力网络，就足j l l i t t 象的点表示实际网络中的节点，并用节点之l 白j 的连线来表示实际网络 。 11 了t i 之f h j 的迮接关系。 图的研究起源f1 8t j = 纪的数学家欧拉对七桥问题的研究。欧拉对七桥问题进行了 一一系列的抽象和沦证，从此丌创了数学中的一个分支一图论。因此，后人称欧拉为图论 之父。 似足在欧：f 覆解决七桥问题之后，图沦并未获得足够的研究与发展。图论的第一部号 著“到1 9 3 6 年j 。被出版，此后图沦丌始逐步发展起来。2 0 世纪6 0 年代，由两位匈牙利 数学家e r d o s 和r o n y i 建立的随机图理论被公认为是在数学上开创了复杂网络理论的系 统陀研究f 4 1 1 1 42 | 。 辽j 。师范人学硕十。z 位论文 2 0 世纪6 0 年代以来，随机图理论一直是研究复杂网络结构的基本理论。但是绝人 多数实际的网络结构并不是完全随机的。例如，社会网络中的人际关系，i n t e r n e tj ：网 页之间的链接等都不会是完全随机的。直到2 0 世纪末，人们对复杂网络的研究发乍了 重要的转变，复杂网络理论研究也不再局限于数学领域。节点数最更多、连结构更加复 杂的现实中的网络逐渐成为研究的主要对象。从此复杂网络的研究侄物理学、尘物学以 及其他众多学科中逐渐变得深入和广泛。 有两篇非常经典的论文被学者们看作是复杂网络研究的新纪元：一篇是美圈康奈尔 大学理论和应用力学系的博士生w a t t s 及其导师、非线性动力学专家s t r o g a t z 教授于 1 9 9 8 年6 月在n a t u r e 杂志上发表的题为c o l l e c t i v ed y n a m i c so f s m a l l w o r l d n e t w o r k s 的文章1 4 3 j ；另一篇是美国n o t r ed a m e 大学物理系的b a r a b a s i 教授及其搏_ j j 生a 1 b e r t 与1 9 9 9 年1 0 月在s c i e n c e 杂志上发表的题为 e m e r g e n c eo fs c a li n gi n r a n d o mn e t w o r k 的文章1 44 l 。这两篇文章分别揭示了复杂网络的小世界特征和尤标度陀 质，并建立了相应的模型以阐述这螳特性的产生机理。 1 3 2 社团结构划分 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际嘲络都存在 一些彼此性质相似并相互聚集的点群，即社团结构。每个群内部节点之间的连接千h 对紧 密，但是各个群之间的连接相对稀疏。 7 一般来说，社团是由点群组成，而众多社团构成了复杂网络。例如，w w w 可以石 成是山大量网站社团组成，其中同一个社团内部的各个网站所讨论的都足。吵唔仃共m 必 趣的活题【4 5 1 1 4 6 】1 4 7 】。类似地，在生物网络或者电路网络中，i 叫样町以将各个节点根圳其 不同的性质划分为不同的社团【4 8 】【4 9 j 【50 l 。揭示网络中的社团结构，对于了解网络结构1j 分析网络特性都足很重要的。社团结构分析在生物学、物理学、计算机图形学和社会学 中都有广泛的应用5 2 1 。万 、李社团结构划分问题中有三类算法：延i 夕割 图，琵房 割笪法柴冱壬i 士敛加图磁学咀的弓_ 卜割山旧 图分割问题主要碜毽的是如何将一个图划分成事先给定大小的几个群，使雀 群州的 最小化而群内的饺犁最大化。它在并行计算、电路分割以及版面设计领域发挥赣1 f ! 要的作用。一般情移己下找到这类图形分割 u 题的精确解是一个n p 难题。冈此，当 图的规模很大时不存在有效的精确解。但是，有很多试探性算法在多数情况l 卜町以得剑 满意解。其中经典的算法有： ( ! ) k e r n i g h a n - l i n 算法【5 3 】：k e r n i g h a n l i n 算法是一种试探性优化法。它足一种堪 于贪婪算法原理将网络划分为两个大小已知的社团的二分法。其基本思想是为网络的划 基丁半监督学习的社团划分算法研究 分，j | 进个增益函数q ，定义为两个社团内部的边数与连接两个社团之问的边数之差， 然后寻找使q 值最人的划分方法。该算法要求必须事先知道网络的两个社团大小，否则 很【t j 能f i 会得到正确的结果。k e r n i g h a n l i n 算法的这个缺陷使得它在实际网络分析中 社川内部的节点对应的元素通常是近似相等的。该算法根据这一原理将网络中的社团结 构划分出来。 最人流域小割方法【，7 j f o r d 和f u l k e r s o n 于1 9 5 6 年指出在一个网络中，任意一个源 点与汇点之| 日j 的最小割集等于它们之间的最大流。一个网络中节点s 为源节点，节点t 为 汇1 了点。最小割集是边的最小集合，这个集合中元素为连接s 和t 的路径上的边，当将这 个集合中的所有边从网络中删除，s 与t 之间的连接完全断开。我们可以利用求出最大流 的方法得到最小的边集，这样就町以将嘲络化分为两个社团结构。f l a k e 等人分别在2 0 0 0 年年【j 2 0 0 2 年利刚最大流方法米划分w w w 网络中的社团结构，w e b 嘲是有向网络，但是 为了计算方便作者将w e b 网简化为无向网络j 【59 1 。 j 二图形分：孥0 方法需要预先设定社团数量与社团大小，因此对于某些社团结构的划 分米砂f 不足十分适用。我们往往希望一个算法能够在社团划分结束时提供给我们社团数 量l 二以及何个社团的节点数量等信息。 ( 2 ) 分级聚类算法 在通常情况下，一个网络的社团数量、社团内节点的数量以及节点之问的关系足未 知的。冈此人们在使用基于图形分割的算法进行社团结构划分时就要为社团数量以及大 小寻找合理的假发，但这些假设住很多时候是不合情理的。然而一个网络极有可能存在 分级结构，这科，结构通常表现为有层次的节点聚类，小的点群包含在更大的点群中，一 级包含一级。例如社会学网络通常包含这种分级结构，这是人们可以使用社会学中的分 级聚炎算法16 0 j ，来寻找网络中的社团结构。 任意一种分级聚类方法的出发点是预先定义节点问的相似性度量，然后可以通过该 度蹬计算任意节点对之问的相似性。分级聚类是寻找社会网络中社团结构的一类传统算 法。它是基于各个节点之| 日j 连接的相似性或者强度，把网络自然地划分为若干子群。该 类算法有可以分为两大类：分裂方法和凝聚方法。 分裂方法：，试图从已知例络中找到已连接的相似性最低的节点对，然后移除连接 它们的边。重复这个过程，逐步把整个网络分成越来越小的各个部分。该方法可以在任 何情况卜 终止，并且把此状态下的网络看作若干网络社团的集合。 在这类方法中，著名的算法是g n 算法【5 ，它的基本思想是逐渐从网络中移除介数 e k l 、 辽j 。师范人学硕十学1 1 ：7 = 论文 最大的边，直到每一个节点都退化成一个独立社团为止。边介数定义为网络中经过每条 边的最短路径的数目。它为区分一个社团的内部边和连接社团之间的边提供了一种何效 的度量标准。g n 算法弥补了一些传统算法的不足，近几年来己成为社团结构分析的一 种标准算法 6 1 1 6 2 1 1 6 3j 。但是g n 算法存在两个缺陷，第一个缺陷是它对于网络的社团结构 并没有一个量的定义。因此，不能直接从网络的结构判断它所求得的社团是7 i 是实际网 络中的社团结构。第二个缺陷是在社团数目未知的情况下，g n 算法f i 能判断谯哪，。步 停止。为了解决这个问题，n e w m a n 等人引进了一个衡量网络划分质黾的标准一模块度 1 6 4 1 。我们u 以计算出算法每一步划分的社团对应的模块度值的人小，当模块度达到局邢 峰值时，对应着比较好的划分。 r a d i c c h i 等人针对g n 算法的两个缺陷提出了一种新的方法，称为自包含g n 算法 ( s e l f - c o n a i n e dg na l g o r i t h m ) 1 6 5 1 。他们提出了一种社团结构的衡量标准，即强社团结 构和弱社团结构，同时也为g n 算法提供了一种白包含的工具。自包含g n 算法i - j g n 算 法的效果相当，但是计算速度却有了较大的提高。后来研究者们相继在g n 算法犟础上 提出了不同的改进算法，例如：基于相异性的算法【6 6 】和基于信息中心度的算法1 6 7 1 。 凝聚方法：它的基本思想是首先将网络中每一个节点看作独立的社团，再川某种 方法计算出各节点对之间的相似性，然后从相似性最高的节点对丌始，逐步川边l i j 连。 这个过程直到所有的节点构成同一个社团为止，再运用前文捉到的模块度来衡f ； = 划分效 果，找到最适合的划分结果 基于一系列相似性度量标准的凝聚方法已经应用于许多f i 同的网络。现实中仃螳 网络本身就包含相似度标准。比如，在电影演员合作网络中，如果两个电影演员现存 同一部电影中他们之间就有一条边相连。这样，就可以用有多少电影演员川时出j 现行邛可 一部电影中来度量节点的相似性。而另外一些网络虽然其本身并没有相似度标准，但足 可以利用某些方法来设计适当的度量标准，例如：相关系数、路径长度或者一些矩阵的 方法。b r e i g e r 等人提出的c o n c o r 算法就是一种典型的凝聚式的聚类方法。 g n 算法虽然精确度比较高，分析社团结构的效果比原有的一些算法也要好，化足 他的算法复杂度还是比较大的，因此仅仅局限于研究中等规模的复杂网络。基于这个原 因，n e w m a n 在g n 算法的基础上提出了一种快速算法【6 4 1 ，它可以用于分析节点数达1 0 0 万的复杂网络。这种快速算法实际上是基于贪婪算法思想的一种凝聚算法，首先将网络 初始化为n 个社团，也就是说每个节点就是一个独立社团。然后依次合并存在边相连接 的社团对，并计算合并后的模块度增量。重复此过程知道整个网络都合并成为一个社| ；j j 。 此算法在计算时间上比起g n 算法有了很大的改善。 c l a u s e t 、n e w m a n 币n m o o r e 等人在n e w m a n 快速算法的基础上采用堆的数圳结构来计 算和更新网络的模块度，提出了一种新的贪婪算法，成为c n m 算法1 6 8 1 。由于办：整个算 法的的过程中，模块度仪有一个峰值，因此当模块度增量矩阵巾最人的r 已素郡小丁零以 基r 半监督学习的社团划分算法研究 后，模块度的值就只可能一直下降了。所以，只要模块度增量矩阵中最大的元素由j 下变 到负以后，就可以停止合并，并认为此事的社团结构就是网络的社团结构。由于采用了 堆这种数据结构，因此该算法比起原来的n e w m a n 算法来说，计算速度上有很大的提高。