CN113378075A - 一种自适应融合网络拓扑和节点内容的社团发现方法 - Google Patents

Abstract

本发明公开了一种自适应融合网络拓扑和节点内容的社团发现方法，属于复杂网络分析技术领域，该方法挖掘社交网络数据集中社团结构，运用节点社团隶属度和图正则项分别建模网络拓扑和节点内容，然后引入自适应因子对所述网络拓扑和节点内容进行融合，以构建基于图正则化的自适应社团检测模型；最后使用评价算法归一化互信息熵评估模型有效性。本发明的有益效果为：利用自动编码器以及图正则整合了网络拓扑和节点内容，另一方面引入自适应因子缓解了社团发现过程中网络拓扑和节点内容的不匹配性。

Description

一种自适应融合网络拓扑和节点内容的社团发现方法

技术领域

本发明涉及复杂网络分析技术领域，涉及一种自适应融合网络拓扑和节点内容的社团 发现方法。

背景技术

在真实的社交网络生活中，存在着大量的网络化数据集，例如社交网络、通信网络等， 它们通常可形式化为复杂网络。对于复杂网络的分析，找到由密集连接的节点组成的社区 非常重要。通常，在分析社交网络时，社团发现可以帮助找到兴趣和目的相似的用户组， 并预测属于社区的用户的行为。复杂网络同时包含了网络拓扑和丰富的内容信息，这些内 容信息可辅助网络拓扑以提高社团发现的能力。但是，在真实网络场景中，网络拓扑与节 点内容信息所刻画的社团结构上存在不匹配性。这使得融合的节点内容信息可能与网络拓 扑在社团发现过程中存在相悖的作用，出现融合网络拓扑和节点内容的社团发现执行能力 低下的结果。如何有效地挖掘具有内容网络、网络拓扑与节点内容不匹配的社团结构，亟 需一种新的社团发现方法。

发明内容

本发明提供了一种自适应融合网络拓扑和节点内容的社团发现方法，主要是针对社团 发现中网络拓扑和节点内容之间的不匹配性以及社团的表征能力不足的技术问题而提出 的，本发明针对不匹配性，引入自适应因子作为融合网络拓扑和节点内容的平衡因子，以 缓解这两种信息不匹配时仍可提高社团发现的质量；基于自动编码器框架构建的模型，利 用其神经网络学习非线性表征，以提高社团隶属度表征社团结构的能力，对融合网络拓扑 和节点内容社团发现理论扩展以及良好应用价值。

本发明的思想为：首先，获得描述网络拓扑的节点之间链接、描述节点内容信息的节 点上文本特征等数据；然后，分别对网络拓扑、节点内容进行矩阵化处理，并分别进行模块度转化和相似度转化；接着，我们基于自动编码器和非负矩阵分解理论相似性，以及利用图正则化描述属于相同社团的节点的内容具有相似的假设，同时引入自适应因子平衡拓扑和内容融合比例，构建自适应融合网络拓扑和节点内容的社团发现模型；最后，通过模型优化推导出模型参数，对模型参数进行聚类，运用评价算法计算聚类结果和原始社团结构近似程度，以评估模型的性能。

本发明所采用的技术方案是：一种自适应融合网络拓扑与节点内容的社团发现方法， 所述方法包括以下步骤：

S1、带有内容信息的复杂网络数据表示为G＝(V，E，Q)，其中V＝{v₁，v₂，…，v_n} 表示节点的集合，E＝{e₁，e₂，…，e_m}表示边的集合，Q表示节点内容的特征向量集合；

S2、形式化构建网络拓扑和节点内容信息；

S3、运用节点社团隶属度和图正则项分别构建网络拓扑和节点内容，分别对应该方法 的模型中两个子模型，基于网络拓扑和节点内容不匹配性构建自适应因子；

S4、使用步骤S3所述的两个子模型和自适应因子在统一框架下结合为一个模型，并在 数据集上对其进行验证，使用归一化互信息熵作为评估算法对统一模型的有效性进行评价。

本发明提供的一种自适应融合网络拓扑与节点内容的社团发现方法进一步优化方案， 所述步骤S2具体包括：

S2.1、形式化构建网络拓扑，具体过程如下：构建G的邻接矩阵

其中a_ij＝1表示节点v_i和v_j之间有边，a_ij＝0表示无边，然后，基于A构建模块矩阵

其中，b_ij表示节点v_i和v_j之间的链接强度，k_i表示节点v_i的度，m表示边的总条数，k_ik_j/2m表示两节点之间期望边的条数；

S2.2、形式化构建节点内容，具体过程如下：构建Q的特征矩阵

矩阵Q每行表示一个节点上的内容，形式为一个r维特征向量，然后，基于Q构建节点之间内容相 似度矩阵

其中，u_ij表示节点v_i和v_j的特征向量的余弦相似度；

本发明提供的一种自适应融合网络拓扑与节点内容的社团发现方法进一步优化方案， 所述步骤S3具体包括：

