陳虹君

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：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

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

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

1 Spark框架與Graphx

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

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

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

2 Graphx算法

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

2.1 Graphx中的PageRank算法

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

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

該PageRank模型在Spark的圖計算Graphx中提供了兩種調(diào)用方式：

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

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

2.2 Graphx中的ConnectedComponents算法

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

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

2.3 Graphx中的TriangleCount算法

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

3 總結(jié)

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

URL outURL

URL outURL

URL outURL

…… ……

對于新聞推薦，就應(yīng)該需要新聞名字以及他在某段時間內(nèi)被點擊查看的次數(shù)；或者根據(jù)與該新聞相關(guān)新聞的熱度值來推薦。對于朋友圈（好友推薦），則是一個大關(guān)系網(wǎng)的數(shù)據(jù)類型，這就需要知道每個人的一些特點，如興趣愛好、地區(qū)等，同時又要包括好友關(guān)系，可以轉(zhuǎn)化為圖的多重邊。圖計算的發(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] 機器學(xué)習(xí)庫[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] 云計算的分類[EB/OL].2010.http：//tech.qq.com/a/20101103/000074.htm.

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