…～ ＤＯＩ：１０．１６７０７￣．ｅｎｋｉ．ｆｊｐｃ．２０１６．１２．００５ 丽 彳 ………一 基于拓扑结构的二分网络社区发现算法 邹凌君 （金陵科技学院信息化建设与管理中心江苏南京２１１１６９；） 【摘要】二分网络的社区划分是＂３前的研究热点。本文提出了一种基于拓扑结构的二分网络社区划分算法。首先找 －出网络中所有的社区核，根据社区核的紧密度得到初始社区，最后再对孤立点进行处理，得到最终的社区划分。实验结果 表明，算法在不需事先指定社区个数的前提下，能获得较好的社区划分效果。 【关键词】二分网络；社区划分；拓扑结构 １．引言 其邻接顶点的标签，最终连接紧密并且有相同标签的顶点形成 一二分网络是复杂网络的一种重要表现形式。如图１所示， 个社区。Ｍｕｒａｔａ￣７１提出了ＬＰ＆ＢＲＩＭ算法，它基于标签传播算 二分网络由两类节点构成。相同类型的节点内部没有连边，连 边只存在于不同类型的节点之间。现实生活中很多的现象都可 以用二分网络来描述。例如科学家和他们写的论文可以用科学 家一论文网『ｌ】来描述，疾病和基因的关系可以用疾病一基因网１２］来 描述。演员和他们参演的电影可以用演员一电影网来描述。 法，采用ＢＲＩＭ算法改进划分质量，以产生更好的社区划分，算 法适用于大型网络，可在大型网络中获得较好的划分质量。文 献Ｅｓ］提出了一个基于矩阵分解的二分网络社区挖掘算法。首 先将二分网络分为两个部分，每个部分尽量完整的保存原始的 社区信息，再对两个部分进行递归分解，直至不能拆分为止。算 法能获得较好的社区划分质量。 ３．算法的基本思想 ３．１相关定义 一个二分网络可以用二部图Ｇ ，曰）来表示，Ａ 和曰 分 图１二分网络 别是Ｇ的两个节点集，分别有ｍ和ｎ个节点。 （Ｇ ，日））和Ｅ （Ｇ ，曰））分别是二分网络的节点集和连边集。对于任意一条 连边（厶），有ｉ∈ＡＸ ９ Ｂ 。二部图的邻接矩阵为： ． 网络中的社区是由网络中的项点及其连边组合而成的集 合，同一个社区内的顶点连边较多，联系比较紧密，而不同的社 区间的顶点连接比较少。研究和分析二分网络社区能够挖掘二 分网络结构和特性，对网络有更深入的理解和认识。 本文提出了基于拓扑结构的二分社区发现算法。在原始二 分网络上进行挖掘，将二分网络中的社区核作为初始社区，根 据紧密度进行合并，最后对不属于任何社区的孤立点进行处理 ：『０Ｉ … Ｕ …０ ｊ ］ 和 这里０ 和０ 分别是ｍｘｍ和ｎ×ｎ阶全０矩阵， 分别是ｍｘｎ和ｎ，Ｘｍ的非０矩阵。由于邻接矩阵是对称，因 而用 表示二部图，每一行表示Ａ类的一个顶点，每一列表 示Ｂ类的一个顶点。 定义１二分子网：假定Ｇ ｓ，Ｂｓ），Ａ ∈Ａ，Ｂｓ∈Ｂ，对于任一 节点ｉ∈Ａ ｓｘ， ∈Ｂｓ ，满足ｅ（ ， ）∈Ｅ（Ｇ（ ）），则称Ｇ ｓ，Ｂｓ）是原 二分网络的一个二分子网。 得到社区划分。本文提出的算法不需额外的参数，能得到较好 的划分效果。 ２．相关工作 对二分网络社区发现是当前的研究热点，目前对二分网络 社区的发现算法主要分为两类。一类是将二分网络投影成单分 网络，用单分网络的方法来发现，文献Ｅ３Ｊ利用资源矩阵替代相 似度矩阵，将二分网络映射到单一网络，挖掘出同类节点问的 隐含信息。但将二分网络投影成单分网络方法会造成部分原始 信息的丢失以及投影过程中生成冗余信息等缺点。另一种方法 是直接对二分网络进行社区发现。文献［４］提出了一种二分模 块度以此来衡量社区的划分质量，该模块度使用相同类型的顶 二分网络的社区发现是要发现这样的二分子网，使得子网 内部的节点连接紧密，而子网之间节点连接稀疏，节点问相互 作用较弱。 定义２社区核：对于二分子网Ｇ ，Ｂｓ），若Ａ 中的任一结 点都和日 中的每个结点相连，同时 中的每个结点都和Ａ 中 的每个结点相连，则称该二分子网是一个社区核Ｃ ，Ｂｓ）。 定义３社区核的紧密度：对于任意两个社区核Ｃ ，Ｂｓ）和 ｃｚｃ４ ｓ，Ｂｓ），社区核之间的紧密度定义为Ｎ【ｃ‘）： 点的共同邻居来表示社区内顶点的相似程度，并以此量化社区 内顶点的连接稠密程度。但该二分模块度只能分别对不同类型 的顶点进行划分，社区间没有对应关系。文献Ｅ５］定义了新的二 其中ｓ（ｑ， ）＝｛（ Ｊ）ｌ（ｉ．，）∈Ｅ．ｆ ＣＩ，Ｊ ｝，Ｎ（Ｃｋ）＝｛Ｉ（ｉ，Ｊ）ｌ（ｉ，，） ．ｆ Ｃｋ．Ｊ ｝ 定义４．孤立点的紧密度：对于任意孤立点到社区的紧密度 分模块度，并提出了能同时对异质节点进行社区划分的ＢＲＩＭ 算法。该方法需要事先确定社区的数量。Ｒａｇｈａｖａｎ［６］等人提出了 标号传播方法ＬＰ用于单分网络的社区挖掘，算法首先为每个 可定义为该结点在社区中的邻居数。ｌⅣ（ ）ｌ＝ｌ｛．／ ．，）ｅＥ，．，ｅｃ｝Ｊ。 ３．２．算法描述 顶点分配一个标签，然后在迭代过程中，每个顶点尽可能选取 整个过程分为两个步骤 金项目】江苏省现代教育技术研究课题（２０１６一Ｒ一５１１６７）；江苏省高等教育教改研究课题（２ｏ１５ＪＳＪＧ５６２） ２０ｌ６年第１２期ｌ福建电脑 ・９・ ＩＩ ＬＪＪＩＡ 煎下器 （一）初始社区的形成 我们首先找到二分网络中的所有的社区核，社区核中的两 类结点相互之间有连边连接，因而它们的连接最紧密。然后根 该算法不需事先确定社区的个数，克服了当前很多二分网络社 区发现需要事先指定社区个数的缺点。算法还能发现社区间的 重叠，具有一定的现实意义。下一步的研究工作是研究当社团 结构不明显时如何进一步提高算法的准确度。 参考文献： ｌ １］Ｎｅｗｍａｎ Ｍ Ｅ Ｊ．Ｓｃｉｅｎｔｉｉｆｃ ｃｏｌｌａｂｏｒａｔｉｏｎ ｎｅｔｗｏｒｋｓ．Ｉ Ｎｅｔｗｏｒｋ ｃｏｎ— 据社区核的紧密度，将社区核进行合并。若社区核紧密度Ｎ（Ｃ ， Ｃ２）大于２／３，则将其合并，否则不做处理。这一过程处理后所得 的结果称为初始社区。 （二）孤立点的处理 经过步骤一以后，仍可能有结点会不包含在任何社区中， 计算孤立点到各个初始社区的紧密度，将孤立点分配到紧密度 ｓｔｒｕｃｔｉｏｎ ａｎｄ ｆｕｎｄａｍｅｎｔａｌ ｒｅｓｕｌｔｓＵｊ．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ，２００１，６４：０１６１３１ ｌ ２］Ｃｈｅｎ Ｗｅｎ—ｑｉｎ，Ｌｕ Ｊｕｎ—ａｎ，Ｌｉａｎｇ Ｊｉａ．Ｒｅｓｅａｒｃｈ ｉｎ ｄｉｓｅａｓｅ—ｇｅｎｅ ｎｅｔ— 最大的社区中。若和两个以上的社区的紧密度相同，则可将该 孤立点作为社区间重叠。 ｗｏｒｋ ｂａｓｅｄ ｏｎ ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ ｐｒｏｊｅｃｔｉｏｎ…Ｃｏｍｐｌｅｘｉｔｙ Ｓｃｉｅｎｃｅ，２００９，６（１）：１３—１９． Ｃｏｍｐｌｅｘ Ｓｙｓｔｅｍ ａｎｄ ４．实验结果与分析 ［３］张嫱嫱，黄廷磊，张银明．基于聚类分析的二分网络社区挖掘 ］．计 为了测试算法的性能，我们将本文的算法在妇女一活动二分 网进行测试。该数据集是由１８个妇女和１４个活动构成的二分 网络，每个顶点代表一个妇女或一个活动，如果一个妇女参加 了某个活动，那么这两个对应的顶点之间存在一条链接。编号 １—１８表示１８个妇女，编号１９—３２表示１４个活动。 算机应用，２０１５，３５（１２）：３５１１—３５１４． １４ｊＧｕｉｍｅｒ ａ Ｒ，Ｓａｌｅｓｐａｒｄｏ Ｍ，Ａｍａｒａｌ Ｌ Ａ．Ｍｏｄｕｌｅ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ ｉｎ ｂｉ— ｐａｒｔｉｔｅ ａｎｄ ｄｉｒｅｃｔｅｄ ｎｅｔｗｏｒｋｓ．１Ｊｊ．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ，２００７，７６：０３６１０２ ｌ ５］Ｂａｒｂｅｒ Ｍ Ｊ．Ｍｏｄｕｌａｒｉｙ ａｎｄ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｔｉｏｎ ｉｎ ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋｓ ｌＪ Ｊ．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ，２００７，７６：０６６１０２ ｌ ６ ｊＲａｇｈａｖａｎ Ｕ Ｎ，Ｍｂｅｒｔ Ｒ，Ｋｕｍａｒａ Ｓ．Ｎｅａｒ ｌｉｎｅａｒ ｔｉｍｅ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｅ— ｔｅｃｔ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅｓ ｉｎ ｌａｒｇｅ—ｓｃａｌｅ ｎｅｔｗｏｒｋｓ ｌＪ ｊ．Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ， ２００７，７６：０３６１０６ ｌ ７ ｊＬｉｕ Ｘｉｎ，Ｍｕｒａｔａ Ｔ，Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｌａｒｇｅ—ｓｃａｌｅ ｂｉｐａｒｔｉｔｅ ｎｅｔ— ｗｏｒｋｓ［Ｃ ｊ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００９ ＩＥＥＥ／ＷＩＣ／ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｅｂ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ｉｎｔｅｎｉｇｅｎｔ Ａｇｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ（ｇｇｌ——Ｉ—— 口 ＡＴ’０９）．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，ＵＳＡ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００９：５０—５７ 图２妇女一活动二分网 ［８］陈伯伦，陈岐，邹盛荣等．基于矩阵分解的二分网络社区挖掘算法 我们使用本文算法划分此二分网络，得到了两个社区｛妇 女１—８，活动１９—２７｝和（妇女９—１８，活动２８—３２｝。该划分结果和 Ｄａｖｉｓ利用人种学知识划分的结果较为一致。说明算法是有效 的。 ［＿Ｊ］．计算机科学，２０１４，４１（２）：５５—５８，１０１． 作者简介： 邹凌君（１９８４一），女，江苏南京人，研究生，工程师，研究方向为复 杂网络的链接预测、数据挖掘，信息管理等。 ５．结束语 本文提出了一种基于拓扑结构的二分网络社区挖掘算法。 （上接第２页） ５结论 图像 ＬＺＷ ＬＺＷ—ＭＡＬ ６．７ ６．２ Ｊ Ａ Ａ Ｆａｓｔ Ｍｇｏｒｉｔｈｍ ｔｏ Ｆｉｎｄ Ａｌｌ ｔｈｅ Ｍａｘｉｍａｌ Ｆｒｅｑｕｅｎｔ Ｓｅｑｕｅｎｃｅｓ ｉｎ ａ ｂ ６．５ ６．１ ７．８ ７．３ ｄ ７．６ ７．１ ７．９ ７－３ ｆ ７．４ ６．８ ｇ ８＿３ ７．５ ｈ ７－３ ６－８ Ｔｅｘｔ ｌＭ Ｊ／／Ｐｒｏｇｒｅｓｓ ｉｎ Ｐａｔｔｅｍ Ｒｅｃｏｇｎｉｉｔｏｎ，Ｉｍａｇｅ Ａｎａｌｙｓｉｓ ａｎｄ Ａｐｐｌｉｃａ— ｄｏｎｓ．Ｓｐｒｉｎｇｅｒ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ，２００４：４７８—４８６ ｌ ３ ｊ Ｖｅｒｇａｒａｖｉｌｌｅｇａｓ，Ｏｓｓｌａｎ Ｏ，ｅｔ ａ１．”Ｄａｔａ Ｐｒｅｐｒｏｃｅｓｓｉｎｇ ｂｙ Ｓｅｑｕｅｎｆｉｄ Ｐａｔｔｅｒｎ Ｍｉｎｉｎｇ ｆｏｒ ＬＺＷ”Ｍｅｘｉｃａｎ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ— 本文结合邻近序列与页面置换方法提出了一个ＬＺｗ图像 压缩的改进ＬＺＷ—ＭＡＬ算法，该算法结合最大邻近序列模式， ｐｕｔｅｒ Ｓｃｉｅｎｃｅ ２００５：８２—８７． ［４］汤小丹梁红兵哲凤屏汤子瀛．计算机操作系统（第四版）：西安电 子科技出版社：西安电子科技大学出版社．２０１６年０８月．１６２—１６７． １ ５ Ｊ Ｇａｒｃｉａ－Ｈｅｒｎａｎｄｅｚ Ｒ Ａ，Ｍａｒｔｉｎｅｚ－Ｔｒｉｎｉｄａｄ Ｉ Ｆ，Ｃａｒｒａｓｃｏ—Ｏｃｈｏａ ｌ Ａ． Ｆｉｎｄｉｎｇ ｍａｘｉｍａｌ ｓｅｑｕｅｎｔｉｌ ａｐａｔｔｅｒｎｓ ｉｎ ｔｅｘｔ ｄｏｃｕｍｅｎｔ ｃｏｌｌｅｃｔｉｏｎｓ ａｎｄ ｓｉｎｇｌｅ 充分利用图像中未使用的像素值编码进行图像文件的最大邻 近序列模式替换，改善了局部而非全局搜索方式产生的字典压 缩效果，此外，使用页面置换的最近最久未使算法方法来改善 ＬＺｗ算法的字典表。实验结果表明，ＬＺＷ—ＭＡＬ改进算法对图 像的压缩比优于ＬＺｗ算法。 ｄｏｃｕｍｅｎｔｓ．－Ｊｊ．Ｉｎｆｏｒｍａｔｉｃａ，２０１０，３４（Ｉ）：９３—１０１． 作者简介： 参考文献： ［１］Ｒｅｈｍａｎ，Ｍｅｈｗｉｓｈ，Ｍ．Ｓｈａｒｉ￣ａｎｄ Ｍ．Ｒａｚａ．”Ｉｍａｇｅ Ｃｏｍｐｒｅｓｓｉｏｎ：Ａ Ｓｕｒｖｅｙ”Ｒｅｓｅａｒｃｈ Ｊｏｕｒｎａｌ ｏｆ Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅｓ Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ ７．４（２０１４）：６５６—６７２． 黄剑雄（１９９０一），男，福建省莆田市人，研究生，研究方向：关联规 则、图像压缩。谢伙生（１９６４一），通讯作者，男，福建省宁化县人，副教 授，研究方向：数据挖掘、图形图像处理。 ［２］Ｇａｒｃ ｉ ａ—Ｈｅｒｎａ ｎｄｅｚ Ｒ Ａ，Ｍａｒｔ ｉ ｎｅｚ—Ｔｒｉｎｉｄａｄ Ｊ Ｆ，Ｃａｒｒａｓｃｏ－Ｏｃｈｏａ ・１０・ 福建电脑ｌ ２０１６年第１２期
