(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210936871.9 (22)申请日 2022.08.05 (71)申请人 东北电力大 学 地址 132000 吉林省吉林市船 营区长春路 169号 (72)发明人 姜万昌　张晓茜　王圣达　郭健　 刘丹妮　 (74)专利代理 机构 北京中理通专利代理事务所 (普通合伙) 11633 专利代理师 刘慧宇 (51)Int.Cl. G06K 9/62(2022.01) G06Q 50/26(2012.01) (54)发明名称 基于公共邻居节点聚类熵紧密相似性的社 区检测方法 (57)摘要 基于公共邻居节点聚类熵紧密相似性的社 区检测方法， 该方法涉及复杂网络技术领域， 解 决现有基于相似性的社区检测方法没有考虑不 同节点对之间公共邻居节点的差异造成节点对 无法区分、 社区检测低效的问题， 本发明通过初 始化网络G， 定义公共邻居节点聚类熵， 计算公共 邻居节点聚类熵的紧密相似性， 根据紧密相似节 点集获得最紧密相似的节点， 创建初始社区并对 所形成的初始社区进行合并优化更新获得最终 社区等步骤实现。 本发明方法在真实网络中检测 到的社区结构更加接近实际社区结构， 同时社区 结构也具有较高的模块度值。 权利要求书3页 说明书7页 附图2页 CN 115169501 A 2022.10.11 CN 115169501 A 1.基于公共邻居节点聚类熵紧密相似性的社区检测方法， 其特征是： 该方法由以下步 骤实现： 步骤一、 初始化网络G＝(V,E)； V＝{vi|i＝1,2,...,n}为网络G的n个节点的集合， E＝ {eij|i＝1,2,...,n,j＝1,2,...,n,i≠j}为网络G的m条边的集合， 这里eij＝(vi,vj)是从节 点vi到节点vj的边， 其中eij＝eji； 步骤二、 定义公共邻居节点聚类熵C Ez； 对于网络G 中任意两个节点vi和vj， 如果节点vi和vj之间存在一条边eij， 则vi和vj的节点 对为＜vi,vj＞， 即节点vi和vj互为一阶邻居节点vi∈N(vj),vj∈N(vi)， 其中， N(vi)和N(vj) 分别表示节点vi和vj的所有一阶邻居节点的集 合； 设定节点 为节点vi和vj的一阶邻居节点， 即 则节点 为节点对＜ vi,vj＞的公共邻居节点， CN(vi,vj)为节点对＜vi,vj＞的公共邻居节点集； 对于节点对＜ vi,vj＞的公共邻居节点集CN(vi,vj)中的每一个公共邻居节点 使用公共邻居节点 的 聚类系数来衡量公共邻居节点 对它的一阶邻居节点的紧密度， 定义公共邻居节 点聚类熵 CEz为： CEz＝‑CCz×log2CCz 式中， 为公共邻居节点 的聚类系数； 表示公共邻居节点 的一阶邻居节点之 间的所有连边的集 合； 为公共邻居节点 的度； 式中， 为公共邻居节点 的所有一阶邻居节点的集合； epq为节点vp和vq组成的 边； 步骤三、 定义基于公共邻居节点聚类熵的紧密相似性sim(vi,vj)； 所述节点对＜vi,vj＞的紧密相似 性通过节点vi和vj之间所有公共邻居的公共邻居节点 聚类熵计算， 定义基于公共邻居节点聚类熵C Ez的紧密相似性 为： 式中， d(vi)为节点vi的度， 当节点对＜vi,vj＞不存在公共邻居节点时， 即|CN(vi,vj)| ＝0， 根据节点vi的度d(vi)计算节点对＜vi,vj＞的紧密相似性； 步骤四、 根据步骤三获得的基于公共邻居节点聚类熵的紧密相似性sim(vi,vj)， 获得节 点vi的紧密相似节点集CSNS(vi)， 在CSNS(vi)中依据节点的领导力选出节点vi最紧密相似 的节点vj， 记为 步骤五、 从网络G中具有最大节点领导力的节点开始， 依次为网络G中的节点识别其紧 密相似节点集， 在紧密相似节点集中选出节点的最紧密相似节点， 将网络 G中的节点与其最权　利　要　求　书 1/3 页 2 CN 115169501 A 2紧密相似节点 合并创建初始社区Cinitial＝{C1,C2,...,Cn}； 步骤六、 对所 形成的初始社区Cinitial进行更新获得最终社区C 。 2.根据权利要求1所述的基于公共邻居节点聚类熵紧密相似性的社区检测方法， 其特 征在于： 步骤四的具体过程 为： 步骤四一、 设定紧密相似节点集是在 节点vi的所有一阶邻居节点中， 具有最大紧密相似 性的节点所构成的集 合， 定义紧密相似节点 集为： 式中， N(vi)＝{vj|eij∈E}是节点vi的所有一阶邻居节点的集 合； 步骤四二、 在节点vi的紧密相似节点集CSNS(vi)中， 节点vi的一阶邻居节点vj的领导力 Lj计算如下： 选择具有最大节点领导力的节点作为vi最紧密相似的节点vj， 记为 3.根据权利要求1所述的基于公共邻居节点聚类熵紧密相似性的社区检测方法， 其特 征在于： 步骤五的具体过程 为： 步骤五一、 计算网络G中所有节点的节点领导力并按节点领导力值降序排列， 网络G中 节点排序后的集 合为 步骤五二、 从具有最大节点领导力的节点开始处理每个节点 采用紧密相似性度 量， 识别节点 的紧密相似节点集 并将 中具有最大领导力的节点作为 节点 最紧密相似节点 步骤五三、 如果节点 已经属于某个社区， 则将节点 添加到节点 所在的社区， 否 则， 将 与 合并以创建新的社区； 依次访问和处理G中节点排序后的集合V'中所有节点， 直到每个节点属于一个社区从 而形成初始社区Cinitial， 对于V'中已经作为某一节点的最紧密相似的节点， 则不再为其识 别最紧密相似节点构造社区。 4.根据权利要求1所述的基于公共邻居节点聚类熵紧密相似性的社区检测方法， 其特 征在于： 步骤六的具体过程 为： 步骤六一、 计算Cinitial的模块度作为当前模块度Qcur， 根据模块度的定义： 式中， m为整个网络G的边数， Aij为网络G的邻接矩阵， Ci和Cj为节点vi和vj所在的社区， 如果vi和vj在同一个社区， 则 δ(Ci,Cj)＝1， 否则， δ(Ci,Cj)＝0； 步骤六二、 在第一层次合并中， 将Cinitial中的每两个社区Ci,Cj合并为临时社区Ctem， 并 计算临时模块度Qtem； 步骤六三、 在第二层次合并中， 如果最大临时模块度max  Qtem＞Qcur， 则将max  Qtem及其 所对应的社区Ctem更新为Qcur和当前社区Ccur； 重复步骤六二和步骤六三的两层次合并， 直到max  Qtem≤Qcur， 将Qcur所对应的社区作为权　利　要　求　书 2/3 页 3 CN 115169501 A 3