CAJ | 학술논문

为提高具有百万个节点以上的大规模图处理效率，通过研究大规模图和分布式框架Hadoop，提出了GDH大规模图直径算法。算法通过每次计算出半径相同的图节点，直到最后一次迭代求出所有节点的半径，然后用节点半径之和除以节点数算出大规模图直径。算法的时空复杂度不大，并且与经典的直径算法相比，GDH算法的效率高些。经测试雅虎网站和脸谱网站的网页数据，发现该算法可清晰地分析Web图的网页节点和社交图的人际关系。
위제고구유백만개절점이상적대규모도처리효솔，통과연구대규모도화분포식광가Hadoop，제출료GDH대규모도직경산법。산법통과매차계산출반경상동적도절점，직도최후일차질대구출소유절점적반경，연후용절점반경지화제이절점수산출대규모도직경。산법적시공복잡도불대，병차여경전적직경산법상비，GDH산법적효솔고사。경측시아호망참화검보망참적망혈수거，발현해산법가청석지분석Web도적망혈절점화사교도적인제관계。
To improve the processing efficiency of the large graph with millions nodes, the author proposed a GDH big graph diameter calculation algorithm by studying large graph and distributed framework Hadoop. Firstly,the algorithm calculates nodes with the same radius,all the radius of nodes will be calculated in the last iteration, then large graph diameter be calculated with the number of nodes divided by the sum of nodes radius. The time complexity and space complexity of the algorithm is not big, and experimental results show that it more efficient than the classical diameter estimation algorithm. What’ s more,by analyzing Yahoo and Facebook websites data,it can benefit both web analytics and interpersonal analysis of social network.