基于谱聚类的复杂网络社团发现算法

复杂网络社团发现的研究对于控制疾病传播、网络病毒的传播等具有重大意义.针对已有社团发现算法时间复杂度过高,不适用于结构未知的大型网络等问题,结合谱聚类在识别未知分布数据集聚类方面的优势,以及模块度函数能够在大型网络中搜寻出最佳社团数目的能力,提出了基于谱聚类的社团发现算法--SCCF算法.实验结果表明,与已有的社团发现算法相比,SCCF算法效率更高,并且能够在网络节点数上万的大型网络中得到高质量的社团结构.     

基于最大生成树的社团划分算法

针对层次聚类算法存在复杂度高、准确度低等问题,提出了一种基于最大生成树的社团划分算法。该算法重新定义了节点间相似度,并利用最大生成树进行初始聚类,然后根据社团相似度合并局部社团得到最终划分结果。算法不仅降低了时间复杂度,而且在划分社团的准确度方面有所提高。将该方法在真实网络与人工网络上进行验证和比对,实验结果表明基于最大生成树的社团划分算法能够快速、准确地划分出网络中的社团结构。     

复杂网络的一种快速局部社团划分算法

为了快速准确地寻找大规模复杂网络的社团结构,文中基于节点度优先的思想,提出了一种新的寻找复杂网络中的局部社团结构的启发式算法.该算法的基本思想是从待求节点出发,基于节点的度有选择性的进行广度优先搜索,从而得到该节点所在的局部社团结构.由于该算法仅需要利用到节点的局部信息,因此时间复杂度很低,达到了线性的时间复杂度.将该算法应用于社会学中经典的Zachary网络,获得了满意的结果.最后,还分析了如何对该算法加以改进以进一步提高准确度.     

基于社团密度的社团发现算法

发现社团结构是研究复杂网络的重要前提,目前社团发现算法研究存在两个较为严峻的问题：评价函数单一和经典算法时间复杂度过大并且无法发现小粒度的社团。针对上述问题,本文首先提出了一种合理的发现算法评价函数,即社团完整度,实验证明,与经典的模块度函数 相比,社团完整度函数能够更合理地评价社团划分质量且社团完整度函数的灵敏度高于模块度函数;其次,本文提出了基于社团密度的社团发现算法,实验证明,该算法不仅可以发现小粒度的社团结构,随着网络节点数和边数的增加BDA算法在时间复杂度方面也具有明显的优势。最后,本文尝试将BDA算法应用在科学合作者网络并得到合理的社团结构。     

复杂网络强社团结构探测

社团结构是反映复杂网络整体性质的重要特征,本文从强社团结构定义出发提出简单启发式强社团结构探测算法,受启发因素为度-度负相关性和簇-度负相关性.利用该算法对空手道俱乐部成员关系网络和美国大学橄榄球队网络进行社团结构探测,验证了该算法能正确探测出网络的强社团结构.并将划分结果与传统划分进行比较分析,该算法未引入其它量化指标或中间变量,降低了计算复杂度,在采用方法上不同于单纯的分裂或聚合,有效地提高了探测速度,更适合大规模复杂网络社团结构探测.     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O(kd)。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O（kd）。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

基于节点相似度的网络社团检测算法研究

社团结构是众多复杂网络的统计特性之一,挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析,其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SUN,相比传统的基于边界数(betweenness)的节点分裂算法GN, SGN在速度和精度上都有明显改善;接着,在利用各种节点相似度计算方法得到节点间的相似度之后,采用几种经典的聚类分析算法对网络进行社团划分,在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。     

一个基于中心度的社团结构发现新算法*

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法（DCGN）。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算     

稳定的标签传播社团划分算法研究

快速稳定地发现复杂网络中的社团是近年来社团划分研究的热点。标签传播算法(LPA)具有接近线性的时间复杂度,能快速发现复杂网络中的社团结构,但是该算法在标签传播过程中存在不确定性和随机性,降低了划分结果的准确性和稳定性。为了解决这一问题,设计了一种稳定的标签传播社团划分算法(S-LPA)。该算法利用改进的K-Shell算法来计算节点全局影响力,并结合能反映节点局部影响力的度值以及邻居节点信息,计算节点综合影响力;在标签传播过程中,根据标签影响力更新标签;当网络中所有节点的标签不再变化或者迭代次数达到最大值时,拥有相同标签的节点划分到同一社团中。在真实网络和人工合成网络上的实验结果表明,S-LPA算法不仅具有线性时间复杂度,而且提高了社团划分的质量和稳定性。     

软距离计算的地震聚类方法*

