网络社团挖掘算法  

Network communities detection algorithm

作　　者：刘启刚[1] 孙向阳[1] 周丽[1] 

机构地区：[1]上海大学悉尼工商学院,上海201800

出　　处：《计算机应用》2015年第A01期18-21,共4页journal of Computer Applications

摘　　要：针对K平均(K-means)、期望最大化(EM)等传统聚类算法在网络社团挖掘中存在的聚类结果不合理、容易陷入局部最小值等问题,以最小化社团间的连接权值为优化目标,基于节点间交互次数归一化结果建立节点间的相似矩阵,求出此矩阵对应的拉普拉斯矩阵,以拉普拉斯矩阵的前k个最小特征值对应的特征向量为基建立新的特征空间,将相似矩阵向新的特征空间做投影,在投影后的特征空间中运用K-means算法进行社团挖掘,实现目标函数的最小化。通过仿真实验对比,说明了该基于拉普拉斯矩阵的聚类方法(LMBC)比传统聚类方法更有效地解决聚类节点分布不均衡的问题,及非凸、高维数据集在保持原有几何结构的同时有效降维的问题。LMBC从数据集相似矩阵的角度进行聚类分析,进一步丰富了流形学习的理论与方法,可广泛应用于社交网络分析及图像识别等领域。In view of problems on unreasonable clustering result and easy to fall into local minimum of traditional clustering algorithms, i. e. K-means, Expectation Maximitation （ EM） when they are applied to communities detection, in this study an different approach was proposed. It set minimizing the link weights between different communities as the optimization objective, built a similarity matrix based on normalization result of interaction times between network nodes, inferred the corresponding Laplacian matrix of this similarity matrix, established a new eigenspace based on the corresponding eigenvectors of the first k smallest eigenvalues, made a projection of the similarity matrix on the new eigenspace, did clustering on the projection eigenspace by K-means, finally, accomplished the minimization of objective function. Simulation experiment was done to illustrate that Laplacian Matrix Based Clustering （ LMBC ） can effectively resolve the problems of unbalancing distribution of network nodes and dimensionality reduction of non-convex high dimensional dataset while keeping the geometric structure. LMBC enriches the manifold learning theory and methodology by doing clustering on the dataset similarity matrix, and it can be widely used in social network analysis and image recognition areas.

关 键 词：拉普拉斯矩阵 聚类 K-means降维 社团挖掘 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]