S3.1、构建基于拓扑信息的第一子模型。根据自动编码器和非负矩阵分解(NMF)理论相似性，使用自动编码器框以实现模块度最大化tr(H_l ^TBH_l)，子模型参数为自动编码器的隐层中网络拓扑表征矩阵为H_l，其中B为自动编码器重构B的数据，从而得到第一子模型 的目标函数为：

S3.2、构建基于节点内容的第二子模型，根据相似度矩阵U和图正则项tr(H_c ^TLH_c)，子 模型参数为节点内容表征矩阵H_c，其中拉普拉斯矩阵L＝D–U，D＝diag(d₁，d₂，…，dn) 是对角矩阵，其中，d_i是相似度矩阵U每行元素之和，第二子模型的目标函数如下：

S3.3、构建网络拓扑和节点内容不匹配性构建自适应因子，基于步骤S3.1和S3.2中设 计的网络拓扑表征矩阵为H_l和节点内容表征矩阵H_c，运用矩阵之间的映射H_c≈H_lP获取 表示网络拓扑和节点内容之间关系的映射矩阵P，基于生成框架，利用表征矩阵H_l和H_c拟合描述匹配程度的P并做归一化处理，以描述网络拓扑与节点内容之间的匹配程度：

基于匹配程度函数，构建融合网络拓扑和内容信息的自适应因子：

其中，arctan(*)是反正切函数，κ表示网络G的社团个数。

本发明提供的一种自适应融合网络拓扑与节点内容的社团发现方法进一步优化方案， 所述步骤S4具体包括：

将步骤S3中基于网络拓扑第一子模型O(H_l)、基于节点内容的第二子模型O(H_c)有机融 合，利用基于网络拓扑和节点内容不匹配性构建自适应因子调节不同子模型比重，然后， 基于H_c≈H_lP构建为一个统一的模型，设置H_l为H，自适应因子改为：

其中

将矩阵H和P作为最终统一模型的模型参数，统一模型的目标函数为：

基于目标函数最小化，模型参数矩阵H和P迭代更新，直至目标函数的值达到收敛.最后， 得到参数矩阵H，即节点的社团隶属度矩阵，基于社团隶属度矩阵H聚类以进行社团检测。

与现有技术相比，本发明的有益效果为：本发明一方面利用自动编码器以及图正则融 合网络拓扑和节点内容，另一方面缓解了社团发现方法对拓扑和内容不匹配性的敏感，自 适应融合这两种信息；同时基于自动编码器神经网络结构增强了社团隶属度的表征社团的 能力，进一步提高了融合拓扑与内容社团发现的质量；在网络拓扑与节点内容匹配的时候， 提高社团发现的执行力；在网络拓扑与节点内容不匹配的时候，亦减缓节点内容与网络拓 扑相悖作用，仍能提高社团发现的执行力。同时，亦需要新方法获取的社团隶属度具有更 好表征社团能力。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施例 一起用于解释本发明，并不构成对本发明的限制。

图1为本发明自适应融合网络拓扑和节点内容的社团发现方法的整体流程示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发 明进行进一步详细说明。当然，此处所描述的具体实施例仅用以解释本发明，并不用于限 定本发明。

实施例1

参见图1、表1和表2，本发明提供其技术方案为，一种自适应融合网络拓扑与节点内 容的社团发现方法，

(1)、使用数据集获取社团信息。使用公共数据集获取社团信息，社团信息G＝(V，E， Q)：V是点{v₁，v₂，…，v_n}的集合，E＝{e₁，e₂，…，e_m}是边的集合，Q是点的特征向量 的集合，κ是社团个数，本发明自适应融合网络拓扑和节点内容的社团发现方法的实验数 据集如表1所示：

表1实验数据信息

其中，Citeseer是一个引文网络，由6个子领域的3312篇科学出版物组成，涉及4732条引 文关系，WebKB网络由4个子网络组成，这些子网络数据分别是从Cornell、Texas、Washington、Wisconsin四所大学收集而来的网页(带有1703维的二元单词属性)数据集，每个子网络包含5个社团。

(2)、根据(1)中获取拓扑信息、节点的内容步骤如下：

根据表1中数据，构建G的邻接矩阵

其中a_ij＝1表示节点v_i和v_j之间有边，a_ij＝0表示无边，然后，基于A构建模块矩阵

然后， 对于节点内容，构建Q的特征矩阵

矩阵Q每行表示一个节点上的内容，形式为 一个r维特征向量，然后，基于Q构建节点之间内容相似度矩阵

(3)、基于网络拓扑构建拓扑第一模型和基于节点内容构建第二子模型，同时引入基于 拓扑与内容匹配程度的自适应因子，降低融合模型对这两种信息不匹配性的敏感；使用自 适应因子将两个子模型统一为最终的模型，得到目标函数为：

自适应因子形式化为：

其中

其中，arctan(*)是反正切函数，κ表示网络G的社团个数，

表示表征社团的社团隶 属度矩阵，映射矩阵

表示网络拓扑和节点内容之间关系。

(4)、基于自动编码器框架的梯度下降法，对H和P不断迭代更新，直至其达到收敛后得到表征矩阵H，最终获知所有节点的社团归属。