传统的基于真实距离的聚类分析方法不利于地震不同断层破裂传播和愈合速度的精确计算。为提高地震预测精度,提出并建立了基于软距离计算的聚类方法。给出了基于软距离聚类过程、软距离计算方法以及具体的基于软距离计算的聚类算法。以现实的强震样本点作为聚类数据源,采用该聚类方法以及其它传统聚类方法对该样本数据进行聚类分析。分析结果表明,采用该聚类方法获得的聚类中心点更接近地壳应力场演变的客观真实性,该聚类分析方法为地震的断层带下次发生强震的精确计算提供了很好的计算依据。     

基于密度的聚类中心自动确定的混合属性数据聚类算法研究

面对广泛存在的混合属性数据,现有大部分混合属性聚类算法普遍存在聚类 质量低、聚类算法参数依赖性大、聚类类别个数和聚类中心无法准确自动确定等问题,针对 这些问题本文提出了一种基于密度的聚类中心自动确定的混合属性数据 聚类算法.该算法通过分析混合属性数据特征,将混合属性数据分为数 值占优、分类占优和均衡型混合属性数据三类,分析不同情况的特征选取 相应的距离度量方式.在计算数据集各个点的密度和距离分布图基础 上,深入分析获得规律: 高密度且与比它更高密度的数据点有较大距离的数 据点最可能成为聚类中心,通过线性回归模型和残差分析确定奇异 点,理论论证这些奇异点即为聚类中心,从而实现了自动确定聚类中心.采 用粒子群算法(Particle swarm optimization, PSO)寻找最优dc值,通过参数dc能够计算得到 任意数据对象的密度和到比它密度更高的点的最小距离,根据聚类 中心自动确定方法确定每个簇中心,并将其他点按到最近邻的更高 密度对象的最小距离划分到相应的簇中,从而实现聚类.最终将本文 提出算法与其他现有的多种混合属性聚类算法在多个数据集上进行 算法性能比较,验证本文提出算法具有较高的聚类质量.     

一种改进的K-means聚类算法

聚类是数据挖掘中的一种重要数据分析方法,K-means是一种基于划分的聚类算法。针对K-means算法中每次调整簇中心后确定新的簇中心需要大量的距离计算,提出一种利用簇中心的变化信息来确定新簇中心的方法,通过从动态簇中心集中选取候选集的方法减少了过滤算法的计算复杂度。理论分析表明,此算法在每一个迭代阶段能有效的减少距离计算数和计算时间。当数据集越大,维度越高时,算法的优越性越显著。     

基于可拓距的改进k-means聚类算法

针对现有聚类算法在初始聚类中心优化过程中存在首个初始聚类中心点落于边界非密集区域的不足,导致出现算法聚类效果不均衡问题,提出一种基于可拓距优选初始聚类中心的改进k-means算法。将样本经典距离向可拓区间映射,并通过可拓侧距计算方法得到可拓左侧距及可拓右侧距;引入平均可拓侧距概念,将平均可拓左侧距和平均可拓右侧距分别作为样本密集度和聚类中心疏远度的量化指标;在此基础上,给出初始聚类中心选取准则。通过与传统k-means聚类算法进行对比,结果表明改进后的k-means聚类算法选取的初始聚类中心分布更加均匀,聚类效果更好,尤其在对高维数据聚类时具有更高的聚类准确率和更好的均衡性。     

自适应密度峰值聚类算法

密度峰值聚类(DPC)算法是一种新型的聚类算法，具有调节参数少、无需迭代求解、能够发现非球形簇等优点；但也存在截断距离无法自动调节、聚类中心需要人工指定等缺点。针对上述问题，提出了一种自适应DPC(ADPC)算法，实现了基于基尼系数的自适应截断距离调节，并建立了一种聚类中心的自动获取策略。首先，综合考虑局部密度和相对距离两种因素以重新定义簇中心权值计算公式；然后，基于基尼系数建立自适应截断距离调节方法；最后，根据决策图和簇中心权值排序图提出自动选取聚类中心的策略。仿真实验结果表明，ADPC算法可以根据问题特征来自动调节截断距离并自动获取聚类中心点，而且在测试数据集上取得了比几种常用的聚类算法和DPC改进算法更好的结果。     

基于密度峰值的加权犹豫模糊聚类算法

由于人们对事物认知的局限性和信息的不确定性,在对决策问题进行聚类分析时,传统的模糊聚类不能有效解决实际场景中的决策问题,因此有学者提出了有关犹豫模糊集的聚类算法。现有的层次犹豫模糊K均值聚类算法没有利用数据集本身的信息来确定距离函数的权值,且簇中心的计算复杂度和空间复杂度都是指数级的,不适用于大数据环境。针对上述问题,文中提出了一种基于密度峰值思想的加权犹豫模糊聚类算法(WHFDP),首先给出了犹豫模糊元素集的补齐方法,并结合变异系数理论给出了新的距离函数权重计算公式,然后利用密度峰值选取簇中心,不仅降低了簇中心计算的复杂度,而且提高了对不同规模以及任意形状数据集的适应性,算法的时间复杂度和空间复杂度也降为多项式级,最后采用典型数据集进行仿真实验,证明了所提算法的有效性。     

