基于Spark的大规模网络结构发现算法

当今社会处于大数据时代,现实中的网络数据越来越多,其结构复杂、规模庞大,有效分析其结构对了解、应用其提供的信息具有重要作用。基于混合模型的网络结构发现算法可挖掘网络中的多类型聚类结构,但不能有效处理大规模网络。基于Graph X图计算模型,提出基于Spark的大规模网络的结构发现算法LNSES,从存储空间和运行时间两方面提升算法效率。为减少网络结构发现算法存储大规模网络邻接矩阵内存耗费量,LNSES算法将边、节点及节点静态属性值进行分布式存储,边分区记录节点连边,可作为索引进行节点间参数传递。为提高网络结构发现算法效率,边分区和节点分区进行拉链操作产生索引结构;更新参数时,节点根据索引找到边分区上对应的边,并行实现节点参数更新。在真实和人工大规模网络数据集上的实验结果表明:LNSES在运行时间和网络结构识别准确度方面都要优于同类网络结构发现算法,可以对大规模网络中的结构进行挖掘分析。     

基于Spark并行的密度峰值聚类算法

针对FSDP聚类算法在计算数据对象的局部密度与最小距离时,由于需要遍历整个数据集而导致算法的整体时间复杂度较高的问题,提出了一种基于Spark的并行FSDP聚类算法SFSDP。首先,通过空间网格划分将待聚类数据集划分成多个数据量相对均衡的数据分区;然后,利用改进的FSDP聚类算法并行地对各个分区内的数据执行聚类分析;最后,通过将分区间的局部簇集合并,生成全局簇集。实验结果表明,SFSDP与FSDP算法相比能够有效地进行大规模数据集的聚类分析,并且算法在准确性和扩展性方面都有很好的表现。     

Spark平台上利用网络加权Voronoi图的分散迭代社区聚类并行化研究

针对当下数据大规模增长对计算能力需求的急剧增长,传统独立运行的机器在大规模网络社区中执行社区检测操作时无法提供所需的数据处理能力的问题,提出一种网络加权Voronoi图的并行分散迭代社区聚类法(NWVD-PDICCM).利用基于网络加权Voronoi图的分散迭代社区聚类方法(NWVD-DICCM)提取大型网络的有效社区...     

基于MapReduce的大规模网络社区发现算法

社区发现是社会网络挖掘领域的基本问题.随着海量数据的迅速产生,传统社区发现算法愈发难以处理大规模社会网络.因此,针对大规模网络设计高效的社区发现算法意义重大.文中提出了一种基于MapReduce和k中心聚类的新型分布式算法.首先,该算法提出\"朋友圈系数\"技术,该技术可更加准确地度量结点间的距离.其次,该算法提出\"两阶段k中心聚类\"技术,该技术在选取中心点过程中融入结点中心度启发式信息,可显著优化输出结果的模块度.最后,该算法提出\"以模块度为优化目标的社区融合\"技术,该技术能够在无先验知识的前提下 自动确定网络中的社区数目.实验结果表明,所提算法的社区发现结果模块度明显优于最先进的社区发现算法.例如,相比LPA算法,其将模块度平均提升9.19倍.     

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

基于Spark的并行信任进化算法

为了提高信任进化(MET)算法在大数据环境下的时效性,提出一种基于Spark的并行MET算法——SparkMET.采用主从式架构,由主节点进行变异、交叉、选择过程,从节点计算适应度值.针对数据倾斜问题,提出一种新的数据分区策略——LBP算法,在SparkMET计算适应度值之前,根据合适的分区标签将数据重分区.在Epin...     

一种基于局部拓展的并行重叠社区发现算法

处理海量级数据的有效途径之一是将算法分解为一系列互不依赖的任务,然后利用开源工具并行地执行算法。而在重叠社区发现算法中,基于局部拓展的方法在拓展阶段往往仅需要局部社区及其相应的邻居结点的信息,因而具备可并行执行的可能性。提出了一种可并行化执行的局部拓展算法,并借助开源工具Spark将其实现。算法分为4个阶段。首先,挑选出一组不相关的中心结点并使用其对应的局部网络作为种子;其次,通过删除本身连接不是很紧密的局部网络来过滤选出的种子;然后,采用一种批量式的拓展策略来拓展种子,即一次向局部社区中添加一批邻居结点或从社区中删除一批结点;最后,融合相似的社区。在人工生成的网络以及真实世界中的网络上的实验结果显示 ,所提算法既准确又高效。     

基于Spark的层次聚类算法的并行化研究

随着大数据时代的来临,传统的计算模式已经不足以支撑如此大量的数据.基于内存计算的大数据并行化计算框架Spark的出现很好地解决了这一问题. CURE是一种基于取样和代表点的层次聚类算法,它采用迭代的方式,自底向上地合并两个距离最近的簇.与传统的聚类算法相比,CURE算法对异常点的敏感度更小.但是在处理大量数据的情况下,...     

基于Spark的点排序识别聚类结构算法

点排序识别聚类结构(Ordering Points to Identify the Clustering Structure,OPTICS)的密度聚类算法能以可视化的方式导出数据集的内在聚类结构,并且可以通过簇排序提取基本的聚类信息。但是该算法由于时空复杂度较高,不能很好地适应当今社会出现的大型数据集。随着云计算和并行计算的发展,提供了一种解决OPTICS算法复杂度缺陷的方法和一种建立在基于Spark内存计算平台的点排序识别聚类结构并行算法。测试的实验结果表明,它能极大地降低OPTICS算法对时间和空间的需要。     

