分布式环境下基于马尔科夫链的图流三角近似计算

图三角数量的计算是计算网络聚集系数和传递性的重要步骤.大数据背景下,以采样为策略的近似计算成为图三角计算的主要方法,然而此类方法面临时空消耗和计算错误性两大难题.本文提出了一种针对图流的基于马尔科夫链的图三角近似计算算法,该算法以窗口作为图流处理单位,将马尔科夫链与采样相结合,保证降低错误率的同时实现动态适应内存空间的变化.实验显示,相较其他三角形近似计算算法,该算法在错误率上降低2~4倍,时间消耗上也有很大改进.     

大规模复杂网络下重叠社区的识别

随着网络规模的不断扩大,经典的复杂网络重叠社识别算法已不能高效处理现有的大规模网络图数据.本文在GraphLab并行计算模型上提出了基于重要节点扩展的重叠社区识别算法DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab).算法选取网络中PageRank值大的节点作为重要节点,计算其他节点归属于重要节点的节点归属度,并以重要节点为中心形成核心社区及扩展社区,最后根据重要节点间的连接紧密度合并核心社区及扩展社区,并计算出每个节点在所属社区里的节点重要度,实现了大规模网络的重叠社区识别.实验表明该算法与PD (Propinquity Dynamics)等现有并行算法相比更能有效地识别大规模网络的重叠社区结构.     

SCBT-index:基于谱编码的子图索引算法

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树（SCBT-index）,首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略：基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.     

面向复杂网络的异构网络表示学习综述

异构信息网络包含丰富的节点信息和链接信息,具有复杂异质性、高稀疏性、属性高维性等特性,这些特性给网络表示学习任务带来了巨大的挑战。异构网络表示学习通过在嵌入过程中将多样化的异质信息和结构信息进行有效融合,学习得到更有利于下游机器学习任务的低维特征向量。从异构网络表示学习方法的研究粒度出发,对近年的研究现状进行了比较全面的分析和讨论。首先探讨网络表示学习的产生动机,阐述了近年的异构网络表示学习的研究历程;然后对具有代表性的算法模型进行分类讨论,归纳其主要的研究内容和所使用的嵌入技巧。最后给出了未来工作中异构网络表示学习可能的研究方向和比较有价值的研究内容。     

大规模图数据划分算法综述

对大规模图数据划分算法进行了总结,介绍了并行环境下图计算模型,详述了大规模静态图划分算法和动态图划分算法,归纳了这些算法的优缺点以及适应性。最后,指出了关于大图划分尚未探索的有意义的研究课题。     

M2LSH:基于LSH的高维数据近似最近邻查找算法

在许多应用中,LSH(Locality Sensitive Hashing)以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本文提出了一种新的基于LSH的解决方案(M2LSH,2 Layers Merging LSH),对于数据分布不均匀的情况依然能得到一个比较好的查询效果.首先,将数据存放到具有计数功能的组合哈希向量表示的哈希桶中,然后通过二次哈希将这些桶号投影到一维空间,在此空间根据各个桶中存放的数据个数合并相邻哈希桶,使得新哈希桶中的数据量能够大致均衡.查询时仅访问有限个哈希桶,就能找到较优结果.本文给出了详细的理论分析,并通过实验验证了M2LSH的性能,不仅能减少访问时间,也可提高结果的正确率.     

SLSB-forest:高维数据的近似k近邻查询

近似k近邻查询的研究一直受到广泛关注,局部敏感散列(LSH)是解决此问题的主流方法之一.LSH及目前大部分改进版本都会面临以下问题:数据散列以后在桶里分布不均匀;无法准确计算对应参数k的查询范围建立索引.基于此,将支持动态数据索引的LSH和B-tree结合,构建新的SLSB-forest索引结构,使散列桶里的数据维持在一个合理的区间.针对SLSB-forest提出了两种查询算法:快速查找和准确率优先查找,并通过理论和实验证明查找过程中查询范围的动态变化.     

基于高阶相似性的属性网络表示学习

现有的网络表示学习方法缺少对网络中隐含的深层次信息进行挖掘和利用。对网络中的潜在信息做进一步挖掘,提出了潜在的模式结构相似性,定义了网络结构间的相似度分数,用以衡量各个结构之间的相似性,使节点可以跨越不相干的顶点,获取全局结构上的高阶相似性。利用深度学习,融合多个信息源共同参与训练,弥补随机游走带来的不足,使得多个信息源信息之间紧密结合、互相补充,以达到最优的效果。实验选取Lap、DeepWalk、TADW、SDNE、CANE作为对比方法,将3个真实世界网络作为数据集来验证模型的有效性,进行节点分类和链路重构的实验。在节点分类中针对不同数据集和训练比例,性能平均提升1.7个百分点;链路重构实验中,仅需一半维度便实现了更好的性能,最后讨论了不同网络深度下模型的性能提升,通过增加模型的深度,节点分类的平均性能增加了1.1个百分点。     

基于MapReduce的连续Skyline查询

随着Web网络和无线传感器网络的不断发展,大数据的出现对数据查询和处理产生了挑战。研究了MapReduce框架下移动对象的并行Skyline计算问题,采用基于角度划分的方法解决负载平衡问题,并提出了一种过滤策略进行剪枝提高计算效率,在此基础上分别实现了静态Skyline算法和基于事件跟踪的MR-Track算法。最后通过对比实验验证了算法的有效性。