发展到现在已有许多划分方法,文献[42-44] 进行了详细的综述,其中社会学中的分级聚类和计算机科学中的图形分割是划分网络社团结构的两类主要方法。在分级聚类方法中应用较为广泛的是 GN 算法[45] 和 Newman 快速算法[46] 。其中 GN 算法是把网络中经过每条边的最短路径的条数定义为边介数,通过不断地从网络中移除最大的边介数从而将整个网络分解为各个社团; 而 Newman 快速算法它是一种基于贪婪算法思想的凝聚算法,初始时把每一个节点看成是独立的社团,计算模块度的增量 Q ?,合并使 Q 增大最多或者减少最小的社团对,然后重新计算合并后的模块度增量,不断合并社团,直到整个网络都合并成为一个社团为止。而图形分割算法最有名的是 Kernighan-Lin 算法[47] 和谱平分法[47] 。其中 Ke rn ighan-Lin 算法是基于贪婪法原理,根据使社团内部及社团间的边最优化的原则对原始的网络进行分类;谱平分法则根据网络的 Laplace 矩阵不为零的特征值所对应的特征向量的各元素中,同一个社团内的节点对应的元素是近似相等的思想,由第二小特征值将网络分为两个社团。此外,聚类复杂网络的另一个思路是:将网络聚类转化为向量聚类。通过给每个网络节点分配一个合理向量坐标,可以把网络聚类问题转换为节点聚类问题,进而采用 K-means 等经典聚类分析算法对这些节点进行聚类,最后将聚类结果还原为相应的社团结构。 Zhang 等[48] 采用谱平分方法获得特征向量矩阵,将网络聚类问题转换为传统的空间点聚类问题, 然后应用 FCM 算法和 K-means 算法对网络进行社团划分;赵凤霞等[49] 通过边的信息中心度来进行转化,然后应用 K-means 算法对网络进行社团划分;文献[50,51] 通过谱平分方法获得特征向量矩阵,分别应用聚类遗传算法和 Wu-Huberman 算法
全文预览
