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

摘要

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

主权项

一种针对复杂网络的混合型聚类方法，其特征在于，该方法包括如下步骤：步骤1：构建整个网络的无向图，统计整个网络中的所有节点和边，为每个节点顺序编号，设节点总数为N，i为节点的编号，1≤i≤N；标记节点i和节点j之间的边为eij，1≤i≤N，1≤j≤N，i≠j；步骤2：初始将网络中的所有节点划分到一个社区中；步骤3：确定网络中的每条边eij的连接聚类系数EdgeClusteringCoefficient： EdgeClusteringCoefficient ( e ij ) = Traid + 1 min ( srcdeg - 1 , destdeg - 1 ) 其中，Traid表示是节点i和节点j共同的邻居节点的个数，srcdeg表示节点i的度，destdeg表示节点j的度，min()表示取较小值；步骤4：找到当前连接聚类系数值最大的边，标记为eAB，连接边eAB的节点为A和B，删除连接聚类系数值最大的那条边eAB，判断节点A和节点B之间是否存在连通的路径，若不存在，更新网络中的社区，然后执行下一步骤；若存在，转步骤3执行；更新网络中的社区，具体是：标记节点A和节点B在未更新社区前都属于社区s，s代表网络中第s个社区，将社区s中能连通节点A的节点划分到一个社区sA，将社区s中能连通节点B的节点划分到一个社区sB，然后更新社区的总数k＝k+1，将社区sA记为第s个社区，社区sB记为第k个社区；步骤5：获取当前网络中的社区，并确定当前网络所划分的社区的模块性评价指标值CurQ： CurQ = AVE s k { C s 2 m s + c s + c s 2 ( m - m s ) - c s } 其中，AVE为平均数，s代表网络中第s个社区，k代表网络中社区的总数，cs代表在步骤1的网络中社区s与其他社区之间连接的边的数量，ms代表社区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后，确定网络所划分的社区的模块性评价指 标值Qij： Q ij = Σ s = 1 k [ m s m - ( d s 2 m ) 2 ] 其中，ds表示社区s中节点度之和；找到计算得到最大的Qij：max(Qij)，将最大Qij对应的两个社区合并，然后执行步骤7；步骤7：令变量CurQ=max(Qij)；判断CurQ与BestQ的大小，如果BestQ<=CurQ，更新变量BestQ=CurQ，保存当前网络中的社区结构，然后执行步骤8；如果BestQ>CurQ，直接执行步骤8；步骤8：判断当前网络是否已经组合为一个社区，若是，执行步骤9，若否，转步骤6执行；步骤9：将最终保存的社区结构输出。