自动确定聚类中心的数据竞争算法

针对数据竞争算法采用欧式距离计算相似度、人为指定聚类簇数以及聚类中心无法准确自动确定等问题,提出了一种自动确定聚类中心的数据竞争聚类算法。引入了数据场的概念,使得计算出的势值更加符合数据集的真实分布;同时,结合数据点的势能与局部最小距离形成决策图完成聚类中心点的自动确定;根据近邻原则完成聚类。在人工以及真实数据集上的实验效果表明,提出的算法较原数据竞争算法具有更好的聚类性能。     

虚拟环境下大数据智能并行聚类方法研究

为了减少虚拟环境下大数据运行时间,数据运行时能够反映出一定的规律性和特殊的分类性,需要对虚拟环境下大数据进行智能并行聚类。当前大数据聚类方法是根据K-均值聚类方法不断地进行大数据样本分类的调整,经过多次计算调整后达到数据并行聚类的效果,但每当有新的大数据流入时,都需要对当前全部数据进行K-均值聚类,计算过程复杂,聚类效率低。为此,提出了一种基于MapReduce的虚拟环境下大数据智能并行聚类方法。首先在虚拟环境下大数据中抽取小规模数据集并确定大数据簇的质心,采用Single法对所抽样的小规模数据进行聚类,获得虚拟环境下大数据属性的均值,利用最小距离分类规则将大数据属性的均值快速地向数据簇的真实中心移动,依据Davies-bouldin指标假设一个数据簇离散度参数,在此参数值中选出大数据智能并行聚类相似度最大值,最后利用聚类相似度最大值得到Davies-bouldin指数,以Davies-bouldin指数为基础将多个类别的质心间距以及聚类离散度指定阈值合并为一个类并进行迭代计算,得到数据最佳聚类中心位置,由此完成虚拟环境下大数据智能并行聚类。仿真实验结果证明,所提方法提高了大数据智能并行聚类的灵活性和普遍适用性,减少了聚类时间,并适合应用于教育技术领域,不仅可以使教育技术网络数据更加合理化,而且更加规范化。     

基于云计算和改进K-means算法的海量用电数据分析方法

针对小区居民用电数据挖掘效率低、数据量大等难题,进行了基于云计算和改进K-means算法的海量用电数据分析方法研究。针对传统K-means算法中存在初始聚类中心和K值难确定的问题,提出一种基于密度的K-means改进算法。首先,定义样本密度、簇内样本平均距离的倒数和簇间距离三者乘积为权值积,通过最大权值积法依次确定聚类中心,提高了聚类的准确率;然后,基于MapReduce模型实现改进算法的并行化,提高了聚类的效率;最后,以小区400户家庭用电数据为基础,进行海量电力数据的挖掘分析实验。以家庭为单位,提取出用户的峰时耗电率、负荷率、谷电负荷系数以及平段用电量百分比,建立聚类的数据维度特征向量,完成相似用户类型的聚类,同时分析出各类用户的行为特征。基于Hadoop集群的实验结果证明提出的改进K-means算法运行稳定、可靠,具有很好的聚类效果。     

一种基于K近邻的比较密度峰值聚类算法

快速搜索与发现密度峰值聚类算法（Fast Search and Discovery Density Peak Clustering Algorithm，CFSFDP）的聚类效果十分依赖截断距离[dc]的主观选取，而最佳[dc]值的确定并不容易，并且当处理分布复杂、密度变化大的数据集时，算法生成的决策图中类簇中心点与非类簇中心点的区分不够明显，使类簇中心的选取变得困难。针对这些问题，对其算法进行了优化，并提出了基于K近邻的比较密度峰值聚类算法（Comparative Density Peak Clustering algorithm Based on K-Nearest Neighbors，CDPC-KNN）。算法结合K近邻概念重新定义了截断距离和局部密度的度量方法，对任意数据集能自适应地生成截断距离，并使局部密度的计算结果更符合数据的真实分布。同时在决策图中引入距离比较量代替原距离参数，使类簇中心在决策图上更加明显。通过实验验证，CDPC-KNN算法的聚类效果整体上优于CFSFDP算法与DBSCAN算法，分离度实验表明新算法使类簇中心与非类簇中心点的区分度得到有效提高。