・６０・ 软件导刊 ２０１５正 ＣＰＭ算法是一种派系过滤算法，主要通过寻找Ｋ ｃｌｉｑｕｅ派系社区对社区进行划分。虽然ＣＰＭ能够发现重 叠点，但该算法在实际应用中依赖参数Ｋ的选取，不同Ｋ 值导致划分出来的社区结构有很大差别。因此，在实际应 用中存在一定局限性。同样地，ＥＡＧＩ Ｅ和ＧＣＥ算法是 ＣＰＭ的改进算法，存在同样的局限。 基于合并社区核心和扩展社区的算法需要人为指定 两个参数，这两个参数需要先验知识，和具体网络相关并 影响社区发现结果的好坏。 基于标签传播的算法是一类具有接近线性时间复杂 度的算法，该算法的优点是计算过程简单，计算速度快，而 它的缺点是算法稳定较差，每次运行的结果可能都不一 样。本文提出一种新的标签算法，该算法对ＣＯＰＲＡ算法 的初始化过程和随机选择过程作出了改进，从而大大提高 算法的稳定性。 ２标签传播算法 本文重点对标签传播算法中的ｃＯＰＲＡ算法进行改 进，故简要介绍标签传播思想和ＬＰＡ算法，并分析ＣＯＰ— ＲＡ算法与ＬＰＡ的区别。 ２．１算法思想 标签传播算法最早由ｚｈｕ等 于２００２年提出，是 基于图的半监督学习方法，其基本思想是通过标记节 点的标签信息预测还未标记节点的标签情况。节点之 间的标签传播主要依照标签相似度来进行，在传播过 程中，未标记的节点根据邻接点的标签情况来迭代更 新自身的标签信息，如果其邻接点与其相似度越相近， 则表示对其所标注的影响权值就越大，邻接点的标签 就更容易进行传播。 图３为标签传播过程。每个顶点都有一个唯一的标 签作为社区标识，对图中所有的顶点进行标签迭代更新。 在迭代过程中，每个顶点标签为其邻接点中出现次数最多 的节点的标签。如果多个标签的数量都是最大值，则随机 选择一个作为该顶点的标签。经过若干次迭代，最终形成 一个完全连通图（代表一个社区），并且该图内所有顶点都 拥有相同标签。 图３标签传播过程 ２．２ ＬＰＡ算法 ＬＰＡ算法基于标签传播算法思想来发现社区结构。 该算法由Ｒａｇｈａｖａｎ 提出，根据每个节点邻接点的社区 情况来选择所要加入的社区。其主要思想是起初每个节 点拥有的标签，每次迭代中对于每个节点将其标签更 改为其邻接点中出现次数最多的标签，如果这样的标签有 多个，则随机选择一个。通过迭代，直到每个节点的标签 与其邻接点中出现次数最多的标签相同，则达到稳定状 态，算法结束。此时具有相同标签的节点即属于同一个社 区。 ＬＰＡ算法的执行步骤： （１）初始化过程即为网络中的每个结点分配一个唯一 的标签，对于节点Ｘ，有 （Ｏ）一 。 （２）设置ｔ一１。 （３）将网络中的节点随机排序，假设顺序为Ｘ。 （４）对Ｘ中每个节点Ｘ，将Ｘ的标签设置为新的标签 （ ）一＿厂（Ｃ （ ）…，Ｃ ，Ｃ （ｔ一１）），ｆ函数返回节点Ｘ 的邻接点中出现次数最多的标签。如果有多个，则随机选 择一个。 （５）如果每个节点的标签都与其邻接点中出现次数最 多的标签相同，则算法结束，否则设置ｔ—ｔ－Ｉ－１，返回步骤 ３继续执行。 ２．３ ＣＯＰＲＡ算法 ＬＰＡ算法虽然有很多优势，但无法挖掘出重叠社区 结构。对此，Ｓｔｅｖｅｌ５ 基于原先的算法，引入了新的标签结 构（Ｃ，ｂ），对每个节点Ｘ， ∈Ｇ（ｚ），都拥有这样的标签。 其中，Ｃ表示社区标识符，ｂ表示节点ｚ在社区Ｃ中的从属 系数，且０≤ｂ≤１。 ＣＯＰＲＡ算法的执行过程如下： （１）初始化，对任意的节点ｚ，ｚ∈Ｇ（ ）分配一个唯一 的标签（Ｃ ，１）。 （２）节点ｚ根据其邻接点集的标签情况更新自己的标 签。如果有多个可选标签，算法会随机选取其中的７Ｊ个标 签作为结果。其中，０＜ｌ ｃ（ ）ｌ≤ 。节点的从属系数 符合如下表达式：＞：ｂ一 （ ，ｚ）一１，其中ｃ（ｚ）表示节点 ｃ ＥＣ（ｘ） ｚ可能属于的社区集合。 （３）如果每个节点的标签都与其邻接点中出现次数最 多的标签相同，则算法结束，否则返回步骤２继续执行。 （４）将具有相同社区标签节点合并为同一社区。 ３社区质量评价指标 对于社区发现算法所产生的社区，需要通过量化指标 衡量其质量好坏，从而进一步评估各种社区发现算法的优 劣。Ｎｅｗｍａｎ和Ｇｉｒｖａｎ 提出了一个评价社区质量的指 标，称之为模块化度量Ｑ。考虑某种划分形式，将网络划 第４期 沈海燕，李星毅：一种新的基于标签传播的重叠社区发现算法 ・６１・ 分为Ｋ个社区。令ｅ 为网络中连接社区ｉ到社区 的顶 点之间边的一半，对角线元素为ｅ ，则对角线上的各元素 之和为丁ｒ 一＞：一 ｅ ，表示网络中连接某一个社区内部各 个节点的边在所有边的数目中的比例。。 ： ：ｅ 为每行 （或者每列）中各元素之和，表示与第ｉ个社区中的节点相 连的边在所有边中的比例。在此基础上，用下式来定义模 块性的衡量标准： Ｑ一＞：（ 一ｎ ）一＂／ｒ＇ｅ—ｌ ｌＰ ｌ ｌ（１） 其中，ＩＩ ｌｌ表示矩阵 中所有元素之和。式（１）表 示在同样社区结构下，网络中连接两个同类型的节点的边 的比例减去任意连接这两个节点的边的比例的期望值。若 社区内部边的比例小于或者等于任意连接时的值，则Ｑ为 ０。Ｑ的上限为１，Ｑ越接近１，说明社区结构越明显。实际 上，该值通常为０．３～０．７。 Ｑ函数只是用来评价非重叠社区结构的指标。Ｓｈｅｎ 等口 对Ｑ函数作了扩展，得到一种可以用来评价重叠社 区结构的指标一ＥＱ函数，其公式为： ＥＱ一 ～ ］ （２） 其中， 是节点ｖ可以同时从属的社区数目，Ａ表示 由网络转换而成的邻接矩阵。 ４算法改进 根据上述ＬＰＡ算法和ＣＯＰＲＡ算法描述，可以看出 算法标签初始阶段是给网络中的所有节点分配唯一的标 签，此后标签会不断更新，网络规模越大，更新标签所需要 的资源消耗就越大。在标签更新阶段，如果存在多个标签 可选，则进行一次随机选择，这样导致算法的结果非常不 稳定。鉴于上述缺点，本文对ｃＯＰＲＡ算法标签初始化和 标签选择进行改进。 ４．１标签初始阶段 对标签的初始化主要是借鉴ＣＰＭ算法中Ｃｌｉｑｕｅ思 想。Ｃｌｉｑｕｅ代表网络中完全子图，用完全子图来代替大量 的节点。这样就不需要对所有的节点进行处理，只要对每 个完全子图分配标签。 标签预处理算法步骤如下： （１）初始化节点数据。 （２）遍历节点，根据邻接点依次寻找网络中Ｋ—Ｃｌｉｑｕｅ， 在此过程中，对从属于完全子图的节点进行标注，以防完 全子图出现重叠节点。 （３）对所发现的完全子图按综合度数排序，按照排序 在标签传播过程中优先处理。 （４）为每个Ｃｌｉｑｕｅ和剩余节点分配一个唯一的标签。 ４．２标签选择过程改进 ＣＯＰＲＡ算法第二步涉及随机选择，可以将此随机选 择进行弱化，本文主要引入标签影响值来进行弱化。 对每一个标签节点进行标签更新时，若其邻接点都没 有标签，则不进行更新。若其邻接点中有标签存在，则在 所有邻接点上的标签组成的集合中，选择其中一个作为ｚ 的标签。影响ｚ的因素有：每个标签存在的个数；所在边 的权重以及其所在邻接点的度。综合考虑这些因素的影 响力及其主次关系，最终提出将平均权重作为影响标签选 择的主要因素，邻接点的度作为次要因素。 对 邻接点中出现的每一个标签ｚ进行标签影响值 ｉｎｆｌｕｅｎｃｅ（ｚ）的计算，其定义如下： ｉｎｆｌｕＰ ｆＰ（ｚ）＝＝— ＋（１——ｇ一∑ （‘ ）（３） 其中，ｚ∈Ｌ，硼（ｚ ）表示每一个标签为ｚ的顶点所在 边的权重值；ｃ（ｚ）表示标签ｚ的总个数；＞：ｄ（１ ）表示所 有标签为ｚ的顶点度之和。 假设边的权重为正整数，则 ＞１，而１一 ∑ ＜１。因此，比较两个标签时，若平均权重的差值 大于１，则平均权重起主要决定作用；若值小于１，则由平 均权重和顶点之和共同决定。故对于一个顶点３２，其标签 为： Ｌａｂｅｌ（ｚ）一ａｒｇｍａｘ （４） ｉｎｆ ‘ｇ ｃｇ（ｚ）＝＝ａｒｇｒ】ｎａｘ［ 十（１——ｅ∑ ｃ‘ ）］（５） ５实验验证与分析 本文实验硬件环境为：Ｐｅｎｔｉｎｕｍ（Ｒ）双核２．７ＧＨＺ处 理器，４Ｇ内存，算法具体实现语言为ＪＡＶＡ。 ５．１基准测试集 为验证算法的有效性，将该算法应用到Ｚａｃｈａｒｙ’Ｓ Ｋａｒａｔｅ Ｃｌｕｂ Ｎｅｔｗｏｒｋ㈣和Ｄｏｌｐｈｉｎｓ Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋ 两 个真实网络中。 ５．１．１ Ｚａｃｈａｒｙ’ｓ Ｋａｒａｔｅ Ｃｌｕｂ Ｎｅｔｗｏｒｋ 在复杂网络社区结构研究中，该网络经常被使用，它 反映一所大学空手道俱乐部成员之间的关系。该数据集 包含３４个节点，７８条边，其中节点表示俱乐部的成员，边 表示成员之间的关系。 从表１可以看出，由于网络社区规模小，因而基于标 签传播的重叠社区算法并不能表现出优势。不仅如此，在 速度上反而还要低于ＣＦｉｎｄｅｒ算法，而且这３种算法挖掘 出的社区质量也没有明显的差别。 表１ Ｋａｒａｔｅ数据集测试结果 ・６２・ 软件导刊 ２０１５往 ５．１．２ Ｄｏｌｐｈｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ 该数据集为Ｌｕｓｓｅａｕ等对新西兰海域一个有６２个成 员的宽吻海豚社会网络进行长达７年（１９９５年到２００１ 年）观测后给出的宽吻海豚社会网络。该网络具有６２个 节点，１５９条边。 通过表２可以看出，本文新算法发现社区的模块化度 量值比原始算法有所提高，新算法所发现的社区质量有所 提高。当网络越复杂时，该优越性表现越明显。 表２基准测试集中的模块化度量ＥＱ ５．２抓取数据集 抓取到的数据集为Ｌｅｓｋｏｖｅｃｓｃ等 从Ａｒｘｉｖ网站上 抓取的关于广义相对论和量子宇宙学主题的论文集合，论 文作者为图的顶点，作者之间的合作关系为边。该数据集 总共有５ ２４２个顶点和１４ ４８４条边。 通过表３可以看出，在处理大规模数据集时，本文算 法无论是在执行效率上还是挖掘精度上较之原有的ＣＯＰ— ＲＡ有明显的优势。 表３ Ａｒｘｉｖ数据集上的测试结果 ６ 结语 本文主要采用标签传播的思想从标签初始化和标签 选择两个方面针对原有ＣＯＰＲＡ算法进行改进。通过在 初始阶段对标签的预处理过程来减少初始化的数目，从而 提高算法执行效率；在标签选择过程中引入标签影响值来 弱化随机选择，使得算法更加稳定。实验结果表明，改进 后的算法提高了算法稳定性，不仅能够成功挖掘出具有较 高质量的社区，而且还能挖掘出重叠社区结构。 本文仅仅从标签初始化和标签选择两个方面对算法 作了改进。对于标签传播的方式却未作出考虑。将从这 方面对算法作进一步改进，以得到更具优势的算法。原有 ＣＯＰＲＡ算法采用同步的方式，较之异步方式存在震荡的 问题。可以考虑将这两种方式进行综合得到新的传播方 式。 此外，在重叠社区结构发现方面，可以考虑将现有的 层次发现算法和重叠社区算法相融合，得到层次性重叠社 区发现算法，较之单一的重叠社区算法所挖掘出的社区更 加真实。 参考文献 ［１］ 汪小帆，李翔，陈关荣．复杂网络理论及其应用［Ｍ］． 北京：清华大 学出版社，２００６，１６２ １９１． ［２］ＴＲＡＵＤ Ａ Ｌ，ＫＥＬＳＩＣ Ｅ Ｄ，ＭＵＣＨＡ Ｐ Ｊ，ＰＯＲＴＥＲ ＭＡ．Ｃｏｍｐａ— ｒｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｔｏ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｉｎ ｏｎｌｉｎｅ ｃｏｌｌｅｇｉａｔｅ ｓｏ一 ｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］．ＳＩＡＭ Ｒｅｖ，２０１１，５３（３）：５２６—５４３． ［３］ＰＡＬＩ Ａ Ｇ，ＤＥＲＥＮＹＩ Ｉ，ＦＡＲＫＡＳ Ｉ，ｅｔ ａ１．Ｕｎｃｏｖｅｒｉｎｇ ｔｈｅ ｏｖｅｒ— ｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｉｎ ｎａｔｕｒｅ ａｎｄ ｓｏ— ｃｉｅｔｙ［Ｊ］．Ｎａｔｕｒｅ，２００５，４３５：８１４—８１８． ［４］ＲＡＧＨＡＶＡＮ Ｕ Ｎ，ＲＥＫＡ Ａ，ＳＯＵＮＤＡＲ Ｋ．Ｎｅａｒ ｌｉｎｅｒ ｔｉｍｅ ａｌｇｏ— ｒｉｔｈｍ ｔｏ ｄｅｔｅｃｔ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅｓ ｉｎ ｌａｒｇｅ ｓｃａｌｅ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａ１ Ｒｅｖｉｅｗ Ｅ，２００７，７６：３６—１０６． ［５］ＧＲＥＧＯＲＹ Ｓ．Ｆｉｎｄｉｎｇ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ｕｓｉｎｇ ｄｉｓｊｏｉｎｔ ｃｏｍ— ｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｓｔｕｄｉｅｓ ｉｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉ ｇｅｎｃｅ，２００９，２０７：４７—６２． ［６］ＨＵＡＷＥＩ ＳＨＥＮ，ｅｔ ａ１．Ｄｅｔｅｃｔ ｏｖｅｒｌａｐｐｉｎｇ ａｎｄ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｒｎ— ｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓｉｃａｌ Ａ：Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ Ｖｏｌｕｍｅ ３８８，Ｉｓｓｕｅ ８，１５ Ａｐｒｉｌ ２００９：１７０６— １７１２． ［７］ Ｃ ｇＥＥ，Ｆ ＲＥＩＤ，Ａ ＭＣＤＡＩＤ，ｅｔ ａ１．Ｄｅｔｅｃｔｉｎｇ ｈｉｇｈｌｙ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｂｙ ｇｒｅｅｄｙ ｃｌｉｑｕｅ ｅｘｐａｎｓｉｏｎ［ｃ］．Ｔｅｃｈ．Ｒｅｐ． ａｒＸｉｖ，２Ｏ１０． ［８］ ｓ ＭＩＮＧ—ＳＨＥＮＧ，Ｃ ＤＵＡＮ—ＢＩＮＧ Ｚ，ＴＡＯ．Ｄｅｔｅｃｔｉｎｇ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ｂａｓｅｄ ｏｎ ｃｏｍｍｕｎｉｔｙ ｃｏｒｅｓ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｃｈｉｎｅｓｅ Ｐｈｙｓｉｃｓ Ｌｅｔｔｅｒｓ，２０１０（２７）：５８－９０１． ［９］ ＺＨＵ Ｘ ＪＩＡＯ—ＪＩＮ，ＧＨＡＨＲＡＭＡＮＩ ｚ．Ｌｅａｒｎｉｎｇ ｆｒｏｍ ｌａｂｅｌｅｄ ａｎｄ ｕｎｌａｂｅｌｅｄ ｄａｔａ ｗｉｔｈ ｌａｂｅｌ ｐｒｏｐａｇａｔｉｏｎ，ＣＭＵ—ＣＡＩ Ｄ［Ｒ］．Ｐｉｔｔｓ ｂｕｒｇｈｅｒｓ：Ｃａｒｎｅｇｉｅ Ｍｅｌｌｏｎ Ｕｎｉｖｅｒｓｉｔｙ，２００２：２－１０７． ［ｉｏ］ＸＩＥ ＪＩＥ—ＲＵＩ，ＳＺＹＭＡＮＳＫＩ Ｂ．Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｕｓｉｎｇ ａ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｔｒｅｎｇｔｈ ｄｒｉｖｅｎ ｌａｂｅｌ ｐｒｏｐａｇａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［ｃ］． Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｎｅｔｗｏｒｋ Ｓｃｉｅｎｃｅ Ｗｏｒｋｓｈｏｐ，２Ｏ１１：１８８—１９５． ［１１］ＫＩＭ Ｙ，ＪＥＯＮＧ Ｈ．Ｔｈｅ ｍａｐ ｅｑｕａｔｉｏｎ ｆｏｒ ｌｉｎｋ ｃｏｍｍｕｎｉｔｙ［Ｊ］． Ｐｈｙｓｉｃａ１ Ｒｅｖｉｅｗ Ｅ，２０１１，８４（２）：２６—１１０． ［１２１ ＮＥＷＭＡＮ Ｍ，ＥＪ ＧＩＲＶＡＮ Ｍ．Ｆｉｎｄｉｎｇ ａｎｄ ｅｖａｌｕａｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ Ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ，２００４（６９）：２６ ｉ１３． ｒ ｉ ３１ ＺＡＣＨＡＲＹ Ｗ Ｗ．Ａｎ ｉｎｆｏｒｍａｔｉｏｎ ｆｌｏｗ ｍｏｄｅ１ ｆｏｒ ｃｏｎｆｌｉｃｔ ａｎｄ ｆｉｓ— ｓｉｏｎ ｉｎ ｓｍａｌｌ ｇｒｏｕｐｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ＡｎｔｈｒＯｐｏｌ０ｇｉｃａ１ Ｒｅｓｅａｒｃｈ， １９７７，３３（４）：４５２－４７３． ［１４］ＤＡＶＩＤ ＬＵＥＳＳＥＡＵ，ＫＡＲＳＴＥＮ ＳＣＨＮＥＩＤＥＲ，ＯＬＩＶＥＲ Ｊ ＢＯＩＳＳＥＡＵ，ｅｔ ａ１．Ｔｈｅ ｂｏｔｔｌｅｎｏｓｅ ｄｏｌｐｈｉｎ ｃｏｍｍｕｎｉｔｙ ｏｆ Ｄｏｕｂｔ— ｆｕｌ Ｓｏｕｎｄ ｆｅａｔｕｒｅｓ ａ ｌａｒｇｅ ｐｒｏｐｏｒｔｉｏｎ ｏｆ ｌｏｎｇ—ｌａｓｔｉｎｇ ａｓｓｏｃｉａｔｉｏｎｓ ［Ｊ］．Ｂｅｈａｖｉｏｒａｌ Ｅｃｏｌｏｇｙ ａｎｄ Ｓｏｃｉｏｂｉｏｇｙ，２００３（５４）：３９６—４０５． ［１５］ＬＥＳＫＯＶＥＣ Ｊ，ＫＬＥＩＮＢＥＲＧ Ｊ，ＦＡＬＯＵＴＳＯＳ Ｃ．Ｇｒａｐｈ ｅｖｏｌｕ ｔｉｏｎ：ｄｅｎｓｉｆｉｃａｔｉｏｎ ａｎｄ ｓｈｒｉｎｋｉｎｇ ｄｉａｍｅｔｅｒｓ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｆｒｏｍ Ｄａｔａ（ＡＣＭ ＴＫＤＤ），２００７，１（１）：１— ４０． （责任编辑：陈福时）
