Network Motif Detection： Algorithms, Parallel and Cloud Computing,and Related Tools

Network motif is defined as a frequent and unique subgraph pattern in a network, and the search involves counting all the possible instances or listing all patterns, testing isomorphism known as NP-hard and large amounts of repeated processes for statistical evaluation. Although many efficient algorithms have been introduced, exhaustive search methods are still infeasible and feasible approximation methods are yet implausible.Additionally, the fast and continual growth of biological networks makes the problem more challenging. As a consequence, parallel algorithms have been developed and distributed computing has been tested in the cloud computing environment as well. In this paper, we survey current algorithms for network motif detection and existing software tools. Then, we show that some methods have been utilized for parallel network motif search algorithms with static or dynamic load balancing techniques. With the advent of cloud computing services, network motif search has been implemented with MapReduce in Hadoop Distributed File System(HDFS), and with Storm, but without statistical testing. In this paper, we survey network motif search algorithms in general, including existing parallel methods as well as cloud computing based search, and show the promising potentials for the cloud computing based motif search methods.     

基于Hadoop建立云计算系统

云计算是2007年底正式提出的一个新概念,本文分析了云计算的特征和Hadoop的作用地位.针对Hadoop这样一个在集群上运行大型数据库处理应用程序的开放式源代码框架进行了云计算平台的实现,并进行了实验验证.     

一种基于无监督学习的社交网络流量快速识别方法

在分析了社交网络的发展和研究现状后,结合现有的网络流量识别方法和社交网络流量特征属性,提出了一种基于KMeans聚类算法的无监督学习社交网络流量识别方法.为了提高处理的高效性、实时性,利用开源云计算平台如doop上提供的M印Reduce架构进行分布式并行处理.对比实验结果表明,提出的方法能快速、高效的识别社交网络流量,并且识别准确率有显著提高.     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件，每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析，得到其一般情形下的竞争比当$s\geq（1+\sqrt{5}）/2$时为$1+1/s$，否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时，其竞争比当$s\geq（1+\sqrt{3}）/2$时不超过$1+1/（2s）$，否则为不超过$1+s/（2s+1）$。     

基于MapReduce和改进人工蜂群算法的并行划分聚类算法

针对大数据背景下基于划分的聚类算法中存在参数寻优能力不佳、初始中心敏感、数据倾斜等问题,提出一种基于MapReduce和人工蜂群(artificial bee colony,ABC)算法的并行划分聚类(the partitioning-based clustering algorithm by using im-prove artificial bee colony based on MapReduce,MR-PBIABC)算法.首先,提出基于反向学习和聚类准则函数的初始化策略(backward learning and the clustering criterion function,BLCCF),提升人工蜂群算法搜索的解质量,并将ABC算法和人工鱼群(artificial fish colony,AFS)算法结合,提出改进人工蜂群(improve artificial bee colony,IABC)算法,通过利用AFS算法最优解能力较强的特性,来提高ABC算法的寻优能力;其次,根据改进的人工蜂群算法IABC获取初始聚类中心,提出相对熵策略(rela-tive entropy strategy,RES)衡量人工鱼间的距离,保证获得的初始聚类中心是最优人工鱼状态,从而有效避免了随机选取初始聚类中心,引起的初始中心敏感的问题;再次,设计数据均衡策略(data balancing strategy,DBS),通过动态收集节点负载并分配节点间的负载,解决了节点上数据倾斜的问题;最后,结合MapReduce计算模型,并行挖掘簇中心,生成最终聚类结果.实验结果表明,MR-PBIABC算法的聚类效果更佳,同时在大数据环境下,能有效地提高并行计算的效率.     

基于MapReduce的Eclat改进算法研究与应用

针对Eclat算法在挖掘海量数据中的频繁项目集时存在的内存和计算资源不足等问题,将Eclat算法与目前流行的大规模数据集并行编程模型MapReduce结合,解决了Eclat算法在数据挖掘过程存在的瓶颈问题,运用于动车组故障诊断系统中,提高了关联规则挖掘的效率.     

基于Hadoop的校园云存储系统的研究

针对海量数据的存储问题,传统方法一般是通过购置更多数量的服务器来提升计算和存储能力,存在硬件成本高,存储效率低等缺点。通过对Hadoop框架和MapReduce编程模型等云计算核心技术的分析和研究,提出了一种基于Hadoop框架的海量数据存储模型,并在此模型的基础上,设计并实现了基于Hadoop的校园云存储系统。经过实验验证,该系统有效地解决了在校园办公、教学和科研过程中遇到的海量数据存储管理问题,具有开发成本低、处理速度较快、运行稳定、易于扩展等特点。     

并行MapReduce PLS算法及其在光谱分析中的应用

偏最小二乘(PLS)算法是常用的光谱建模算法,然而对于海量光谱处理情形,在单台计算机上建模及优化时间开销很大。基于MapReduce编程模式,提出了并行MapReduce PLS回归算法,包括并行数据标准化和并行主成分提取两个过程。在多台普通计算机上搭建Hadoop云计算集群平台,以近红外光谱处理为例,开展了算法验证实验。实验结果表明,基于MapReduce编程模式的并行PLS算法对海量近红外光谱数据集进行回归建模时,能有效提高建模速度,随计算机台数的增多可得到接近线性的加速比,并具有良好的扩展性。     

基于MapReduce的数据流频繁项集挖掘算法

针对传统数据流频繁项集计算中效率低、内存消耗大等问题,本文采用并行计算的思想设计了一种基于MapReduce的数据流频繁项集挖掘算法,首先,对进行数据分块压缩和传输,其次,将数据频繁项的计算分布在负载均衡的数据节点,可以有效保证数据的执行效率.最后通过一次调度处理合并各个节点产生的频繁项集并进行合并.理论分析和实验对比结果均表明,该算法对于并行处理数据流频繁项集的统计问题是有效可行的.