陳虹君

摘要：隨著搜索引擎對(duì)網(wǎng)頁(yè)的排名的需要，以及社交網(wǎng)絡(luò)的興起，海量關(guān)系所產(chǎn)生的大數(shù)據(jù)需要得到處理。圖計(jì)算在數(shù)據(jù)關(guān)系的分析上發(fā)揮著其巨大的潛能。Spark框架是Hadoop大數(shù)據(jù)平臺(tái)上整合能力強(qiáng)，處理速度快的內(nèi)存模型框架，它的圖處理Graphx也得到快速發(fā)展。該文先介紹Spark框架與Graphx的關(guān)系與發(fā)展。接著分析了Graphx中的三個(gè)典型的算法。最后總結(jié)了Graphx的場(chǎng)景應(yīng)用。

關(guān)鍵詞：大數(shù)據(jù)；Hadoop；Spark；圖計(jì)算；Graphx；PageRank

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）01-0075-03

Research on Graphx Algorithms in Spark Framework

CHEN Hong-jun

（Chengdu College of University of Electronic Science and Technology of China， Chengdu 611731， China）

Abstract： As the search engine need of Webpage ranking， and the rise of social networking， large mass data relations need to process. Graph calculation plays its great potential in the analysis of data relationship. The Spark framework is memory model frame which is deployed on Hadoop. It has great integration ability； high processing speed.So the graph processing Graphx also obtained the fast development. In this paper， firstly introduce the relation and development of Spark framework and Graphx. Then analyze the three typical algorithms in Graphx. Finally sum up the scene using Graphx.

Key words： big data； Hadoop； Spark； graphs computing； Graphx； PageRank

圖計(jì)算可以用來處理復(fù)雜的數(shù)據(jù)聯(lián)系。比如：整個(gè)社交網(wǎng)站就像一個(gè)關(guān)系網(wǎng)一樣，處處充滿了聯(lián)系。在大數(shù)據(jù)時(shí)代，網(wǎng)絡(luò)關(guān)系日益豐富的今天，大數(shù)據(jù)的圖處理正迅猛發(fā)展。而圖在數(shù)據(jù)分析上的典型應(yīng)用就是Facebook、twitter這樣的社交網(wǎng)站上的對(duì)用戶及話題的分析，因?yàn)橛脩糁g可能隨時(shí)都會(huì)產(chǎn)生新的聯(lián)系，不同用戶對(duì)于不同話題也有不同的傾向。

圖用頂點(diǎn)（vertex）來表示數(shù)據(jù)對(duì)象，用邊（edge）來表示數(shù)據(jù)之間的聯(lián)系，而邊的權(quán)值可以是價(jià)值、身份、時(shí)間等各種抽象或者邏輯上的意義。圖可以轉(zhuǎn)化為數(shù)學(xué)上的鄰接矩陣，因此對(duì)圖的各種算法應(yīng)用大多都要建立在數(shù)學(xué)之上；圖的應(yīng)用算法需要用數(shù)學(xué)公式來分析和證明，同樣一個(gè)圖能否并行處理也要依賴于它相應(yīng)的數(shù)據(jù)矩陣是否可以再分。

1 Spark框架與Graphx

Spark是基于內(nèi)存的編程模型，它可以把中間的迭代過程不放在磁盤中，直接數(shù)據(jù)不落地在內(nèi)存中執(zhí)行，極大地提高了它的執(zhí)行速度。Spark分為四大模塊：Spark SQL-RDD（數(shù)據(jù)執(zhí)行的基本單元），MLlib（機(jī)器學(xué)習(xí)）、Graphx（圖計(jì)算），Spark Streaming（實(shí)時(shí)處理），整個(gè)框架形成了大數(shù)據(jù)處理各種應(yīng)用場(chǎng)景編程的一致性。

GraphX是新的（alpha）Spark用于圖表和圖形，并行計(jì)算的的API。 GraphX在一個(gè)高層次上， 延伸了Spark RDD。 通過引入Resilient Distributed Property Graph （彈性分布式屬性圖）： 一個(gè)有向多重圖能附加每個(gè)頂點(diǎn)屬性和邊的屬性。為了支持圖形計(jì)算， GraphX 公開了一組基本的運(yùn)算符，比如：subgraph （子圖）、 joinVertices、mapReduceTriplets，以及一個(gè)最優(yōu)的轉(zhuǎn)變的Pregel API. 此外， GraphX 包含一個(gè)對(duì)圖形算法（algorithms）和構(gòu)建器 （builders） 不斷增長(zhǎng)的包集合，用以簡(jiǎn)化圖形分析任務(wù)。

在 GraphX的發(fā)布之前，Spark中的圖形計(jì)算使用Bagel來表達(dá)， 即對(duì)Pregel的實(shí)現(xiàn)。 GraphX改進(jìn)了Bagel 通過更豐富的特性圖形 API，使用比Pregel更精簡(jiǎn)的版本， 使系統(tǒng)得到優(yōu)化，提升了性能并減少了內(nèi)存開銷。

2 Graphx算法

Graphx作為Spark的圖處理框架，支持以下算法：PageRank算法、ConnectedComponents算法、TriangleCounting算法等。PageRank算法是Google專有的算法，用于衡量特定網(wǎng)頁(yè)相對(duì)于搜索引擎索引中的其他網(wǎng)頁(yè)而言的重要程度。ConnectedComponents算法，用于找出與該主題有關(guān)的用戶。TriangleCounting算法，用于找出與該用戶具有最穩(wěn)定關(guān)系的朋友圈。

2.1 Graphx中的PageRank算法

