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

摘要

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

主权项

1.一种针对复杂网络的基于群思想改进的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]： 其中，m代表整个网络的边数，m_i代表社区i内的边数in_edge[i]，d_i代表社区i内所有节点的度之和degree[i]，q代表社区i对应的群，m_q代表群q内的边数，d_q代表群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']： 其中，nalive'为假定将社区i和社区j进行合并情况下的当前网络中存在的社区总数，其值为当前网络中存在的社区总数nalive-1；q'代表新社区i'对应的群，m代表整个网络的边数，m_i'代表新社区i'内的边数in_edge[i']，m_q'代表群q'内的边数，d_i'代表新社区i'内所有节点的度之和，d_q'代表群q'内所有节点的度之和； 所述的新社区i'内部的总边数in_edge[i']，是将社区i的内部边数加上社区j的内部边数，再加上社区i和社区j之间连接的边数得到，所述新社区i'内部的总度数degree[i']是将社区j的度数加社区i的度数得到； 步骤11：比较得到的模块性评价函数值Q'[i']是否大于当前的最大Q'值的变量maxQ'，若否，不作更新，转步骤8执行；若是，更新maxQ'的值为新社区的模块性评价函数值Q'[i']，并将社区j合并到社区i中，然后转步骤7执行； 步骤12：保存当前变量maxQ'中最大Q'值，以及最终社区划分结构，然后结束本方法。