结合网络拓扑与节点内容的统一化半监督社团检测方法_许伟忠.pdf

第 卷第 期 年 月南京师大学报（自然科学版）（）.，收稿日期：基金项目：国家自然科学基金面上项目（）、江苏省自然科学基金面上项目（）、江苏省高等学校自然科学研究面上项目（）、南通大学人才引进项目（）通讯作者：曹金鑫，博士，讲师，研究方向：数据挖掘、机器学习、社团检测等：结合网络拓扑与节点内容的统一化半监督社团检测方法许伟忠，曹金鑫，金 弟，孙 翔，张晓峰，刘 路，丁卫平（南通大学信息科学技术学院，江苏 南通）（天津大学智能与计算学部，天津）（莱斯特大学信息学院 莱斯特，英国 ）摘要 在复杂网络分析中，社团检测发挥着越来越重要的作用，而在实际应用中如何提高社团检测的性能仍是一个共同研究目标 由于网络节点中内容信息有助于社团识别，一些方法侧重于将网络拓扑和节点内容相结合，并且获得了不错效果 此外，也有些方法借用节点之间的拓扑相似度，以提升实现社团检测性能 鉴于此，我们提出了一个统一化方法，结合节点内容的半监督社团检测，简称 在该方法中，我们不仅将链接增强应用于社团检测，而且实现了拓扑和内容有机融合 首先，我们运用随机模型来描述节点社团隶属度 其次，我们构建出一个刻画节点内容社团隶属度的随机块模型，节点社团隶属度作为节点内容的权重向量，以实现拓扑和内容结合 再次，我们利用网络中节点之间的拓扑相似度构建先验信息，即，使网络中节点与其最相似的邻居节点具有相同的隶属度分布 最后，使用非负矩阵分解的方法学习新模型的统一化参数 在带有真实标签的人工网络和真实网络上，我们对新方法与一些当前流行的社团检测方法进行了性能比较 实验结果显示，通过融合节点内容和先验信息强化的链接，新方法检测社团的性能取得了显著提升关键词 社团检测，节点内容，先验信息，随机块，非负矩阵分解中图分类号 文献标志码 文章编号（），（，）（，）（，）：，许伟忠，等：结合网络拓扑与节点内容的统一化半监督社团检测方法 ，：，社交网络的发展催生了纷繁复杂的海量数据，如用户关系网络、产品评论和在线评论等 这些海量数据通常被建模为复杂网络 对于复杂网络的分析，挖掘网络中的社团结构是一项十分关键的任务，可用以揭示复杂网络的结构和功能特性一般来说，社团为网络中一组节点所构成的簇，同一簇的节点之间链接稠密，而不同簇的节点之间链接稀疏 已经有不少研究人员提出了许多不同类型的方法以检测网络中社团结构 这些方法很大程度上依赖于网络拓扑，其性能往往受到原始网络中某些链接丢失的影响 实际上，真实世界中的网络充满各种类型的内容信息，比如社交网络中用户节点上的用户信息等 这些内容能够减缓链接丢失的负面影响，辅助网络拓扑进行社团检测 等研究发现，内容信息有助于挖掘网络中的社团结构 已有一些融合拓扑和节点内容的社团检测方法被提出，并且也取得了不错的效果 但是，这些方法仍受网络拓扑中结构信息的影响此外，传统社团检测方法大多基于以下想法建模网络拓扑，即视社团为一组具有相似链接模式的节点集合，其在具有清晰社团结构的网络上表现效果不错 而当网络中包含一些复杂结构时，例如同配结构、异配结构和分层结构等，这些方法的性能将急剧下降 为了解决该问题，可挖掘网络中先验信息对网络拓扑进行调整，进而提高社团检测方法的性能 最近，等、等使用先验信息提出半监督社团检测方法 其研究结果显示，尤其是在具有噪声和复杂结构的真实网络中，这些方法仅融入有限的先验信息便实现了社团检测精度和鲁棒性的显著提升综上所述，网络中包含了网络拓扑、节点内容和先验信息 当融合来自网络中不同源的有益信息，社团检测的性能将得到进一步提升 例如，我们在网络中发现对于具有相似内容信息的节点或是邻居相同的比例高的节点，可运用节点内容、先验等有益信息指导设计社团检测算法，将节点划分到同一社团 在本文，我们提出了一种同时融合网络拓扑、节点内容的统一化半监督社团检测模型（，）新模型的输入为两个源，其一是表示网络拓扑信息的邻接矩阵，其二是表示节点内容的特征矩阵 此外，利用邻接矩阵转化为节点结构相似度矩阵获得先验信息 在该模型框架下，我们首先基于生成模型的思想构建节点隶属度矩阵，以拟合邻接矩阵；同时，视社团为文档中主题，隶属度矩阵即可作为 模型中的文档主题隶属度矩阵，以实现网络拓扑与节点内容的融合 然后，我们运用节点结构相似度矩阵获取先验信息，基于以下想法：“若两节点具有存在链接且拓扑结构相似的先验信息，则它们可被划分到同一社团”，建模先验信息为一个非负矩阵以调整隶属度矩阵，进而实现先验信息的融入 最终，我们运用一个平衡因子融合拓扑和内容信息，一个邻域超参控制先验信息，以构建融合节点内容的统一化半监督社团检测模型 总结来说，本文研究的贡献如下：（）我们提出了一种新型的、统一化的半监督社团检测模型 该模型不仅融合网络拓扑与节点内容信息，也引入先验信息 刻画的结构信息（）在统一模型框架下，获取的单一的节点社团隶属度同时刻画网络拓扑、节点内容和先验三种信息 模型的鲁棒性得到提升（）我们通过量化模型中的平衡因子和邻域超参以提升新模型在人工、真实网络上社团检测效果 与当前流行的社团检测方法相比，新模型识别社团结构的性能更优南京师大学报（自然科学版）第 卷第 期（年）相关工作对本文新模型相关的社团检测算法进行梳理，分别从融合拓扑和内容社团检测、半监督社团检测两方面展开研究 等基于图聚类提出了 算法，其融合拓扑和内容的方式简单易行，但方法性能依赖于社团结构的清晰程度 等基于生成的思想提出了一种联合概率模型 融合拓扑和内容，但对拓扑中复杂结构敏感 等设计了基于非负矩阵分解的 算法，学习节点属性社团隶属度以实现对社团的语义解释，但也受到拓扑结构信息影响 等考虑节点度不均衡、节点内容流形等问题，提出了 模型，发现建模拓扑结构有益于社团检测 分析上述方法发现，虽然这类方法融合了拓扑和内容，但先验信息的利用仍具有必要性 等将已知社团信息分配给不同节点，基于半监督图聚类实现社团检测 等将 和 约束融入邻接矩阵并进行分解，以实现半监督社团检测 等基于隐空间聚类策略，运用图正则以实现先验信息对社团隶属度的惩罚，构建半监督社团检测模型 和 等分别构建非负矩阵、图正则项以表示先验信息的硬、软约束，提出一种基于非负矩阵分解的链接强化框架（简称），实现半监督社团检测 虽然这类方法运用了先验信息，却忽略了内容信息的作用，仍会受到链接存在噪声或是缺失的影响 方法首先，我们在基于非负矩阵分解的生成框架下构建了融合拓扑和内容的基本模型 其次，计算节点间的结构相似度，建模先验信息，并将其集成到拓扑信息中，以构建融合节点内容的半监督社团检测模型 最后，使用梯度下降法实现模型参数的学习在本文，我们使用（，）描述一个无向非加权的属性网络，表示网络中节点的集合，表示网络中链接的集合，表示网络中节点内容特征的集合 本文中，邻接矩阵 表示拓扑信息，即当节点 和 之间存在链接时，否则；使用内容矩阵表示节点内容信息，即当节点 含有第 个特征时，否则 基本模型构建我们使用矩阵 描述节点社团隶属度分布，其中 表示节点 属于第 个社团的倾向 网络中节点之间的链接取决于这两个节点属于同一个社团的概率 因此，表示社团 中节点 和 之间生成的链接数量，则整个网络 个社团中 和 之间的链接期望数可表示为 ，（）可用式（）生成期望邻接矩阵?，即?，以拟合邻接矩阵 拓扑子模型的损失函数可写为（）?（）若网络中的每个节点对应一篇文档，那么社团对应文档集中的主题，节点内容的属性对应文档的单词 我们借鉴 主题模型的思想构建内容信息子模型 首先，我们引入一个描述社团内容的矩阵，表示内容社团 包含第 个单词的倾向，那么，表示节点 属于第 个内容社团且该内容社团包含第 个单词的倾向 进一步来说，节点 与第 个特征之间的关系可表示为 ，（）可用式（）生成期望内容矩阵?，即?，以拟合内容矩阵 内容信息子模型的损失函数可写为（，）?（）由式（）可见，我们将社团内容矩阵 与社团隶属度矩阵 一样作为变量来优化，与 相比，不仅得到了节点内容与内容社团之间的关系，而且还具有更低的时间复杂度，为（）至此，结合拓扑子模型（）和内容信息子模型（），我们构建了融合网络拓扑和内容信息的统一化基许伟忠，等：结合网络拓扑与节点内容的统一化半监督社团检测方法本模型，其损失函数可写为（，），（）式中，为平衡因子，控制基本模型（）中内容信息比重 在统一化基本模型中，我们视节点内容中挖掘出的内容社团与从拓扑信息中挖掘出的节点社团是一致的。那么，非负矩阵分解所获得的社团隶属度矩阵 即运用到节点内容 因此，我们的统一化模型能够同时利用拓扑信息和内容信息联合学习出网络中的社团结构 先验信息建模和融合内容半监督社团检测构建关于先验信息，我们运用网络拓扑中节点之间相似的结构来刻画，具体可用该节点的邻域来进行描述 因此，网络中节点 的拓扑结构可表示为（）（，）（）启发于人类社会中“熟人交集越大的两个人在同一社会群体中的概率可能也越大”，则节点 和 基于拓扑的结构相似度可定义为（）（）（）（）（）使用式（）可计算网络中任意两个节点之间的结构相似度，记为相似度矩阵 基于以下思想构建先验信息：如果网络中两个节点之间存在链接并且拓扑结构相似度高，我们就有理由认为这两个节点之间存在，将这两个节点划入同一个社团 那么，约束矩阵 可定义为，（）式中，为控制 数量的邻域超参 约束矩阵 可对应于一个无向图 为了实现先验信息集成，我们首先计算图 的连通分量，并认为每个连通分量中的节点之间都满足 关系，即同一个连通分量的节点应被划入同一个社团 借鉴 等所提 算法中强约束的构造方法，我们再构建指示矩阵 记录每个节点所属的连通分量，以表示先验信息，同时引入一个非负的辅助矩阵 则节点社团隶属度矩阵 可表示为（）从式（）可知，若节点 和 之间存在，我们使指示矩阵 的第 行和 行相等，即 ，从而，表示矩阵 的第 和 行相等，即节点 和 有相同的隶属度分布，必被划入同一个社团中 基于此，我们建模了先验信息最终，构建融合节点内容且集成 先验信息的新模型，其损失函数为（，）（）新模型不仅使用先验信息对拓扑信息起到增强的效果，而且还融合了节点内容信息，从而能够更加精确地揭示网络中的社团结构 模型优化本文基于梯度下降算法学习模型参数 该模型的参数包括两个参数矩阵 和 我们先对公式（，）进行迹运算，然后，基于参数矩阵求偏导，进而获取参数更新规则 损失函数的迹（，）如下：（，）（）（）（）（）（）（），（）式（）关于参数 求偏导为（，）（）根据 规则，参数 的更新公式可以写为南京师大学报（自然科学版）第 卷第 期（年）（）（）|（）同理，式（）关于参数 求偏导为（，）（）式（）属于标准非负矩阵分解的优化，同理，依据 规则，参数 的更新公式可写为（）（）|（）在新模型中，我们首先随机初始化 和 然后，分别基于更新规则（）和（）对 和 进行迭代更新，直至损失函数（）收敛为止 最后，运用式（）计算出节点社团隶属度，以实现社团检测 实验分析为了量化新方法检测社团的性能，我们选择一些当前流行的社团检测方法与 在人工、真实网络上进行性能对比，并运用常用评价方法标准互信息熵、调整兰德系数 进行量化本文使用的对比算法涉及融合拓扑和内容、半监督社团检测算法两类，具体如表 所示。考虑到算法涉及节点内容，我们使用的人工数据集是基于经典的、基准数据集和结合节点内容生成算法生成的内容信息构建的新型、具有内容信息的、基准数据集 其中，、网络生成算法的参数设置可以参考文献。我们还在真实网络上进行对比实验，真实网络的详细信息如表 所示表 本文实验中真实网络的详细信息 表 本文实验中的对比方法 图 在 的 网络上测试参数 和 的 结果.图 在 的 网络上测试参数 和 的 结果.超参 和 敏感度测试在两个带有节点内容的人工网络 上（和，其社团结构非常模糊），我们对超参 和 进行测试 首先为超参选择一个初始化的区域，即、间隔为 和、间隔为，然后进行遍历搜索 基于不同的超参组（，），识别社团的精确度 值曲面如图、图 所示 可以发现，当（，）（，）、（，）时，取得峰值 综合分析，我们选择（，）（，），也将该设置应用于真实网络实验中许伟忠，等：结合网络拓扑与节点内容的统一化半监督社团检测方法 人工网络上实验分析我们在网络规模为 、带有节点内容的 网络上对比不同方法检测社团的能力 网络生成算法的混合参数 描述了当前节点与社团外部其他节点之链接所占该节点之度的比例 值越大，网络中社团结构越不清晰 一般而言，社团检测方法识别该网络中社团的性能呈现下降趋势 那么，随着 值不断增大，社团检测精度 曲线下降缓慢的方法更具有竞争力 在本实验中，我们分别以指数 、和、的幂律分布生成网络中节点的度和社团的大小，从而得到四组网络 在每组网络中，我们从 至 以 为步长设计混合参数，共计 个网络作为实验网络数据 如图 所示，不同社团检测方法的基于 精度曲线随混合参数 值的增大而以不同程度下降 我们从图中可以较明显地观察到，方法 获得 曲线下降速度比其他方法更缓慢 我们还发现，半监督社团检测方法 （为 的）、（为、基于标准 的）和 获得的精度曲线下降速度快于融合拓扑和内容的社团检测方法、其原因可能是，网络中拓扑与内容具有较强的同质性，以致节点内容具有较强辅助拓扑检测社团的能力 本小节实验综合分析可得，新方法 融合节点内容、先验信息实现了社团检测性能和鲁棒性的提升网络规模 ，参数 和 分别表示生成网络算法中度分布和社区规模分布的指数图 我们的方法和对比方法在带有节点内容 网络上的 曲线.真实数据集上实验分析我们还在真实网络上测试 检测社团的性能 其中，各对比算法中参数设置均为原作者给出的默认设置 由于 等未明确设置、中 数量 因此，我们设置 与、具有相当数量的 参考式（），中 数量小于且接近网络中链接总数；参考表 中真实数据集的 （）平均值为，可设置、中 数量为（），大于且接近 为了检验 融合先验信息的性能，将其与其他半监督方法在不同比例先验信息条件下进行对比 如图 所示，随着 不断增大，的精度明显高于其他方法 同时，在不同真实网络上，新方法 与其他方法基于评价方法、度量的对比结果如表 所示 可以发现，检测不同网络中社团结构，取得最佳或是第二佳的精度值 尤其运用聚类、社团检测领域中常用的、算法类型无关的评价方法 评价时，方法仍取得最佳或是第二佳精度 在 上取得较高精度，其原因在于使用的 数量为 所使用的 倍之多，先验信息给出社团结构也更清晰 方法识别社团的精度基本高于融合拓扑和内容、半监督类型社团检测方法 这些实验都验证了，融合节点内容、拓扑的先验信息可进一步提高社团检测性能以及鲁棒性南京师大学报（自然科学版）第 卷第 期（年）图 邻域超参 取不同值，不同半监督方法在（）、（）、（）和（）上的性能对比.，（），（），（）（）表 不同方法社团检测性能对比，加粗、斜体的结果分别指示最佳、第二佳结果 ，图 在，和 真实网络上的收敛曲线.，新模型收敛分析我们在 个真实数据集上分析新方法 的模型收敛 如图 所示，的损失函数值随迭代次数增大的变化情况 在不同规模网络上，需要迭代 次左右，其损失函数值的显著变化率小于，许伟忠，等：结合网络拓扑与节点内容的统一化半监督社团检测方法 即可达到收敛 新模型的时间复杂度分析我们还对提出方法进行时间复杂度分析，算法 的主要时空开销包含以下两个过程：一是先验信息的构建过程，另一是目标矩阵 和 的迭代更新过程 先验信息的构建过程主要分为三个阶段，相似度矩阵 的计算、约束矩阵 的计算以及图 中连通分量的计算 这里，表示网络中节点数量，为网络中链接的数量，表示网络中社团的数量，为节点内容特征的维度，为网络中节点的最大度，为约束矩阵 中连通分量的数量 计算、以及连通分量的时间复杂度不超过（）、（）和（），则构建先验信息的时间复杂度为（）矩阵 和 一次更新的时间复杂度分别为（）、（）因此算法迭代一次时间复杂度为（），考虑到网络拓扑的稀疏性，时间复杂度可简化为（）综合以上分析，假设算法在经历 次迭代后达到收敛，整个算法的时间复杂度将不超过（），线性接近于网络规模，具有较低的时间复杂度 结论我们设计了一种融合节点内容的统一化半监督社团检测模型，同时结合了网络拓扑、节点内容信息和先验信息 该模型不仅可借助节点内容减小链接丢失的负面影响，亦可挖掘网络中结构信息来强化拓扑刻画社团的能力，具有更优的社团发现性能和鲁棒性 其关键思想在于基于统一的非负矩阵分解框架充分地整合拓扑、内容和先验信息，同时运用非负矩阵分解优化以处理 模型的参数学习，并设计了具有收敛保障的高效更新规则 实验结果证实了 模型识别网络中社团结构的优越性能本文中的真实网络显示拓扑与内容具有较强同质性，即拓扑和内容刻画一致的社团 因此，我们未来将致力于设计能够检测具有非同质拓扑和内容网络中的社团结构的模型 具体可以通过空间映射等思想尝试实现 此外，新模型中社团个数需要预设，社团个数的自确定也是我们未来需要解决的问题之一参考文献 ，：，：，（）：，：，：胡云，张舒，佘侃侃，等 基于重叠社区发现的社会网络推荐算法研究 南京师大学报（自然科学版），（）：黄立威，李彩萍，张海粟，等 一种基于因子图模型的半监督社区发现方法 自动化学报，（）：陈俊宇，周刚，南煜，等 一种半监督的局部扩展式重叠社区发现方法 计算机研究与发展，（）：，：，：，（）：，（）：，：，：，：，：，：，：，南京师大学报（自然科学版）第 卷第 期（年），：，（）：，（）：，：，：，：，：，：，（）：，：，（）：，：，：，：（），：，：，（）：，（）：，（）：，：，：，（）：责任编辑：杜忆忱