下载文档原格式
收稿日期：2010－12－01；修回日期：2011－03－02基金项目：哈尔滨市后备带头人基金项目（2004AFXXJ039）作者简介：黄韬（1982－），男，黑龙江人，硕士研究生，研究方向为企业智能计算；刘胜辉，教授，硕士研究生导师，研究方向为计算机集成制造系统，企业智能计算。
基于k －means 聚类算法的研究黄韬，刘胜辉，谭艳娜（哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨150080）摘要：分析研究聚类分析方法，对多种聚类分析算法进行分析比较，讨论各自的优点和不足，同时针对原k －means 算法的聚类结果受随机选取初始聚类中心的影响较大的缺点，提出一种改进算法。
通过将对数据集的多次采样，选取最终较优的初始聚类中心，使得改进后的算法受初始聚类中心选择的影响度大大降低；同时，在选取初始聚类中心后，对初值进行数据标准化处理，使聚类效果进一步提高。
通过UCI 数据集上的数据对新算法Hk －means 进行检测，结果显示Hk －means 算法比原始的k －means 算法在聚类效果上有显著的提高，并对相关领域有借鉴意义。
关键词：数据挖掘；聚类算法；k －means 算法中图分类号：TP301．6文献标识码：A文章编号：1673－629X （2011）07－0054－04Research of Clustering Algorithm Based on K －meansHUANG Tao ，LIU Sheng －hui ，TAN Yan －na（Sch．of Computer Sci．and Tech．，Harbin Univ．of Sci．and Tech．，Harbin 150080，China ）Abstract ：Analyze and research the method of cluster analysis ，analyze and compare many kinds of algorithms of cluster analysis ，discuss their respective strengths and weaknesses．At the same time ，according to the weaknesses of the cluster result of original k －means algorithm is significant influence by selecting the initial cluster centers randomly ，a modified algorithm is proposed．Through taking sample many times to data set ，choose final superior cluster center ，bring down the impact of initial cluster centers to improved algorithm greatly．Simultaneously ，the initial data is standadized once the initial cluster center is selected ，makes cluster effect improved furthermore．Detecting new algorithm Hk －means through the date of UCI data set ，the result shows that Hk －means algorithm is more prominent improved than initial k －means algorithm in cluster effect ，and it＇s useful for conference to relative field．Key words ：data mining ；clustering algorithm ；k －means algorithm0引言数据挖掘（Data Mining ）［1］是一种数据分析处理技术，一般采取排出专家因素而通过自动的方式来发现数据仓库、大型数据库或其他大量信息中新的、不可预见的或隐藏的有价值的知识。
收稿日期:2008208227;修回日期:2008210227 基金项目:国家“973”重点计划资助项目(2004CB318000);辽宁省教育厅科研资助项目作者简介:赵凤霞(19822),女,硕士研究生,主要研究方向为人工智能、复杂网络(zfx_1118@s ohu .com );谢福鼎(19632),男,教授,博士,主要研究方向为人工智能、复杂网络、数据挖掘、计算机代数.基于K 2m eans 聚类算法的复杂网络社团发现新方法3赵凤霞,谢福鼎(辽宁师范大学计算机与信息技术学院,辽宁大连116029)摘 要:提出了一种基于K 2means 聚类算法的复杂网络社团结构划分方法。
算法基于Fortunat o 等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k 个社团,然后通过模块度来确定网络理想的社团结构。
该算法有效地避免了K 2means 聚类算法对初始化选值敏感性的问题。
通过Zachary Karate Club 和College Football Net w ork 两个经典模型验证了该算法的可行性。
关键词:复杂网络;社团结构;K 2means 聚类算法;节点关联度中图分类号:TP393 文献标志码:A 文章编号:100123695(2009)0622041203doi:10.3969/j .issn .100123695.2009.06.012Detecting community in comp lex net w orks using K 2means cluster algorithmZHAO Feng 2xia,X I E Fu 2ding(College of Co m puter &Infor m ation Technology,L iaoning N or m al U niversity,D alian L iaoning 116029,China )Abstract:This paper p r oposed a ne w detecting method based on K 2means cluster algorith m.Thr ough the definiti on of node link based on inf or mati on centrality which Fortunat o p r oposed and the selecti on of the clustering center and the clustering of the node according node link,the app r oach identified the net w ork t o k communities,then identified the ideally community struc 2ture according modularity .The algorithm could find clustering center better and it is r obust t o initializati on,s o the quality of detecting was i m p r oved greatly .It tested the algorith m on the t w o net w ork data na med Zachary Karate Club and College Football Net w ork .Key words:comp lex net w ork;co mmunity structure;K 2means cluster algorith m;node link 引言随着对复杂网络性质的物理意义和数学特性的深入研究,人们发现许多实际网络都具有一个共同性质,即社团结构。
基于聚类分析的复杂网络中的社团探测
刘婷;胡宝清
【期刊名称】《复杂系统与复杂性科学》
【年(卷),期】2007(004)001
【摘要】社团结构是复杂网络中普遍存在的一种特征.本文应用改进了的谱分法将网络的社团探测问题转换为聚类分析问题,并将Girvan和Newman提出的模块度函数概念应用到聚类分析的4类算法中进行社团结构的探测,特别提出了一种新的结合模块度的聚类遗传算法.然后用3种类型的网络实验算例验证了本文算法的有效性,并对实验结果进行了比较分析,得出本文提出的新算法在初始化敏感性和准确性方面效果较好.最后指出本文算法的进一步研究方向.
【总页数】8页(P28-35)
【作者】刘婷;胡宝清
【作者单位】武汉大学数学与统计学院,武汉,430072;武汉大学数学与统计学院,武汉,430072
【正文语种】中文
【中图分类】N94;TP393
【相关文献】
1.基于物理场论的探测复杂网络社团结构的分布估计算法 [J], 刘晋霞;孙丽萍;杜静;刘晋钢;张丽
2.基于随机聚类采样算法的复杂网络社团探测 [J], 蔡君;余顺争
3.复杂网络中的邻域重叠社团结构探测 [J], 马磊
4.基于量子模糊聚类算法的复杂网络社团结构探测 [J], 牛艳庆
5.复杂网络中社团结构的快速探测方法 [J], 贾宗维;崔军;王晓芳
因版权原因，仅展示原文概要，查看原文内容请购买。
聚类分析的网络论坛社团探测算法探究1引言网络论坛(BBS)由于具有及时性、交互性、开放性等特点，因而也是网络舆论产生、形成和发展的主要场所，整个网络论坛的参与者呈现一种特性社团结构，即整个网络由若干个社团构成，每个社团内部的节点之间的连接相对紧密，各社团之间的连接相对稀疏.研究网络论坛的社团结构，对了解BBS中网络舆论的传播特点具有现实意义.网络论坛中成员根据兴趣或背景而形成真实的社会团体，网络中的这些社区有助于更加有效地理解其成员结构和分析网络舆论传播特性.目前对网络社团结构研究主要有两类主要的方法社会学中的分级聚类和计算机科学中的图形分割方法.分级聚类是探测网络社团的传统方法，基于各个节点间连接的相似性或强度将网络划分成子群，并根据划分时是往网络中添加还是移除边可分为凝聚算法和分裂算法，Girvan和Newman提出基于边介数的分裂算法(简称GN算法);KemighanLin算法和谱平分法则是较为出名的图形分割算法，其中KernighanLin算法根据使社团内部及社团间的边最优化的原则对原始的网络进行分类，谱平分法是根据网络图的Laplace矩阵进行向特征向量空间的谱映射.该文算法是谱平分法的一种改进算法，将模块度函数与聚类分析算法结合进行社团结构探测.2试验及结果海峡四川钓友联谊会是海峡钓鱼网的一个子板块，其中参与者大部分为四川本地钓鱼爱好者，论坛成员具有共同的兴趣爱好.该板块为四川钓鱼爱好者的学习与交流提供了一条新途径.针对相关主题，论坛成员可以提出问题、发表各自的观点和看法，相互交流，相互帮助. 实际数据处理时，根据对己掌握的id对应关系，对部分id进行了特别处理，例如将清凉油和151这2个id合并处理，将被草压死的骆驼与骆驼，黑武器与黑版视为同一个id.2. 1连接权矩阵的生成该文从6000余名在该论坛中发言的成员中筛选出满足各种阈值条件的成员1436人，并生成对应的连接权矩阵.2. 2对比试验为验证算法的有效性，该文将该论坛数据分别运用K-Means算法,CNN算法以及该文的基于模拟退火的社团探测算法.其中，K -Means算法是常见的聚类算法，是基于距离聚类中心最近法则为标准对个体进行分类的;而CNN算法则采用竞争型神经网络模型，进行无监督学习的分类.这里要注意的是，这里所有的算法程序都用matlab编写.这里运行次数为得到最优解的平均运行次数，时间为平均运行时间. 表2给出了应用C - based SA算法模块度在0.36以上的聚类结果，k=3,4,5时模块度较高.图1给出了k =5,降温速率为0.997时的探测算法的迭代过程，迭代到2300次左右就己经求出了最优解.2. 3结果分析通过对实际数据运行3种不同的社团探测算法，结果表明:K-Means 算法速度较快，但受初始化条件影响较大，可靠性也比其他两种算法差，网络规模扩大对算法性能影响较大;CNN算法对初始化条件依赖程度较K-Means算法较低，但运算速度较慢，并且对数据预处理需要花较长的时间;三种算法中，C-based SA算法不依赖初始化条件的选取，直接使用模块度函数作为目标函数对网络进行社团探测，能保证达到全局最优解，可靠性较其他两种算法要高，该算法的复杂度依赖于系统降温速率的设置，其缺点是运行时间较长.3结束语提出了针对网络论坛的社交网络的构建方法，将组合优化的方法与聚类分析的思想相互结合并应用到网络论坛社团结构的求取上，并提出了用模拟退火算法来求解，解决了实际工作实践中遇到的问题.试验结果验证了算法的准确性，模拟退火算法与聚类分析的思想能有效的结合起来，对论坛社团结构进行分析有较大的实用价值.试验结果同时说明，基于兴趣的网络论坛中的社交网络社团结构不太明显，值得注意的是，该文使用的是非重叠性的社团探测算法，考虑到实际网络中，个体往往具有多群体特性，因此，改进社团结构的定义以及在此基础上探索新的社团划分方法是一个值得研究的方向.。
K-means聚类算法的研究共3篇K-means聚类算法的研究1K-means聚类算法的研究聚类是数据挖掘和统计分析领域中非常重要的方法，它能够从大量的数据中抽象出有意义的类别。
K-means聚类算法是一个经典的聚类算法，它的思想简单而有效，广泛应用于数据分析、图像处理、生物信息学等领域。
本文将从算法原理、优缺点、应用及改进等方面进行研究和探讨。
一、算法原理K-means算法是一种基于距离的聚类算法，其基本原理是将数据点划分到k个不同的簇中，使得簇内的数据点尽可能相似，而簇间的数据点尽可能不同。
具体步骤如下：1. 随机选择k个中心点（centroid）作为初始的聚类中心。
2. 对于每个数据点，计算其到各个聚类中心的距离，并将其归类到距离最近的簇中。
3. 对于每个簇，重新计算其聚类中心，即为该簇内所有数据点的平均值。
4. 重复执行步骤2和3，直到聚类中心不再改变，或达到预设的迭代次数。
二、优缺点K-means算法具有以下优缺点：优点：1. 算法简单、易于实现和理解，计算速度快，适用于大规模数据。
2. 对于点密集的数据集，聚类效果较好。
3. 可以很好地处理凸型和球型簇。
缺点：1. K值需要事先确定，不确定时需要多次试验，计算量大。
2. 算法容易陷入局部最优解，结果不稳定，可能需要多次运行来得到最优解。
3. 对于噪声和离群点的敏感度较高。
三、应用K-means算法适用于以下数据挖掘任务：1. 分类问题：根据数据的属性特征将其划分到不同的组别，如客户分群、市场分析等。
2. 图像分割：将图像中的像素点划分到不同的区域，实现图像分割。
3. 地质勘探：对地面的物质进行分离和分类，例如岩性分类、照片过滤等。
4. 生物信息学：对基因序列进行聚类分析，以发现有共性的基因序列。
四、改进K-means算法有许多改进算法，尝试解决其缺点和不足，如以下算法：1. K-means++算法：改进了初始聚类中心的选择方法，使得聚类结果更加稳定和准确。
龙源期刊网
复杂网络中的邻域重叠社团结构探测
作者：马磊
来源：《物联网技术》2012年第07期
摘要：网络，数学家们称其为图，它为许多复杂系统的结构提供了一个很好的抽象，从
社会网络、计算机网络，到生物网络以及物理系统的状态空间。
在过去的几十年里出现了许多确定网络系统拓扑结构的改进实验，但对实验产生的数据进行科学的分析,仍然存在本质的挑战。
目前的社团检测中主要存在两个问题：一是不知道网络中有几个社团；二是网络中的顶点可能属于不同的社团，也就是社团中存在重叠结构。
为了了解各种重叠社团检测算法的思想、实现步骤、优缺点比较、算法应用,文中对邻域重叠社团检测算法进行了深入的分析，以k-means算法分析了经济网络，同时采用Silhouette 指标解决了最佳聚类数的问题，并通过仿真实验证明了此算法的可能性。
关键词：网络；社团结构；重叠社团；社团检测。
复杂网络社团的投影聚类划分李伟;杨晓峰;张重阳;汤可宗;杨静宇【期刊名称】《智能系统学报》【年(卷),期】2011(6)1【摘要】Community detection is important for understanding complex networks. Because of its high complexity ,community detection in complex networks has recently attracted significant interest from research groups. In this work, a data analysis perspective was proposed for commumty detection on complex networks. First. based on the network topology, the nodes of the studied network were projected as data points in a high-dimensional space, and the network was associated with a data cloud. Secund , principal component analysis ( PCA) was used to reduce the high-dimensional data cloud into a low-dimensional one. which kept the main structural information. Third, Kmeans algorithms were used to find clusters of the data points in the reduccd data cloud. which inferred the communities of the studied network. Experiments on datasets DCG (2-mode) and Zachary ( 1-mode) indicated that the proposed method can reveal network communities effectively. The proposed method provided a novel perspective of the community detection of complex networks.%社团结构划分对研究复杂网络有重要作用,由于该问题的复杂性,复杂网络中的社团划分问题成为近期的一个研究热点.从经典数据分析的角度研究了复杂网络的社团结构,首先依据网络的拓扑信息,将网络节点投影成高维空间的点,使得一个网络对应到高维空间中的一个点分布;接着使用主分量分析方法PCA对高维点分布降维,保留点群分布的主要结构信息;再通过K-means聚类结果来推断网络的社团结构.基于2-mode数据和1-mode网络数据实验表明,该方法可以快速、可靠地找出网络的社团.将经典数据分析的聚类方法应用到网络分析中,验证了该思路的有效性,为网络社团分析提供一个新视角.【总页数】6页(P57-62)【作者】李伟;杨晓峰;张重阳;汤可宗;杨静宇【作者单位】南京理工大学计算机系,江苏,南京,210094;南京理工大学计算机系,江苏,南京,210094;南京理工大学计算机系,江苏,南京,210094;南京理工大学计算机系,江苏,南京,210094;南京理工大学计算机系,江苏,南京,210094【正文语种】中文【中图分类】TP311;TP393;N94【相关文献】1.基于复杂网络的绿色CDN社团结构划分 [J], 李昕冉;周金和2.基于复杂网络社团划分的文本聚类方法 [J], 谢凤宏;张大为;黄丹;谢福鼎3.基于复杂网络社团划分的Web services聚类 [J], 欧有远;张海粟;孟晖;李德毅4.基于中心节点和局部优化的复杂网络社团划分方法 [J], 王建玺;黄淼5.基于节点向量表达的复杂网络社团划分算法 [J], 韩忠明;刘雯;李梦琪;郑晨烨;谭旭升;段大高因版权原因，仅展示原文概要，查看原文内容请购买。
基于图神经网络的社团检测算法基于图神经网络的社团检测算法一、引言社团检测是图数据分析中的重要问题之一，旨在从复杂网络中发现具有紧密联系的节点群体。
社团结构的发现对于了解网络的组织结构、社交网络分析、信息传播等具有重要意义。
近年来，随着深度学习的发展，图神经网络（Graph Neural Network，简称GNN）被提出并成功应用于社团检测中，极大地推动了社团检测的研究进展。
二、图神经网络简介图神经网络是一种用于处理图数据的深度学习模型。
相对于传统的深度学习模型，如卷积神经网络（Convolutional Neural Network，简称CNN）和循环神经网络（Recurrent Neural Network，简称RNN），图神经网络能够处理非欧几里得空间的数据，具有较强的适应性和泛化能力。
图神经网络的核心思想是将节点和边作为输入，并通过多层的神经网络模型进行信息传播和聚合。
在信息传播过程中，每个节点将其周围节点的信息进行聚合，得到一个更全面的表示。
这种信息传播和聚合的过程能够充分利用节点之间的关系，从而更好地挖掘图数据中的特征。
三、基于图神经网络的社团检测算法基于图神经网络的社团检测算法主要包括以下步骤：1. 构建图数据：首先，将复杂网络表示为图数据结构，其中节点表示网络中的实体，边表示实体之间的关系。
可以使用邻接矩阵或者邻接表等数据结构来存储和表示图数据。
2. 节点特征编码：为了让图神经网络能够处理节点的特征，需要将节点特征进行编码。
可以使用词嵌入（Word Embedding）等技术将节点特征转化为低维的向量表示，从而减少计算复杂度。
3. 图神经网络模型构建：选择适合的图神经网络模型用于社团检测。
常用的图神经网络模型包括图卷积网络（Graph Convolutional Network，简称GCN）、图注意力网络（Graph Attention Network，简称GAT）等。
4. 信息传播和聚合：通过多层的神经网络模型，将节点和边的信息进行传播和聚合，得到更全面的节点表示。
基于K-means聚类算法的复杂网络社团发现新方法
赵凤霞;谢福鼎
【期刊名称】《计算机应用研究》
【年(卷),期】2009(026)006
【摘要】提出了一种基于K-means 聚类算法的复杂网络社团结构划分方法.算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构.该算法有效地避免了K-means 聚类算法对初始化选值敏感性的问题.通过Zachary Karate Club和College Football Network 两个经典模型验证了该算法的可行性.
【总页数】4页(P2041-2043,2049)
【作者】赵凤霞;谢福鼎
【作者单位】辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029;辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029
【正文语种】中文
【中图分类】TP393
【相关文献】
1.基于K-means聚类算法的城市轨道交通车站配电变压器容量计算新方法 [J], 魏海洋
2.一种基于复杂网络属性值的K-means聚类算法 [J], 董俊;任家东;卢海涛
3.基于置信传播的复杂网络社团发现算法 [J], 尤心心;葛檬
4.一种基于加权复杂网络特征的K-means聚类算法 [J], 赵鹏;耿焕同;蔡庆生;王清毅
5.基于社团密合度的复杂网络社团发现算法 [J], CHEN Dong-ming;WANG Yun-kai;HUANG Xin-yu;WANG Dong-qi
因版权原因，仅展示原文概要，查看原文内容请购买。
2023年研究生数学建模竞赛e题k-means聚类一、概述研究生数学建模竞赛一直是我国研究生数学教育中的重要组成部分，对于培养学生的数学建模能力和创新思维起到了至关重要的作用。
2023年研究生数学建模竞赛的e题涉及到k-means聚类问题，k-means聚类作为一种经典的数据聚类方法，具有广泛的应用价值和理论研究意义。
本文将对2023年研究生数学建模竞赛e题k-means聚类进行深入分析和讨论。
二、k-means聚类的原理和算法1. k-means聚类的原理k-means聚类是一种基于样本的无监督学习方法，其原理是将n个样本分成k个簇，使得每个样本点都属于离它最近的均值所对应的簇。
具体而言，k-means聚类的目标是最小化簇内点与簇中心的距离的平方和，即最小化目标函数：\[J = \sum_{i=1}^{k}\sum_{x∈C_i}||x-μ_i||^2\]其中，μ_i是第i个簇的均值向量，C_i是第i个簇的样本集合。
2. k-means聚类的算法k-means聚类的算法主要包括以下几个步骤：1）初始化簇中心：随机选择k个样本点作为初始的簇中心。
2）分配样本点：对每个样本点，计算其与各个簇中心的距离，并将其分配到离它最近的簇中心所对应的簇。
3）更新簇中心：对每个簇，重新计算其均值向量作为新的簇中心。
4）重复步骤2和步骤3，直至簇中心不再发生变化或达到最大迭代次数。
三、k-means聚类的应用领域k-means聚类作为一种简单而有效的聚类方法，在各个领域中都有着广泛的应用，主要包括但不限于以下几个方面：1. 图像分割：将图像中相似的像素点聚类到同一簇，从而实现图像的分割和分析。
2. 文本聚类：将文本数据按照其语义和主题进行聚类分析，用于信息检索和文本分类。
3. 生物信息学：基因序列、蛋白质结构等生物学数据的聚类分析。
4. 社交网络分析：对社交网络中的用户行为、关系等进行聚类研究，挖掘其中的规律和特征。
复杂网络中聚类方法及社团结构的研究的开题报告题目：复杂网络中聚类方法及社团结构的研究一、研究背景随着人们对复杂现象的研究不断深入，网络科学逐渐成为一个重要的研究领域。
在复杂网络中，节点和之间的关系是非常复杂的，网络的结构具有高度的异质性和非线性性。
因此，利用聚类方法对网络进行分析和研究越来越受到人们的关注。
社团结构是网络中一种特殊的结构，它具有高度的内部稠密度和低度的跨组连通性，社团内节点之间的联系比群组外的节点之间的联系更紧密。
在实际应用中，掌握网络的聚类方法和社团结构对于了解网络的演化规律和网络的特性有着非常重要的意义。
二、研究内容和方法1. 聚类算法的研究本文将主要研究复杂网络中的聚类算法，包括基于相似度的聚类算法、基于图论的聚类算法、基于统计学习的聚类算法等。
相似度是指节点之间在某种意义下的相似程度，在网络中各节点的属性值都不同，计算相似度时需要根据具体的应用来选择不同属性进行计算。
图论方法将网络看做是一个图，节点和边分别对应图中的点和线，利用图的连通性和距离等性质进行聚类。
统计学习方法是一种基于机器学习的方法，它通过学习和建立概率模型来进行聚类分析。
2. 社团结构的研究本文还将研究复杂网络中的社团结构，包括社团结构的发现方法、社团结构的性质和演化规律等方面。
其中社团结构的发现方法主要包括基于模块度的社团发现方法、基于谱聚类的社团发现方法等。
社团结构的性质包括社团内部的紧密度和连通性等，它们与网络的结构和功能密切相关。
社团结构的演化规律包括静态和动态两个方面，静态的规律表现在网络不变的情况下，不同的网络具有不同的社团结构，动态的规律表现在网络演化过程中，社团结构的变化体现了网络的演化规律和特性。
三、研究意义本文将探讨复杂网络中的聚类方法和社团结构，这对于深入了解网络结构和特性有着重要的意义。
研究成果有望在社交网络分析、信息传播、金融风险控制等领域得到广泛应用。
四、参考文献1. Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113.2. Porter, M. A., Onnela, J. P., & Mucha, P. J. (2009). Communities in networks. Notices of the AMS, 56(9), 1082-1097.3. Zhang, P., Li, X., Yang, F., & Li, J. (2014). Clustering complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 404, 1-24.4. Fortunato, S. (2010). Community detection in graphs. Physics reports, 486(3-5), 75-174.5. Han, J., Pei, J., & Kamber, M. (2011). Data mining: conceptsand techniques. Morgan Kaufmann.。
基于聚类算法的复杂网络结构分析研究随着互联网的快速发展，人们创建和使用网络的方式越来越多样化。
而网络作为一种复杂系统，其结构也变得越来越复杂。
为了更好地理解和研究网络结构，聚类算法成为一个十分有用的工具。
本文旨在研究基于聚类算法的复杂网络结构分析，包括聚类算法的基本概念、应用场景和研究方法等。
一、聚类算法的基本概念聚类算法是一种常见的数据分析方法，用于将相似的数据点归类。
简单来说，聚类算法通过测量数据点之间距离或相似性，将它们分成不同的组。
这种算法广泛应用于各种领域，包括机器学习、数据挖掘、图像分析等等。
在分析复杂网络时，聚类算法也是一种十分有用的工具。
现在我们来了解一下聚类算法的一些基本概念。
1.1 距离度量距离度量是指两个数据点之间的距离。
在聚类算法中，距离度量往往是一个关键的考虑因素，因为距离度量的不同可能会导致分组结果的不同。
常见的距离度量包括欧式距离、曼哈顿距离、切比雪夫距离等等。
1.2 聚类方法聚类方法是指将数据点分组的具体算法。
一般来说，聚类方法可以分为基于原型的聚类和层次聚类两类。
基于原型的聚类是指将数据点分为不同的团簇，每个团簇都有一个代表元，可以是重心或中心等等；层次聚类是指将数据点组织为层次结构，每个层次都对应一个分组结果。
1.3 聚类评估聚类评估是指评估聚类结果的方法。
一般来说，聚类评估可以分为内部评估和外部评估两类。
内部评估指评估聚类结果的好坏，通常采用轮廓系数、DB指数等指标；外部评估指比较聚类结果和真实聚类结果的差异，可以采用精准度、召回率、F值等指标。
二、应用场景复杂网络结构分析是聚类算法的一个重要应用方向。
因为复杂网络结构通常具有大规模、高纬度和动态变化等特征，因此需要一些高效的算法对其进行处理。
聚类算法可以帮助我们对复杂网络结构进行分组和分类，从而更好地理解和分析网络结构。
下面我们来了解一些聚类算法在复杂网络分析中的应用场景。
2.1 社交网络社交网络是人们在网络中互相交流和分享的平台。
社团检测算法
社团检测算法是网络分析中的一种方法，用于发现网络中的社团结构。
社团结构是指
网络中由密切关联的节点组成的分组。
社团检测算法可以帮助我们理解网络中的关系，发
现网络的模式，识别关键节点和集群等。
模块度最大化算法是一种基于网络密度和社团内部连接强度的方法。
它通过比较网络
中实际连接和随机连接的差异，来确定社团结构。
该算法优化目标是最大化网络中社团的
密度和社团之间的差异性。
模块度最大化算法在处理大规模网络时效果较好，但容易受到
网络噪音的影响。
谱聚类算法是一种基于网络谱矩阵的方法。
该算法将网络转换为谱矩阵，并通过特征
值分解和聚类来确定社团结构。
谱聚类算法适用于处理稀疏网络和高维数据，但需要计算
网络谱矩阵，计算复杂度较高。
层次聚类算法是一种基于网络节点相似度的方法。
该算法通过计算节点之间的相似度，将节点逐层聚类成社团。
层次聚类算法适用于处理带权网络和不规则网络，但对噪音和异
常值比较敏感。
K-means算法是一种基于距离的方法。
该算法将网络节点按照距离划分为若干个簇，
并对簇内节点进行聚类。
K-means算法适用于处理纯数字数据和高维数据，但对离群点比
较敏感。
总之，社团检测算法是一种重要的网络分析方法，可以帮助我们理解网络中的关系和
结构，为社会科学、生物学、计算机科学等领域提供有用的研究工具。
在应用社团检测算
法时，需要根据网络的特点和需求选择合适的算法，并结合实际领域的专业知识进行解释
和分析。
复杂网络中的社团发现算法综述随着社会网络的日益发达，社交网络成为了现代社会的重要组成部分。
然而，这些网络往往都是由大量的节点和边构成，而且具有非常复杂的拓扑结构。
对于这样的复杂网络，如何有效地发现其中的社团结构一直是研究的热点之一。
社团结构是指在网络中存在一些密度较高、连通性较强的子图，其中节点之间的联系比较紧密，而与其他社团的节点则联系较松散。
社团结构的发现可以帮助我们了解网络中的相互作用关系，为社交网络的数据挖掘和信息推荐提供基础理论和方法。
社团发现算法按照算法思想的不同，可以分为基于模型的方法、基于聚类的方法和基于图分割的方法。
其中，基于模型的方法是使用概率模型描述网络，然后利用统计学方法推导出社团结构；基于聚类的方法是将网络中的节点聚类成若干个社团，每个社团内节点之间的相似性要求较高；基于图分割的方法则是将网络切分为若干个部分，使得每个部分内的节点之间的连通性要求较强。
下面将分别介绍一些经典的社团发现算法：1. 基于模型的方法(1) 随机游走社团发现算法（Random Walk Community Detection Algorithm，RWCD）RWCD是基于随机游走模型的社团发现算法，它将节点的相似性定义为它们之间的转移概率，然后使用PageRank算法迭代计算各节点的权值，在一定阈值下将权值较高的节点聚合成社团。
RWCD算法可以充分利用网络中的拓扑结构，对大型网络具有较好的扩展性。
(2) 右奇社团发现算法（Modularity Optimization Algorithm，MOA）MOA算法是一种基于模块度优化的社团发现算法，它将社团内节点的连接强度与所有节点的连接强度相比较，然后计算模块度值，寻找最大模块度值时的节点聚类。
MOA算法的思想简单易懂，但需要耗费大量的计算资源。
2. 基于聚类的方法(1) K-means社团发现算法K-means算法是一种常用的聚类算法，它将网络中的节点分成K个组，每个组是一个社团。
聚类技术——复杂网络社团检测一．实验背景复杂网络是描述复杂系统的有力工具，它不仅是一种数据的表现形式，同样是也一种科学研究手段。
钱学森对于复杂网络给出了一种严格的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络成为复杂网络。
复杂网络社团结构定义为内紧外松的拓扑结构，即一组节点的集合，集合内的节点交互紧密，与外界节点交互松散。
复杂网络社团结构检测广泛的应用于信息推荐系统、致癌基因识别、数据挖掘等领域。
近年来，社区检测得到了快速的发展，这主要是由于Newman提出了模块度(modularity)的概念，从而使得网络社区划分优劣可以有一个明确的评价指标来衡量。
模块度越大，对应的社区划分越合理。
社团检测就是在复杂网络上做聚类，聚类出来的就是社团。
二．实验内容某跆拳道俱乐部数据由34个节点组成，由于管理上的分歧，俱乐部要分解成两个社团。
该实验的任务即：要求我们在给定的复杂网络上检测出两个社团。
三．分析与设计实验思路分析如下：1. 聚类算法通常可以描述为用相似度来衡量两个数据的远近，搜索可能的划分方案，使得目标函数达到极值。
目标函数通常与相似度关系密切，例如目标函数是同类中数据相似度的平均值。
2. 类似的，对于社团检测（复杂网络上做聚类），我们有三个关键问题：·希望得到什么样的社团？·如何衡量数据的相似度？·如何搜索得到最优解？下面我们围绕解决这三个问题进行本实验算法的说明：问题一：在本实验中，由于复杂网络的数据结构特点，我考虑从社团结构而不是两点之间的距离去定义社团。
我希望检测到“内部链接密集，外部链接稀疏”的两个社团。
问题二：明确了希望得到什么样的社团，下面解决如何衡量数据的相似度以及目标函数的构造。
1)给定节点i, 其邻居节点定义为与该节点相链接的所有节点组成的集合N(i)={j|A ij=1,j=1,2,…,n}，给定一对节点（i,j）,其相似度定义为这个两个节点的公共邻居节点个数与邻居节点的并的个数的比值，即：S ij=|N(i)∩N(j)||N(i)∪N(j)|，其中|N(i)∩N(j)|表示集合N(i)∩N(j)中元素的个数。
第24卷第3期V ol.24N o.3控 制 与 决 策Cont rolandDecision2009年3月 Mar.2009收稿日期:2008201212;修回日期:2008204213.基金项目:国家自然科学基金项目(50674070,60374041);国家863计划项目(2007A A 06Z 231).作者简介:高忠科(1982—),男,山东东营人,博士生,从事复杂系统建模、非线性信息处理的研究;金宁德(1963—),男,黑龙江东宁人,教授,博士生导师,从事先进传感器、信息处理技术等研究. 文章编号:100120920(2009)0320377206基于K 2means 聚类和数据场理论的复杂网络社团结构探寻高忠科,金宁德(天津大学电气与自动化工程学院,天津300072)摘 要:探寻社团结构是研究复杂网络结构与功能之间关系的基础.提出和分析了基于K 2means 聚类的社团探寻算法和基于数据场理论的社团探寻算法,并通过实验仿真验证了这两种算法的有效性.在仿真中发现并验证了社团内部比整个网络具有更加鲜明的小世界效应,这说明在网络控制中,在相同的耦合强度下,对社团的同步控制比对整个网络的同步控制更容易实现.关键词:复杂网络;社团结构;K 2means 聚类;数据场;小世界效应中图分类号:N941.4 文献标识码:ADetecting community structure in complex net w orks based onK 2means clustering and d ata f ield theoryGA O Zhon g 2ke ,J I N N i ng 2de(School of Electrical Engineering and Automation ,Tianjin University ,Tianjin 300072,China.Correspondent :J IN Ning 2de ,E 2mail :ndjin @ )Abstract :Detecting community structure is fundamental for analyzing the relationship between structure and f unction in complex networks.We propose two algorithms for network community detection :Community detection based on K 2means clustering and community detection based on data fields.Experiments show that the algorithms presented inthis paper are of high accuracy with good performance and the “small 2world ”effect in the community is more obvious than that in the whole network ,which implies that it is much easier to reach synchronization in the community than that in the whole network under the same coupling strength.K ey w ords :Complex networks ;Community structure ;K 2means clustering ;Data field ;Small 2world effect1 引 言 复杂网络是对复杂系统的抽象和描述方式.任何包含大量组成单元(或子系统)的复杂系统,当把构成单元抽象为节点、单元间的相互关系抽象为边时,都可作为复杂网络来研究.在Watt s 等关于小世界网络[1,2],以及Barab ási 等关于无标度网络[3,4]的开创性工作之后,人们对存在于不同领域的大量实际网络进行了广泛的实证性研究.研究发现:大量的大型复杂网络不仅具有小世界效应和无标度特征[5,6],而且都呈现一种特性———社团结构[7,8].即整个网络由若干个社团构成,每个社团内部节点间的连接非常紧密,但各个社团之间的连接却相对较为稀疏.本文针对探寻复杂网络社团结构的问题,首先探讨了如何判断网络中的社团数目,以及基于节点度值、介数和聚集系数寻找每个社团中的关键节点.然后提出和分析了两种算法:一是基于K 2means 聚类的社团探寻算法,即对通过Capocci 算法[9]转换得到的数据,运用K 2means 算法进行聚类分析,从而揭示网络社团结构;二是在淦文燕等[10]提出的基于数据场层次聚类法的基础上,提出了基于数据场理论的社团探寻算法.最后通过实验仿真验证了两种算法的有效性.2 网络社团个数的判断及关键节点的搜索2.1 网络社团个数的判断谱图理论利用矩阵理论和线性代数理论来研究图的邻接矩阵,根据矩阵的谱来确定图的某些性质.谱图理论分析的基础是图的Laplace 矩阵[11].本文 控 制 与 决 策第24卷基于网络谱分析[11,12]的基本思想,对复杂网络中社团个数进行判断,具体方法如下:一个有n个节点的无向图G的Laplace矩阵是一个n×n维的对称矩阵L,其中L对角线上的元素L ii是节点i的度,其他非对角线上的元素L ij则表示节点i与节点j的连接关系.如果这两个节点之间有边连接,则L ij值为-1,否则L ij值为0.也可将矩阵L表示成L=K- A.其中:K是一个对角矩阵,其对角线上的元素对应于各个节点的度;A为网络的连接矩阵.L矩阵所有行与列的和都为0,因此该矩阵总有一个特征值为0,且其对应的特征向量l=(1, 1,…,1).从理论上可证明,对于社团结构明显的网络,不为零的特征值所对应的特征向量各元素中,同一社团节点对应的元素是近似相等的.然而,对于节点数目众多、社团结构不明显的网络,仅通过一个第一非平凡特征向量来判断网络社团个数是很难的,而通过比较多个第一非平凡特征向量(即增加特征向量平面的维数)中各节点相应元素的分布,则可较准确地判断社团结构不明显网络中社团的个数.2.2 社团关键节点的搜索寻找社团关键节点对于分析复杂网络的性质十分重要.评价节点重要程度的依据和搜索关键节点的方法有多种,如节点度排序法、介数排序法等.节点的度值反映了拓扑模型的静态结构特征;节点的介数反映了节点的流量状况,且与节点的活动相关;节点的聚集系数则反映了节点周围其他节点间的聚集情况.因此,采用基于节点度值、介数和聚集系数的综合判据,对节点重要性进行评估,进而找出社团中的关键节点.算法的基本思路是:1)计算网络中每个节点的度值,计算网络平均度值.2)遍历网络的两两节点对,求解节点对最短路径,计算节点的介数和聚集系数.3)选取参量y i=αk i+βb i+γC i,i=1,2,…,N.(1)其中:α,β和γ为参数;k i为节点i的度值;b i为节点i 的介数;C i为节点i的聚集系数;N为节点总数.4)根据实际情况,适当选取参数α,β和γ,计算网络中所有节点的y i值,从大到小依次取k个y i值, k为网络中社团个数,i对应于节点的编号,因此得到了网络中k个社团的关键节点.3 基于K2means聚类和数据场理论的社团探寻算法3.1 基于K2means聚类的社团探寻算法聚类分析是机器学习的经典问题,它是通过抽取数据的潜在结构,将相似数据组成类或类的层次结构.聚类分析不需要先验知识和假设,故称为无监督学习.谱聚类[13,14]是由数据点间相似关系建立矩阵,获取该矩阵的前n个特征向量,并用它们来聚类不同的数据点.其算法的一般原则是:类内样本间的相似度大,类间样本间的相似度小.复杂网络中的社团结构探寻与数据的聚类分析有相似之处.聚类分析属于无监督的模式识别,其方法比社团结构探寻多样有效,因此将聚类分析应用于复杂网络,可以探寻其社团结构.应用聚类分析探寻网络社团结构分为两个主要步骤:1)将原问题转化为聚类问题,即将网络中节点间的联系在特征向量空间表述出来.谱平分法[11,12]恰好可实现这一转化,本文应用传统谱平分法的一种改进算法———Capocci算法[9].2)对转化后的数据进行聚类,并将聚类结果还原为相应的社团结构.本文采用一种常用的聚类算法———K2means聚类算法.对于节点数目众多、社团结构不明显的网络,传统谱平分法[11,12]虽能通过比较多个第一非平凡特征向量中各节点相应元素的分布,从而判断网络社团个数,但却难以通过第一非平凡特征向量元素分布,探寻含有多个社团网络中的社团结构.为此, Capocci等提出了基于标准矩阵N=K-1A的谱平分算法[9](称为Capocci算法).利用行标准化对矩阵N进行转换,可得矩阵N的最大特征值总等于1,相应的特征向量称为平凡特征向量.对于一个社团数目为k的网络,矩阵N有k-1个非常接近于1的第一非平凡特征向量,而其他特征值都与1有明显的差距,且在这k-1个特征向量中,同一社团的元素非常接近[9].在求取标准矩阵特征量时,为使对应于同一社团的元素尽可能接近, Capocci等引入最优化目标函数z(x)=12∑ni,j=1(x i-x j)2w ij.(2)其中:n为网络节点数;w ij为节点i和j连边的权值; x i是为各个节点定义的变量,且向量x满足约束条件∑ni,j=1x i x j m ij=1,(3)式中m ij是已知对称矩阵M的元素.最优化目标函数(2)可保证:如果定义x i为特征向量的元素,在式(3)的限制下求式(2)的最小值,便对应于第一非平凡特征量的问题,而该最小值即对应于平凡特征量,它是一个常量.其他驻点对应的特征量中,同一社团内节点相应的元素具有相近的值.函数z对所有满873第3期高忠科等:基于K 2means 聚类和数据场理论的复杂网络社团结构探寻 足约束条件的x 的驻点为(D -W )X =μM x.(4)其中D =(d ij ),d ij =δij∑nk =1wik,(5)W 是网络的连接权矩阵,μ是拉格朗日系数.显然,不同的矩阵M 对应于不同的特征向量问题.例如:当M =D 时,D -1W x =(1-2μ)x ,对应于标准矩阵N =K -1A ;当M =I 时,(D -W )x =μx ,对应于Laplace 矩阵L =K - A.基于谱聚类的基本思想,在探寻含有k 个社团的网络社团结构时,可通过Capocci 算法求出其标准矩阵的k -1个非平凡特征向量,并以此作为聚类数据进行聚类分析,将分析后的结果再转化为对应的节点,便可得到相应的社团.K 2means 算法是一种常用的聚类算法,它是基于距离聚类中心最近法则对个体进行分类.本文基于K 2means 聚类的社团探寻算法,就是通过Capocci 算法转换得到的数据,运用K 2means 算法进行聚类分析,从而揭示网络社团结构.本文研究的网络为无权网络,因此连接权矩阵即为连接矩阵,即W = A.3.2 基于数据场理论的社团探寻算法自然界中除了重力、电磁力等长程作用以外,还存在核力等衰减速度较快的短程作用.根据物理学中的场论思想,淦文燕等[10]将物质粒子间的相互作用及其场描述方法引入抽象的数域空间,提出一种基于数据场的层次聚类方法.该方法将空间中的每个对象视为具有一定质量的粒子,其周围存在一个球形对称的虚拟数据场.类似于物理场的矢量强度函数和标量势函数描述,该方法引入数据场的势函数和场强函数定义,其中势函数定义为φ(x )=∑ni =1φi (x )=∑ni =1(m i ×e-(‖x -x i ‖/σ)2).(6)式中:‖x -x i ‖为对象x i 到场点x 的距离;m i ≥0(i =1,2,…,n )为对象的质量,满足归一化条件,即∑ni =1mi=1;σ∈(0,+∞)用于控制对象间相互作用力程,称为影响因子.在复杂网络的拓扑结构中,不同的节点具有不同的重要性,那些具有重要地位和作用的节点,在网络中会有较大的影响范围,对周围邻居节点具有较大的辐射强度,其他节点会在一定程度上受其影响.根据这种影响程度的大小,网络可划分为不同的社团.受数据场层次聚类方法的启发,本文提出了基于数据场理论的社团探寻算法.将网络中的节点视为空间中具有质量的粒子,其周围存在一个虚拟作用场,位于场内的任何其他对象都将受到场力作用,所有对象的联合作用便在空间上确定了一个数据场.该算法依据对象(节点)个体之间的势值(联系强弱程度),把它们划分到不同的社团,从而揭示网络社团结构.采用网络拓扑上的距离(即节点间的最短路径)来衡量这种联系强度.本文结合复杂网络的特性,采用类似于淦文燕等[10]使用的势函数(6).其中:节点质量m i 和σ取常数,节点间的距离‖x j -x i ‖取两个节点x j 和x i 在网络中的最短路径.势函数(6)作为描述数据场中各对象之间相互作用关系的直观方法,能方便地计算网络节点的影响范围.算法流程如下:1)对网络社团数目k 进行判断,搜索相应社团中的关键节点,找到网络中的k 个关键节点,并将这k 个关键节点作为一个集合记为S ;2)将集合S 中节点个数的倒数作为质量,计算当前节点到S 中每个节点的势值,并将此节点归属于拥有最大势值的S 中的节点;3)当出现某个节点i 同时属于S 中2个或2个以上节点时,计算与节点i 有边相连的所有节点q j (j =1,2,…,k i ,k i 为与节点i 有边相连的节点个数,即节点i 的度值)到集合S 中每个节点的势值,计算与节点i 相连的k i 个节点到S 中每个节点的势值和,并将节点i 归属于拥有最大势值和的S 中的节点;4)遍历网络中所有节点,最终将网络划分为k个社团.4 实验仿真与分析 本文选用3个实验例子,包括通过Matlab 编程及网络可视化软件Ucinet 和Net draw [15]生成的两个网络:一个具有较明显的社团结构;另一个则具有不明显的社团结构.一个实际网络为Zachary 研究的空手道俱乐部内部成员的关系网络.对这3个网络分别应用本文提出的两种算法进行社团探寻,最终获得了较好的社团分类.为了便于判断社团分类效果的好坏,采用衡量社团分类效果的一个定量指标———模块度[16,17],它是衡量网络划分质量的一个标准.对于具有n 个社团的网络,引入一个n ×n 的对称矩阵E ,其元素e ij 是网络中连接社团i 的点和社团j 的点的所有边.矩阵的迹tr E =∑ie ij是网络中连接同一社团的点的所有边,而行和(或列和)a i =∑je ij是连接社团i 的点的所有边.若网络中两点之间有一条边的概率相等,则不管最后是否属于同一社团,均有e ij =a i a j .973 控 制 与 决 策第24卷因此模块度定义为Q =∑i(e ij -a 2i )=t r E -‖E 2‖,(7)其中‖E 2‖表示矩阵E 2的元素之和.基于定义(7),网络的n 社团结构越明显,则Q 值越大,因此可用Q 作为衡量社团结构有效度的标准.当Q >0.3时,具有相对明显的社团结构[17].仿真研究中,以所探测的模块度准确率作为判断社团结构探寻算法好坏的准则.即首先通过Matlab 生成具有已知社团结构(固定模块度Q 1)的网络;然后察看社团探寻算法能否揭示出网络真实的社团结构,并计算由该算法得出的网络社团结构相应模块度Q 2;最后以模块度准确率γ=Q 2/Q 1衡量社团结构探寻算法的有效性.4.1 具有明显社团结构的网络为了验证本文方法的有效性,根据网络社团结构的定义编写了Matlab 程序,生成具有相对明显社团结构的复杂网络.此网络为拥有24个节点,3个大小分别为9,7和8的社团,模块度为0.3325,记为网络1.应用Matlab 绘制该网络的2个第一非平凡特征向量中各节点相应元素的分布,如图1所示.应用本文两种方法对网络1聚类后,通过Ucinet 和Net draw 绘制社团结构,如图2所示.两种方法对网络1聚类后的模块度和准确率如表1所示.图1 网络1各节点相应元素的分布图2 网络1的社团结构表1 网络1的模块度和准确率采用的算法模块度准确率/%基于K 2means 聚类的算法0.3325100基于数据场理论的算法0.33251004.2 具有不明显社团结构的网络为了验证本文方法对社团结构不明显网络的有效性,根据Newman 等[17]提出的模块度可调的网络结构,通过Matlab 编写了相应程序,生成具有不明显社团结构的复杂网络.此网络为拥有128个节点,4个大小均为32的社团,模块度为0.2768,记为网络2.应用Matlab 绘制该网络的3个第一非平凡特征向量中各节点相应元素的分布,如图3所示.应用基于K 2means 聚类的算法,得到的社团结构见图图3 网络2各节点相应元素的分布(a ) 基于K 2means 聚类算法的网络2社团结构(b ) 基于数据场理论的网络2社团结构图4 不同算法得到的网络2社团结构83第3期高忠科等:基于K 2means 聚类和数据场理论的复杂网络社团结构探寻 4(a );应用基于数据场理论的算法,得到的社团结构见图4(b ).两种方法对网络2聚类后的模块度和准确率如表2所示.表2 网络2的模块度和准确率采用的算法模块度准确率/%基于K 2means 聚类的算法0.276299.78基于数据场理论的算法0.272898.554.3 Z achary 的空手道俱乐部内部成员关系网络社会网络大部分都具有社团结构,根据不同的属性可分为不同性质的社团.在实际网络分析中,本文采用社会网络分析的一个经典问题———Zachary ’s karate club st udy .Zachary 花费两年时间来观察美国一所大学中空手道俱乐部成员间的相互社会关系,基于这些成员在俱乐部内部及外部的社会关系,构造了他们之间的关系网[18],如图5(a )所示.在调查过程中,该俱乐部主管与校长因是否提高收费问题发生了争执,(a ) Zachary的空手道俱乐部内部成员关系网络(b ) 基于K 2means 聚类算法的Zachary网络社团结构(c ) 基于数据场理论的Zachary 网络社团结构图5 Z achary 网络社团结构的不同算法验证分析结果该俱乐部分裂成了分别以主管和校长为核心的两个小俱乐部.图5中的节点1和节点33分别代表俱乐部主管和校长,而方形和圆形节点分别代表分裂后的小俱乐部中的各个成员.对于Zachary 网络原始数据,应用本文的两种社团探寻算法得到的社团结构分别如图5(b )和图5(c )所示.4.4 仿真结果分析通过仿真结果可得出以下结论:对于模块度为0.3325的网络1,应用Matlab 以2个第一非平凡特征向量为坐标,绘制该网络各节点相应元素的分布.由图1可以看出,这些点主要集中在3个区域,因此可判断出此网络拥有3个社团.基于K 2means 聚类的社团探寻算法和基于数据场理论的社团探寻算法,均可以100%的准确率对其进行社团分析并找出其社团结构.对于社团结构不明显的网络,如模块度仅为0.2768的网络2,应用Matlab 以3个第一非平凡特征向量为坐标,绘制该网络各节点相应元素的分布.由图3可以看出,这些点主要集中在4个区域,因此可判断出此网络拥有4个社团.基于K 2means 聚类的社团探寻算法和基于数据场理论的社团探寻算法,分别可以99.78%和98.55%的准确率对其进行社团分析并找出其社团结构.在对Zachary 网络进行分析时,仅对节点3归属于哪个社团有争议.实际上,节点3处于两个社团的交界处,且都分别通过4条边与两个社团相连,因此它本身就有一定的歧义性.对比实际关系网络(图5(a )),对Zachary 网络原始数据分别应用本文的两种社团探寻算法,都较好地揭示了空手道俱乐部内部成员间的关系(图5(b )和图5(c )),因此这两种算法在网络社团探寻中都是有效的.通过复杂网络社团的研究发现:在具有社团结构的复杂网络中,社团内部比整个网络具有更加鲜明的小世界效应,即具有比整个网络更短的平均路径和更大的聚集系数.对网络2的相关数据统计结果如表3所示.因此在网络控制中,在相同的耦合强度下,对社团的同步控制比对整个网络的同步控制更容易实现[19].表3 网络2社团小世界效应统计数据网络2整体社团a社团b 社团c 社团d平均路径长度 2.0271 1.5530 1.5814 1.5284 1.5795聚集系数0.17680.29740.29420.32860.29385 结 论 复杂网络的社团结构已成为一个具有挑战性的研究课题.本文首先介绍了判断网络中的社团数目,以及基于节点度值、介数和聚集系数寻找社团中关183 控 制 与 决 策第24卷键节点的算法;然后提出和分析了两种社团探寻算法:基于K2means聚类的社团探寻算法和基于数据场理论的社团探寻算法;最后基于模块度的概念,分别对社团结构明显和社团结构不明显的两个由Matlab,Ucinet和Net draw生成的网络及Zachary 网络进行仿真分析,仿真结果验证了两种算法在复杂网络社团分析中的有效性.参考文献(R eferences)[1]Watts D J,Strogatz S H.Collective dynamics of“Small2world”networks[J].Nature,1998,393(6684):4402 442.[2]Latora V,Marchiori M.Efficient behavior of small2world networks[J].Physical Review Letters,2002,87(19):124.[3]Barabási A L,Albert R.Emergence of scaling inrandom networks[J].Science,1999,286(5439):5092 512.[4]Zhou T,Wang B H,Jin Y D,et al.Modellingcollaboration networks based on nonlinear preferential attachment[J].Int J of Modern Physics C,2007,18(2):2972314.[5]Dorogovtsev S N,Mendes J F F,Samukhin A N.Structure of growing networks with preferential linking [J].Physical Review Letters,2000,85(21):46332 4636.[6]许丹,李翔,汪小帆.局域世界复杂网络中的病毒传播及其免疫控制[J].控制与决策,2006,21(7):8172 820.(Xu D,Li X,Wang X F.On virus spreading in local2 world complex networks and its immunization control [J].Control and Decision,2006,21(7):8172820.) [7]Albert R,Barabási A L.Statistical mechanics ofcomplex network[J].Review of Modern Physics,2002, 74(1):47297.[8]Newman M E J,G irvan M.Finding and evaluatingcommunity structure in networks[J].Physical Review E,2004,69(2):262113.[9]Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks[J].PhysicaA,2005,352(24):6692676.[10]淦文燕,李德毅,王建民.一种基于数据场的层次聚类方法[J].电子学报,2006,34(2):2582262.(G an W Y,Li D Y,Wang J M.An hierarchicalclustering method based on data fields[J].Acta Electronic Sinica,2006,34(2):2582262.)[11]Fiedler M.Algebraic connectivity of graphs[J].Czechoslovak Mathematical J,1973,23(98):2982305.[12]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.(Wang X F,Li X,Chen G R.The theory and applications of complex networks[M].Beijing: Tsinghua University Press,2006.)[13]Higham D J,Kalnaa G,Milla K.Spectral clusteringand its use in bioinformatics[J].J of Computational and Applied Mathematics,2007,204(1):25237. [14]Ng A Y,Jordan M I,Weiss Y.On spectralclustering:Analysis and an algorithm[R].Berkeley: University of California,2006.[15]王柏,吴巍,徐超群,等.复杂网络可视化研究综述[J].计算机科学,2007,34(4):17223.(Wang B,Wu W,Xu C Q,et al.A survey on visualization of complex network[J].Computer Science,2007,34(4):17223.)[16]刘婷,胡宝清.基于聚类分析的复杂网络中的社团探测[J].复杂系统与复杂性科学,2007,4(1):28235.(Liu T,Hu B Q.Detecting community in complex networks using cluster analysis[J].Complex Systems and Complexity Science,2007,4(1):28235.)[17]Newman M E J.Fast algorithm for detectingcommunity structure in networks[J].Physical Review E,2004,69(6):125.[18]Zachary W W.An information flow model for conflictand fission in small groups[J].J of Anthropological Research,1977,33(4):4522473.[19]Boccaletti S,Latora V,Moreno Y,et plexnetworks:Structure and dynamics[J].Physics Reports,2006,424(4/5):1752308.283。
