一种基于K-means改进的社区发现算法

传统的社区发现算法往往时间复杂度较高,K-means算法作为聚类算法且时间复杂度较低可为社区发现提供新思路,但K-means算法的原始应用场景为数值环境与社交网络不符,且自身存在初始中心节点选取敏感等原有问题,针对上述问题本文在下面三个方面进行了优化：第一,结合最短路径及共同邻居信息重新定义距离度量;第二,结合了节点的度和节点距离因素进行初始中心节点选取;第三,在K-means算法结果的基础上进行基于贪心策略以模块度为目标的层次聚类优化。通过实验表明：改进的K-means算法能够很好地应用于社区发现,得到的社区发现结果有较高质量。     

边异质网络中的社区结构发现算法

为解决社区结构发现算法功能社区与拓扑社区不一致的问题,提出一种基于边类型相似性聚类(TESC)的社区结构发现算法。该算法以局部拓扑特征与异质信息为目标进行节点聚类,基于节点邻接边类型构造网络节点之间的相似矩阵,从而获取边异质信息。在该相似矩阵的基础上,通过传统层次聚类的思想将相似度大的节点进行合并,进而利用轮廓系数优化社区数量,得到最终社区划分结果。选取社区结构已知的4个真实网络和6个人工合成基准LFR网络,通过与同质网络的GN、Louvain算法以及异质网络的Hete-SPAEM、Hetero-Attractor算法对比,结果表明TESC算法获得的社区结构更接近于网络实际社区结构。     

基于K-means聚类算法的复杂网络社团发现新方法

提出了一种基于K-means聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了K-means聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

面向异质信息网络的双通道协同聚类算法

网络聚类广泛应用于现实世界的各个领域，受到了越来越多的关注.由于保留了节点和链接关系的异质性，异质信息网络聚类相较于同质网络聚类具有更优的性能.然而，现有基于图神经网络的异质信息网络聚类忽略了节点属性以及拓扑结构对聚类的权重不同的问题.此外，这些方法仅对单一类型的目标节点聚类，而没有考虑其余类型节点的辅助作用.为此，提出了面向异质信息网络的双通道协同聚类算法（B3C），其能够有效地融合节点属性和拓扑结构，并挖掘异质节点间的潜在相关性，从而提高聚类性能.首先，设计了一个简单有效的双通道编码器以聚合拓扑结构及相似矩阵的邻域信息；接着，应用自训练聚类的同时学习异质信息网络表示以及优化聚类分配，并采用协同聚类机制，以对不同类型节点同时聚类；最后，利用三元中心损失（Triplet-Center Loss）学习具有区分度的节点表示，以凝聚相似节点，分离不相似节点.在公开数据集上进行了大量实验，验证了本文提出的双通道编码器性能相较于广泛使用的图神经网络编码器有显著提升，并且B3C精度优于现有的基于学习的异质信息网络聚类方法.     

基于同质子图变换的异质网络表示学习

目前针对信息网络的研究多数基于同质网络,关于异质信息网络的网络表示学习研究相对较少。为此,提出一种结合不同元路径将异质信息网络转化成带权同质子图的网络表示学习算法。基于不同元路径在同类节点间构建带权重的连边,从异质网络中抽取出带权同质子图,通过带偏置的随机游走方式得到同类节点序列,并利用Skip-gram模型生成该类节点的表示向量。实验结果表明,与只考虑单一路径的算法相比,该算法处理节点分类、相似性搜索等数据挖掘任务时均能得到较好的效果。     

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

基于中心度的标签传播时间序列聚类方法

为了实现时间序列自动聚类,以及更为细致地描述时间序列之间的结构关系,引入社区发现方法来研究时间序列聚类.针对标签传播方法在标签传播过程中具有较强不确定性,以及算法对网络结构较为敏感等问题,提出一种基于中心度的标签传播时间序列聚类方法;通过构建时间序列网络空间结构,将每条时间序列看作一个节点,根据每个节点的中心度来得到标签更新顺序;计算节点对于每个簇的归属度,再利用节点的归属度和标签的传播实现节点的划分,从而实现时间序列聚类.所提方法通过分析时间序列之间的连接关系来发现其在欧氏空间的结构特征,进而实现空间结构的有效划分.实验结果表明,所提方法无需确定初始簇中心,能够有效划分人工数据网络和真实社会网络,在时间序列数据聚类中取得了良好的聚类效果.     

快速混合Web文档聚类

提出了一种使用后缀树聚类算法优化K-means文档聚类初始值的快速混合聚类方法STK-means。该方法首先构建文档集的后缀树模型,使用后缀树聚类算法识别初始聚类、提取K-means聚类算法初始值中心值。然后,把后缀树模型的节点映射到M维向量空间模型中的特征项,利用TF-IDF方案计算基于短语的文档向量特征值。最后,使用K-means算法产生聚类结果。实验结果表明该方法优于传统K-means聚类算法和后缀树聚类算法,并具备了这些算法聚类速度快的优点。     

支持向量机优化基于K-means的蚁群聚类算法

基于K-means算法思想改进蚁群聚类算法聚类规则,提出一种新的K-means蚁群聚类算法,并通过实验验证其聚类效果;引入具有全局最优性的支持向量机SVM,取各类中心附近适当数据训练支持向量机,然后利用已获模型对整个数据集进行重新分类,进一步优化聚类结果,使聚类结果达到全局最优。UCI数据集实验结果表明,新的算法可以明显提高聚类质量。     

基于SOM网和K-means的聚类算法

K-means算法因对初始中心依赖性而导致聚类结果可能陷入局部极小.而恰当的选取初始中心向量就成为改进K-means算法的关键所在.因此可以先通过SOM进行聚类,较快确定聚类范围,再将其结果作为K-means方法的初始中心向量加以使用.实验证明结合这两种算法能够弥补这两种方法的缺陷,较好改善聚类效果.