一個(gè)頁(yè)面的重要性可以由其“得票數(shù)”確定?！暗闷睌?shù)”由所有鏈向它的頁(yè)面的重要性來決定。到一個(gè)頁(yè)面的超鏈接相當(dāng)于對(duì)該頁(yè)投一票。一個(gè)超鏈接指向了多個(gè)頁(yè)面s個(gè)，那么它對(duì)每個(gè)頁(yè)面的貢獻(xiàn)值是1/s。一個(gè)頁(yè)面的PageRank是由所有鏈向它的頁(yè)面的重要性經(jīng)過遞歸算法得到的。一個(gè)有較多鏈入的頁(yè)面會(huì)有較高的得分，相反如果一個(gè)頁(yè)面沒有任何鏈入頁(yè)面，那么它沒有得分。數(shù)學(xué)公式[1]如（1） ：

Pi，P2，…， Pn是被研究的頁(yè)面，M（Pi）是Pi鏈入頁(yè)面的數(shù)量，L（Pj）是Pj鏈出頁(yè)面的數(shù)量，而N是所有頁(yè)面的數(shù)量。

該P(yáng)ageRank模型在Spark的圖計(jì)算Graphx中提供了兩種調(diào)用方式：

第一種：靜態(tài)調(diào)用方式，如圖1。在調(diào)用時(shí)提供一個(gè)參數(shù)number，用于指定迭代次數(shù)，即無論結(jié)果如何，該算法在迭代number次后停止計(jì)算，返回圖結(jié)果。

第二種：動(dòng)態(tài)調(diào)用方式，如圖2。在調(diào)用時(shí)提供一個(gè)參數(shù)tol，用于指定前后兩次迭代的結(jié)果差值應(yīng)小于tol，以達(dá)到最終收斂的效果時(shí)才停止計(jì)算，返回圖結(jié)果。

2.2 Graphx中的ConnectedComponents算法

在Graphx中的ConnectedComponent算法[2]是指在無向圖中，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱vi和vj連通。如果圖中任意兩個(gè)頂點(diǎn)之間都連通，則稱該圖為連通圖，否則，稱該圖為非連通圖，則其中的極大連通子圖稱為連通分量，這里所謂的極大是指子圖中包含的頂點(diǎn)個(gè)數(shù)極大。連通圖只有一個(gè)連通分量，即其自身；非連通的無向圖有多個(gè)連通分量，如圖3、圖4。

尋找連通圖在一些場(chǎng)景中是圖計(jì)算的核心應(yīng)用。比如：以關(guān)鍵詞集合識(shí)別集群。以每個(gè)定點(diǎn)表示每一項(xiàng)（Item），以邊代表它們之間的聯(lián)系，或者認(rèn)為他們之間具有相似性。因此。連通圖就對(duì)應(yīng)了不同類別的項(xiàng)集合。

2.3 Graphx中的TriangleCount算法

在Graphx中的的TriangleCount算法可以用于社區(qū)發(fā)現(xiàn)。此應(yīng)用與微博上，表示你關(guān)注的人且關(guān)注你的人，大家的關(guān)注關(guān)系就會(huì)形成很多的三角形，說們與你形成三角形的人與你有穩(wěn)定的關(guān)系，大家關(guān)系緊密。

3 總結(jié)

對(duì)于不同的應(yīng)用場(chǎng)景，需要不同的數(shù)據(jù)，而對(duì)于不同的算法，同樣的數(shù)據(jù)可能又有不同的數(shù)據(jù)格式。對(duì)于圖技術(shù)而言，在各種工程中都可能某一部分會(huì)用到圖處理，概而言之就是只要涉及到計(jì)算熱度值（例如PageRank，新聞推薦，朋友圈分析）都可以使用圖來處理。對(duì)于上次的PageRank的實(shí)例，需要的數(shù)據(jù)就應(yīng)滿足：一個(gè)網(wǎng)頁(yè)URL及該網(wǎng)頁(yè)鏈出的URL，可表示如下：

URL outURL

URL outURL

URL outURL

…… ……

對(duì)于新聞推薦，就應(yīng)該需要新聞名字以及他在某段時(shí)間內(nèi)被點(diǎn)擊查看的次數(shù)；或者根據(jù)與該新聞相關(guān)新聞的熱度值來推薦。對(duì)于朋友圈（好友推薦），則是一個(gè)大關(guān)系網(wǎng)的數(shù)據(jù)類型，這就需要知道每個(gè)人的一些特點(diǎn)，如興趣愛好、地區(qū)等，同時(shí)又要包括好友關(guān)系，可以轉(zhuǎn)化為圖的多重邊。圖計(jì)算的發(fā)展隨著社交網(wǎng)絡(luò)的發(fā)展將得到飛速的發(fā)展。

參考文獻(xiàn)：

[1] PageRank算法[EB/OL].2012.http：//blog.csdn.net/hguisu/article/details/7996185.

[2] 連通圖[EB/OL].http：//www3.cs.stonybrook.edu/～algorith/files/dfs-bfs.shtml.

[3] Spark編程指南[EB/OL].2013.http：//spark.apache.org/docs/latest/programming-guide.html.

[4] 機(jī)器學(xué)習(xí)庫(kù)[EB/OL].2013.http：//blog.csdn.net/johnny_lee/article/details/25656343.

[5] Graphx學(xué)習(xí)[EB/OL].2012.http：//spark.apache.org/docs/latest/graphx-programming-guide.html.

[6] 云計(jì)算的分類[EB/OL].2010.http：//tech.qq.com/a/20101103/000074.htm.

[7] 最近的spark文檔[EB/OL].2014.http：//spark.apache.org/docs/latest/.