基于Spark的并行Eclat算法

通过对Spark大数据平台以及Eclat算法的深入分析,提出了基于Spark的Eclat算法(即SPEclat)。针对串行算法在处理大规模数据时出现的不足,该方法在多方面进行改进：为减少候选项集支持度计数带来的损耗,改变了数据的存储方式;将数据按前缀进行分组,并划分到不同的计算节点,压缩数据的搜索空间,实现并行化计算。最终将算法结合Spark云计算平台的优势加以实现。实验表明该算法可在处理海量数据集时高效运行,并且在面对数据量大规模增长的情况下,具备良好的可扩展性。     

基于流量行为图的攻击检测方法

传统基于流的攻击检测无法完全捕获网络通信模式,难以对网络中的攻击事件进行有效检测,而流量行为图中包含的信息可以有效反映主机的真实情况。文章针对多类型网络攻击检测问题,提出了基于流量行为图的攻击检测方法,实现了基于流量行为图的攻击检测。检测方法基于聚类和生成学习模型,包含两个阶段,第一阶段通过聚类算法尽可能地过滤良性节点,第二阶段应用生成学习模型检测多种不同攻击事件。在公开数据集上的实验结果表明,文章提出的攻击检测方法可以有效检测出网络中存在的多种不同攻击事件。此外,系统使用基于Apache Spark的分布式处理框架,可以有效进行大规模数据处理。     

基于Spark的大数据聚类研究及系统实现

传统聚类算法由于单机内存和运算能力的限制已经不能满足当前大数据处理的要求,因而迫切需要寻找新的解决方法。针对单机内存运算问题,结合聚类算法的迭代计算特点,提出并实现了一种基于Spark平台的聚类系统。针对稀疏集和密集集两种不同类型的数据集,系统首先采用不同策略实现数据预处理;其次分析比较了不同聚类算法在Spark平台下的聚类性能,并给出最佳方案;最后利用数据持久化技术提高了计算速度。实验结果表明,所提系统能够有效满足海量数据聚类分析的任务要求。     

使用分布式De Bruijn图遍历基因拼接并行构建和化简

目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法,需要对长达数十亿BP长度的基因组测序数据进行处理.针对海量的基因测序数据,快速、高效和可扩展的基因拼接算法非常重要.虽然已出现一些并行拼接算法（如YAGA）开始研究这些问题,但是拼接过程中时间、空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序（list ranking）,而该方法需要多次对De Bruijn图的海量顶点信息进行分布式的排序,产生了大量的计算节点间的通信.单链化简可由1次De Bruijn 图深度优先遍历完成而不再需要表排序,于是提出一种基于分布式海量图遍历方法对单链化简进行优化,极大地减少了处理器间的通信和计算节点之间的数据移动,因而取得较好的扩展性,其算法复杂度为O（g/p）,通信复杂度为O（g）,这里g为参考序列的长度,p为处理器的核数.当对E.coli和Yeast数据集进行测试,处理器的核数从8个增加到512个时,算法可以得到13倍和10倍的加速比;当对C.elegans和人类1号染色体（chr1）数据集进行测试,处理器的核数从32个增加到512个时,算法可以得到7倍和10倍的加速比.     

基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。     

基于Spark的支持隐私保护的聚类算法

针对经典聚类方法无法应对任意背景知识下恶意攻击者在海量数据挖掘过程中的恶意攻击问题,结合差分隐私保护机制,提出一种适用于Spark内存计算框架下满足差分隐私保护的聚类算法,并从理论上证明了改进算法满足在Spark并行计算框架下的ε-差分隐私。实验结果表明,改进算法在保证聚类结果可用性前提下,具有良好的隐私保护性和满意的运行效率,在海量数据聚类分析的隐私保护挖掘中,具有很好的应用前景和价值。     

基于局部扩充优化的重叠社群检测方法的改进

生物信息学、社会网络、Web分析等方面的发展积累了大量的复杂网络数据信息,在对这些复杂网络进行社群检测时,往往会将一些节点归类于多个社群,目前已经提出了一些处理此类问题的算法(如LFK、GCE等),然而这类算法对局部扩充函数中参数α的选取过程复杂,无法一次性获取最优α,直接影响到了算法的可应用性.针对该缺点,提出了一种基于局部扩展的重叠社群检测的改进算法.该算法通过将α参数考虑进社群的成长过程中,使算法在保持原有速度与精度的情况下自适应地选取最优α.     

基于网络社团划分方法的多维数据聚类研究

为了解决传统聚类方法在多维数据集中聚类效果不佳的问题,提出了将网络社团划分的方法,并应用到多维数据聚类分析中。对于一个多维数据集,首先对分析对象进行特征提取,构建出每个对象的特征向量,通过计算皮尔森相关系数来度量不同特征向量之间的相似性,从而构建出一个相似性网络,采用Blondel算法对该网络进行社团划分达到聚类的效果。实验结果表明该方法可以在多维数据聚类中得到较好的聚类结果,准确率达到92.5%,优于K-means算法的75%。     

一种改进聚类算法在入侵检测中的应用

本文首先介绍入侵检测系统的基本结构和研究情况,然后介绍了K-means聚类算法的目标函数、算法流程;在总结K-means聚类算法存在的问题的基础上,提出了一种改进的聚类算法。该算法为基于数据挖掘的入侵检测的设计提供了相关可操作的理论依据。最后,通过模拟实验,证明了改进算法的有效性。