针对复杂网络的基于群思想改进的Fast-Newman聚类方法

摘要

本发明公开了一种应用于复杂网络的基于群思想改进的Fast-Newman聚类方法，引入群的思想，根据复杂网络簇结构特点，定义了相邻簇概念，改进了Newman提出的模块性评价函数，并保存最大的模块性评价函数值，使得聚类精度避免了在达到全局最大值时并非最高的问题，得到的聚类结果能够更加准确地刻画真实的网络簇结构。本发明方法对大规模复杂网络聚类分析的精度比原FN聚类方法有显著提高，对于常见的具有规模大、连接稀疏且关系不均匀的复杂网络，聚类效果尤其突出。

主权项

一种针对复杂网络的基于群思想改进的Fast‑Newman聚类方法，其特征在于，具体包括如下步骤：步骤1：统计网络中的所有节点，并为每个节点顺序编号，设节点总数为N，i为节点的编号，1≤i≤N，对网络中的每个节点i，设置其所在的社区号为i；步骤2：为每个节点i创建一个社区结构，并为各社区设置用于表示该社区是否存在的存活标记alive，将节点i加入社区i的社区成员中，设置该社区结构的参数alive的值为ture，ture表示该社区存在，false表示该社区不存在；设置当前网络中存在的社区总数nalive为网络中总的节点数N；步骤3：对每个社区i，确定其内部的边数in_edge[i]以及其内部的度数degree[i]；步骤4：对每对社区i，j，确定两者之间的边数cross_edge[i][j]，1≤i≤N，1≤j≤N，且i≠j；步骤5：确定每个社区i的模块性评价函数值Q′[i]： Q ′ [ i ] = Σ i = 1 nalive [ m i m - d i 2 m q d q 2 m ] - - - ( 1 ) 其中，m代表整个网络的边数，mi代表社区i内的边数in_edge[i]，di代表社区i内所有节点的度之和degree[i]，q代表社区i对应的群，mq代表群q内的边数，dq代表群q内所有节点的度之和；社区i对应的群q是指社区i与社区i相邻社区的集合；所述的相邻社区的定义为：若社区i中至少存在一个节点与社区p中任意节点存在至少一条连边，则社区i与社区p就是相邻社区；步骤6：设置变量maxQ′，用于保存当前网络中社区的最大Q′值；步骤7：判断当前网络中是否存在大于一个的社区，若存在，则列举当前网络中所有的社区对i、j，然后执行步骤8；否则，执行步骤12；1≤i≤nalive，1≤j≤nalive，且i≠j；步骤8：判断当前网络中所有的社区对是否都已经被取过，若没有，任意取一对没有取过的社区对i，j，若全部被取过，转步骤12执行；步骤9：判断社区i和社区j之间是否存在连接的边，若存在，执行步骤10，若不存在，转步骤8执行；步骤10：假定将社区i和社区j进行合并得到新社区i′，i′为新社区号，确定新社区i′的内部的总边数in_edge[i′]以及内部的总度数degree[i′]，然后确定新社区i′的模块性评价函数值Q′[i′]： Q ′ [ i ′ ] = Σ i ′ = 1 nalive ′ [ m i ′ m - d i ′ 2 m q ′ d q ′ 2 m ] - - - ( 2 ) 其中，nalive′为假定将社区i和社区j进行合并情况下的当前网络中存在的社区总数，其值为当前网络中存在的社区总数nalive‑1；q′代表社区i′对应的群，m代表整个网络的边数，mi′代表社区i′内的边数in_edge[i′]，mq′代表群q′内的边数，di′代表社区i′内所有节点的度之和，dq′代表群q′内所有节点的度之和；步骤11：比较得到的模块性评价函数值Q′[i′]是否大于当前的最大Q′值的变量maxQ′，若否，不作更新，转步骤8执行；若是，更新maxQ′的值为新社区的模块性评价函数值Q′[i]，并将社区j合并到社区i中，然后转步骤7执行；步骤12：保存当前变量maxQ′中最大Q′值，以及最终社区划分结构，然后结束本方法。