(5)、使用归一化互信息熵(NMI)作为模型的评估指标，归一化互信息熵将互信息归 一化到[0，1]之间，基于混淆矩阵C，该矩阵每一列表预测值，每一行表示实际类别，一般用来呈现算法性能的可视化效果，具体表达式如下：

(6)、本实验将所提出的模型在五个公共数据集上进行测试，本发明自适应融合网络拓 扑和节点内容的社团发现方法的实验结果如表2所示：

表2基于公共数据集的测试结果

从表2分析可以看出，本发明提出的方法在5个具有内容信息和拓扑信息的公共数据 集上进行模型有效性验证，同时计算了该方法在不同数据集上基于标准互信息熵(NMI)的平 均值。在数据集Citeseer、Texas、Wisconsin上，基于NMI计算，该方法获得的社团划分和 数据集的真实社团划分相似度分别为35.11、39.40、36.67，均超过了平均水平31.39。其中， 在数据Wisconsin上，该方法获取的社团结构和数据集的真实社团划分更是接近40。尽管 该方法在数据集Cornell上表现仅为18.93，但就总体而言，本发明提出的方法自适应融合 网络拓扑和内容信息在真实数据集上表现出不错的社团检测执行能力。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则 之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (4)

1.一种自适应融合网络拓扑和节点内容的社团发现方法，其特征在于，所述社团发现方法包括以下步骤：

S1、带有内容信息的复杂网络数据表示为G＝(V，E，Q)，其中V＝{v₁，v₂，…，v_n}表示节点的集合，E＝{e₁，e₂，…，e_m}表示边的集合，Q表示节点内容的特征向量集合；

S2、形式化构建网络拓扑和节点内容信息；

S3、运用节点社团隶属度和图正则项分别构建网络拓扑和节点内容，分别对应该方法的模型中两个子模型，基于网络拓扑和节点内容不匹配性构建自适应因子；

S4、使用步骤S3所述的两个子模型和自适应因子在统一框架下结合为一个模型，并在数据集上对其进行验证，使用归一化互信息熵作为评估算法对统一模型的有效性进行评价。

2.根据权利要求1所述的自适应融合网络拓扑和节点内容社团发现方法，其特征在于，所述步骤S2具体包括：

S2.1、形式化构建网络拓扑，具体过程如下：构建G的邻接矩阵

其中a_ij＝1表示节点v_i和v_j之间有边，a_ij＝0表示无边，然后，基于A构建模块矩阵

其中，b_ij表示节点v_i和v_j之间的链接强度，k_i表示节点v_i的度，m表示边的总条数，k_ik_j/2m表示两节点之间期望边的条数；

S2.2、形式化构建节点内容，具体过程如下：构建Q的特征矩阵

矩阵Q每行表示一个节点上的内容，形式为一个r维特征向量，然后，基于Q构建节点之间内容相似度矩阵

其中，u_ij表示节点v_i和v_j的特征向量的余弦相似度。

3.根据权利要求1或2所述的自适应融合网络拓扑和节点内容社团发现方法，其特征在于，所述步骤S3具体包括：

S3.1、构建基于拓扑信息的第一子模型：根据自动编码器和非负矩阵分解(NMF)理论相似性，使用自动编码器框以实现模块度最大化tr(H_l ^TBH_l)，子模型参数为自动编码器的隐层中网络拓扑表征矩阵为H_l，其中

为自动编码器重构B的数据，从而得到第一子模型的目标函数为：

S3.2、构建基于节点内容的第二子模型：根据相似度矩阵U和图正则项tr(H_c ^TLH_c)，子模型参数为节点内容表征矩阵H_c，其中拉普拉斯矩阵L＝D–U，D＝diag(d₁，d₂，…，dn)是对角矩阵，其中，d_i是相似度矩阵U每行元素之和，第二子模型的目标函数如下：

S3.3、构建网络拓扑和节点内容不匹配性构建自适应因子：基于步骤S3.1和S3.2中设计的网络拓扑表征矩阵为H_l和节点内容表征矩阵H_c，运用矩阵之间的映射H_c≈H_lP获取表示网络拓扑和节点内容之间关系的映射矩阵P，基于生成框架，利用表征矩阵H_l和H_c拟合描述匹配程度的P并做归一化处理，以描述网络拓扑与节点内容之间的匹配程度：

基于匹配程度函数，构建融合网络拓扑和内容信息的自适应因子：

其中，arctan(*)是反正切函数，κ表示网络G的社团个数。

4.根据权利要求1-3任一项所述的自适应融合网络拓扑和节点内容社团发现方法，其特征在于，所述步骤S4具体包括：

将步骤S3中基于网络拓扑第一子模型O(H_l)、基于节点内容的第二子模型O(H_c)有机融合，利用基于网络拓扑和节点内容不匹配性构建自适应因子调节不同子模型比重，然后，基于H_c≈H_lP构建为一个统一的模型，设置H_l为H，自适应因子改为：

其中

将矩阵H和P作为最终统一模型的模型参数，统一模型的目标函数为：

基于目标函数最小化，模型参数矩阵H和P迭代更新，直至目标函数的值达到收敛，得到参数矩阵H，即节点的社团隶属度矩阵，基于社团隶属度矩阵H聚类以进行社团检测。

Images