一种针对复杂网络的混合型聚类方法

摘要

本发明提出一种针对复杂网络的混合型聚类方法，属于社区网络的数据挖掘领域。本发明方法首先利用基于启发式的聚类方法分割复杂网络，在其中设置了优化终止函数和迭代终止阈值，以得到一个比较良好的网络社区划分结果，然后再利用基于优化的聚类方法合并网络，通过计算终止优化终止函数，保存最优的网络社区划分结果，最后输出该社区结构。本发明方法对大规模复杂网络进行社区划分或者聚类，社区划分结果良好，并且在提高基于连接聚类系数的GN算法精度的同时没有时间损失，可保证良好的用户体验。

主权项

一种针对复杂网络的混合型聚类方法，其特征在于，该方法包括如下步骤：步骤1：构建整个网络的无向图，统计整个网络中的所有节点和边，为每个节点顺序编号，设节点总数为N，p为节点的编号，1≤p≤N；标记节点p和节点q之间的边为e_pq，1≤p≤N，1≤q≤N，p≠q；步骤2：初始将网络中的所有节点划分到一个社区中；步骤3：确定网络中的每条边e_pq的连接聚类系数EdgeClusteringCoefficient：其中，Traid表示是节点p和节点q共同的邻居节点的个数，srcdeg表示节点p的度，destdeg表示节点q的度，min()表示取较小值；步骤4：找到当前连接聚类系数值最大的边，标记为e_AB，连接边e_AB的节点为A和B，删除连接聚类系数值最大的那条边e_AB，判断节点A和节点B之间是否存在连通的路径，若不存在，更新网络中的社区，然后执行下一步骤；若存在，转步骤3执行；更新网络中的社区，具体是：标记节点A和节点B在未更新社区前都属于社区s，s为社区编号，将社区s中能连通节点A的节点划分到一个社区s_A，将社区s中能连通节点B的节点划分到一个社区s_B，然后更新社区的总数k＝k+1，将社区s_A记为社区s，社区s_B记为第k个社区；所述的步骤4中判断节点A和节点B之间是否存在连通的路径，具体包括如下步骤：步骤4.1：构建一个队列Queue和一个哈希表Hash，初始将节点A放入队列Queue中，设置节点A的哈希值Hash(A)＝0，节点N的哈希值Hash(N)表示节点N到节点A的距离；步骤4.2：从队列Queue中取出一个节点记为N，如果N＝B，找到节点A和B之间的最短路径，Hash(B)＝Hash(N)，执行步骤4.4；否则，找到节点N的所有邻居节点N_p，将N_p放入队列Queue中，并设置Hash(N_p)＝Hash(N)+1，N_p表示节点N的第p个邻居节点，然后执行步骤4.3；步骤4.3：判断队列Queue是否为空，若否，转步骤4.2执行；若是，设置Hash(B)＝‑1，执行步骤4.4；步骤4.4：判断Hash(B)是否为‑1，若否，节点A和节点B之间存在连通的路径，若是，节点A和节点B之间不存在连通的路径；步骤5：获取当前网络中的社区，并确定当前网络所划分的社区的模块性评价指标值CurQ：其中，AVE为平均数，k代表网络中社区的总数，c_s代表当前网络中社区s与其他社区之间连接的边的数量，m_s代表社区s内的边的数量，m代表整个网络的边数；设置变量BestQ表示到目前为止最好的社区划分所对应的模块性评价指标值，初始赋值为0；设置变量steps用于标记当前迭代次数与BestQ所对应的迭代次数的差值，初始值为0；判断CurQ与BestQ的大小：如果BestQ<＝CurQ，令BestQ＝CurQ，保存当前所划分的社区结构，更新迭代次数steps＝0，转步骤3执行；如果BestQ>CurQ，更新迭代次数steps＝steps+1，并判断steps是否小于用户设定的阈值threshold，若否，转步骤3执行，若是，执行步骤6；步骤6：列举网络中当前存在的所有社区的两两组合，每个组合中不是相同的社区，针对每个组合，确定合并该组合中的两个社区i和j后，确定网络所划分的社区的模块性评价指标值Q_ij：其中，d_s表示社区s中节点度之和；找到计算得到最大的Q_ij：max(Q_ij)，将最大Q_ij对应的两个社区合并，然后执行步骤7；步骤7：令变量CurQ＝max(Q_ij)；判断CurQ与BestQ的大小，如果BestQ<＝CurQ，更新变量BestQ＝CurQ，保存当前网络中的社区结构，然后执行步骤8；如果BestQ>CurQ，直接执行步骤8；步骤8：判断当前网络是否已经组合为一个社区，若是，执行步骤9，若否，转步骤6执行；步骤9：将最终保存的社区结构输出。