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

Structure exploring algorithm on Spark for large-scale network

作　　者：柴变芳 欧朋成 胡吉朝 Chai Bianfang;Ou Pengcheng;Hu Jichao(College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China;Hebei Center for Ecological&Environmental Geology Research,Hebei GEO University,Shijiazhuang 050031,China)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]河北地质大学河北省高校生态环境地质应用技术研发中心,石家庄050031

出　　处：《计算机应用研究》2021年第2期409-413,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61503260);河北省自然科学基金资助项目(F2019403070)。

摘　　要：当今社会处于大数据时代,现实中的网络数据越来越多,其结构复杂、规模庞大,有效分析其结构对了解、应用其提供的信息具有重要作用。基于混合模型的网络结构发现算法可挖掘网络中的多类型聚类结构,但不能有效处理大规模网络。基于Graph X图计算模型,提出基于Spark的大规模网络的结构发现算法LNSES,从存储空间和运行时间两方面提升算法效率。为减少网络结构发现算法存储大规模网络邻接矩阵内存耗费量,LNSES算法将边、节点及节点静态属性值进行分布式存储,边分区记录节点连边,可作为索引进行节点间参数传递。为提高网络结构发现算法效率,边分区和节点分区进行拉链操作产生索引结构;更新参数时,节点根据索引找到边分区上对应的边,并行实现节点参数更新。在真实和人工大规模网络数据集上的实验结果表明:LNSES在运行时间和网络结构识别准确度方面都要优于同类网络结构发现算法,可以对大规模网络中的结构进行挖掘分析。Today’s society is in the era of big data.There are more and more network data in reality,which has complex structure and large scale.Analyzing their structure effectively plays an important role for understanding and applying their provided information.The network structure discovery algorithm based on hybrid model can mine the multi type clustering structure in the network,but it can not deal with large-scale network effectively.Based on GraphX graph computing model,this paper proposed a large scale network structure exploring algorithm LNSES(large scale network structure exploring algorithm on Spark)to improve the efficiency of the algorithm from two aspects of storage space and running time.In order to decreasing the large memory consumption for the network adjacency matrix,the LNSES algorithm stored attribute values of edge,node and node in a distributed manner.Edge partitions recorded edges,which were used as index for parameter transferring between nodes.For improving the efficiency of the structure exploring algorithm,a zipper operation between edge partition and node partition generated an index structure.At the stage of updating parameter,nodes found corresponding edges based on the index structure,and updated parameters in parallel.Experiments on large-scale real and artificial networks illustrate that LNSES is better than the similar network structure exploring algorithms in terms of running time and accuracy,and can mine and analyze the structure of large-scale network.

关 键 词：大规模网络 网络结构发现 并行图计算 SPARK 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]