基于SPARK GraphX的YELP社區(qū)發(fā)現(xiàn)研究

袁麗娜 王紅勤 潘正軍

（廣州軟件學(xué)院軟件工程系 廣東省廣州市 510990）

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)分析逐漸成為研究熱點(diǎn)，而社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究中的重要領(lǐng)域。在這大數(shù)據(jù)時(shí)代，分布式計(jì)算平臺(tái)在大數(shù)據(jù)處理領(lǐng)域發(fā)揮著舉足輕重的作用，使用分布式計(jì)算平臺(tái)不僅能夠快速處理海量數(shù)據(jù)，還能提高算法的執(zhí)行效率，在實(shí)際生產(chǎn)中起著非常重要的作用。Hadoop 和Spark 是目前主流的開(kāi)源分布式處理平臺(tái)。本文重點(diǎn)研究使用Spark GraphX 對(duì)YELP 數(shù)據(jù)集進(jìn)行社區(qū)發(fā)現(xiàn)及可視化。

1 社區(qū)發(fā)現(xiàn)

1.1 復(fù)雜網(wǎng)絡(luò)

現(xiàn)實(shí)世界中，每個(gè)個(gè)體或者事物都至少屬于一個(gè)系統(tǒng)中，不同的個(gè)體之間通過(guò)各種方式進(jìn)行著交互，如社會(huì)關(guān)系、萬(wàn)維網(wǎng)、交通運(yùn)輸系統(tǒng)等，若將這些個(gè)體看成一個(gè)個(gè)節(jié)點(diǎn)，個(gè)體間的交互關(guān)系看成邊，即可將這些高度復(fù)雜性的網(wǎng)絡(luò)抽象成為一個(gè)復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)理論的研究最早來(lái)自于1736年數(shù)學(xué)家歐拉關(guān)于七橋問(wèn)題的解決，進(jìn)而哈佛大學(xué)心理學(xué)家通過(guò)“六度分離”理論研究了人與人之間的社交關(guān)系網(wǎng)絡(luò)圖，從此復(fù)雜網(wǎng)絡(luò)正式進(jìn)入了全新的領(lǐng)域。而對(duì)于復(fù)雜網(wǎng)絡(luò)的研究最具開(kāi)創(chuàng)性的文章主要有兩篇，其一為1998年6月在Nature 雜志上發(fā)表《“小世界”網(wǎng)絡(luò)的集體動(dòng)力學(xué)》的文章；其二為是1999年10月在Science 雜志上發(fā)表的《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》的文章。后續(xù)復(fù)雜網(wǎng)絡(luò)在學(xué)術(shù)界開(kāi)始進(jìn)行大量研究[1]。

復(fù)雜網(wǎng)絡(luò)區(qū)別于正常普通網(wǎng)絡(luò)主要表現(xiàn)在網(wǎng)絡(luò)規(guī)模龐大，節(jié)點(diǎn)種類(lèi)繁多，結(jié)構(gòu)復(fù)雜，連接多樣化、具有動(dòng)態(tài)性等[2]。

復(fù)雜網(wǎng)絡(luò)在探索其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，主要涉及以下統(tǒng)計(jì)類(lèi)指標(biāo)：

（1）度及度的分布：某節(jié)點(diǎn)的度指的是與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)總數(shù)。有向網(wǎng)絡(luò)度分布包括出度、入度兩種特征，從不相關(guān)節(jié)點(diǎn)到連接相關(guān)節(jié)點(diǎn)之間通過(guò)邊連接，這種邊的總數(shù)量稱為入度；從目標(biāo)節(jié)點(diǎn)到其它節(jié)點(diǎn)的邊的總數(shù)稱為出度。復(fù)雜網(wǎng)絡(luò)中，描述節(jié)點(diǎn)度分布狀況的函數(shù)是度分布函數(shù)。

（2）平均最短路徑：連接兩個(gè)不同節(jié)點(diǎn)所需最少邊的數(shù)量稱為兩節(jié)點(diǎn)之間的最短路徑。而任一節(jié)點(diǎn)到其余節(jié)點(diǎn)的平均距離叫做平均最短路徑，通常用來(lái)描述網(wǎng)絡(luò)的大小和節(jié)點(diǎn)及節(jié)點(diǎn)是否緊密聯(lián)系。

（3）聚類(lèi)系數(shù)：一個(gè)節(jié)點(diǎn)能夠連接的鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)與最大可能邊數(shù)之比稱為聚類(lèi)系數(shù)，通常用來(lái)描述網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的聚集程度。

（4）介數(shù)中心性：介數(shù)中心性是基于最短路徑的，用來(lái)衡量網(wǎng)絡(luò)圖的中心性。介數(shù)分為節(jié)點(diǎn)介數(shù)和邊介數(shù)。節(jié)點(diǎn)介數(shù)可以通過(guò)網(wǎng)絡(luò)中經(jīng)過(guò)某節(jié)點(diǎn)的最短路徑的數(shù)目除以所有最短路徑數(shù)目計(jì)算得到。邊介數(shù)可以通過(guò)網(wǎng)絡(luò)中經(jīng)過(guò)某條邊的最短路徑的數(shù)目除以所有最短路徑數(shù)目得到[3]。

復(fù)雜網(wǎng)絡(luò)發(fā)展不斷演化，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)展從開(kāi)始的規(guī)則網(wǎng)絡(luò)模型、隨機(jī)網(wǎng)絡(luò)模型，然后到小世界網(wǎng)絡(luò)模型、無(wú)標(biāo)度網(wǎng)絡(luò)模型等。

（1）規(guī)則網(wǎng)絡(luò)。規(guī)則網(wǎng)絡(luò)是指網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間通過(guò)既定的規(guī)則進(jìn)行連接，各個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目相同。常見(jiàn)的包括全局耦合網(wǎng)絡(luò)、最近鄰耦合網(wǎng)絡(luò)和星型耦合網(wǎng)絡(luò)。

（2）隨機(jī)網(wǎng)絡(luò)。隨機(jī)網(wǎng)絡(luò)即指網(wǎng)絡(luò)當(dāng)中的任意節(jié)點(diǎn)不是按照確定的規(guī)則連線，而是使用純粹的隨機(jī)方式進(jìn)行連線。如果節(jié)點(diǎn)按照某種自組織原則方式連線，將演化成各種不同網(wǎng)絡(luò)。

（3）小世界網(wǎng)絡(luò)。規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)兩個(gè)極端并不能完全展示真實(shí)網(wǎng)絡(luò)的相關(guān)特征，而小世界網(wǎng)絡(luò)模型則作為兩者的過(guò)渡。

無(wú)標(biāo)度網(wǎng)絡(luò)。很多網(wǎng)絡(luò)中其實(shí)只有少數(shù)節(jié)點(diǎn)與大量節(jié)點(diǎn)之間存在鏈接關(guān)系，在度分布上具有冪律形式，而多數(shù)節(jié)點(diǎn)則是存在極少數(shù)幾個(gè)鏈接，這些具有大量鏈接的節(jié)點(diǎn)稱為“集散節(jié)點(diǎn)”，所擁有的鏈接數(shù)可能高達(dá)幾百、幾千甚至幾百萬(wàn)。無(wú)標(biāo)度網(wǎng)絡(luò)就是包含這種集散節(jié)點(diǎn)的網(wǎng)絡(luò)，且網(wǎng)絡(luò)節(jié)點(diǎn)的度沒(méi)有明顯的特征長(zhǎng)度。

1.2 社區(qū)發(fā)現(xiàn)

科學(xué)家們根據(jù)圖論理論對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)構(gòu)建了大量數(shù)學(xué)模型，通過(guò)這些模型發(fā)現(xiàn)了其相似的規(guī)律及特征，因此社區(qū)結(jié)構(gòu)被發(fā)現(xiàn)成為了網(wǎng)絡(luò)存在的重要特征。同一社區(qū)具有一定的共性信息，社區(qū)內(nèi)部連接緊密，社區(qū)間連接稀疏。社區(qū)發(fā)現(xiàn)屬于挖掘復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的技術(shù)，實(shí)際上是一種網(wǎng)絡(luò)聚類(lèi)的方法，即可以將其理解為一類(lèi)具有相同特性的節(jié)點(diǎn)的集合。復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)分析不僅可以得到網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)的統(tǒng)計(jì)結(jié)果，也可以了解網(wǎng)絡(luò)的動(dòng)態(tài)特性。有效的社區(qū)結(jié)構(gòu)挖掘在很多領(lǐng)域都有非常重要的意義，例如交通網(wǎng)絡(luò)中，通過(guò)社區(qū)發(fā)現(xiàn)，可以幫助交通部門(mén)分析不同路段車(chē)流量的情況，從而合理地規(guī)劃網(wǎng)絡(luò)中交通燈的變化情況；也可以通過(guò)社區(qū)發(fā)現(xiàn)，快捷地捕獲到用戶感興趣的信息，實(shí)現(xiàn)熱點(diǎn)挖掘、個(gè)性化推薦和鏈接預(yù)測(cè)；還可以為經(jīng)濟(jì)、政策及社會(huì)活動(dòng)提供導(dǎo)向性作用，預(yù)測(cè)傳染病傳播等各方面。復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)在政治、醫(yī)學(xué)、經(jīng)濟(jì)、生物學(xué)和社會(huì)關(guān)系等領(lǐng)域均獲得廣泛關(guān)注[4]。

近幾年社區(qū)發(fā)現(xiàn)發(fā)展快速，目前，已經(jīng)有一些算法被提出來(lái)用于社區(qū)發(fā)現(xiàn)，這些算法從不同的角度出發(fā)，在不同的網(wǎng)絡(luò)上進(jìn)行模擬實(shí)驗(yàn)，研究了不同類(lèi)型的社區(qū)結(jié)構(gòu)，同時(shí)也提出了模塊度等衡量社區(qū)質(zhì)量的指標(biāo)。按照社區(qū)結(jié)構(gòu)來(lái)劃分社區(qū)發(fā)現(xiàn)算法，通常可以分為重疊社區(qū)發(fā)現(xiàn)算法和非重疊社區(qū)發(fā)現(xiàn)算法。按照算法檢測(cè)的網(wǎng)絡(luò)來(lái)劃分，通常分為可以應(yīng)用在無(wú)向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、符號(hào)網(wǎng)絡(luò)以及無(wú)符號(hào)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法。社區(qū)發(fā)現(xiàn)算法主要包括基于圖分割的Kernighan‐Lin 算法，基于層次聚類(lèi)的GN 算法，基于模塊度優(yōu)化的貪婪算法，模擬退火算法，半監(jiān)督聚類(lèi)的標(biāo)簽傳播算法等。

2 SPARK GraphX

Apache 下的頂級(jí)開(kāi)源項(xiàng)目Spark，是一款專(zhuān)門(mén)為快速處理大規(guī)模數(shù)據(jù)而設(shè)計(jì)的計(jì)算引擎，如今已經(jīng)形成了一套完整的生態(tài)系統(tǒng)，在此生態(tài)系統(tǒng)中既可以提供內(nèi)存計(jì)算框架進(jìn)行大規(guī)模數(shù)據(jù)計(jì)算，也可以使用Spark SQL 提供SQL 即席查詢，使用GraphX 進(jìn)行圖計(jì)算和處理，使用MLlib 機(jī)器學(xué)習(xí)，使用Spark Streaming 對(duì)流數(shù)據(jù)進(jìn)行流式計(jì)算。

Graph X 屬于Spark 生態(tài)系統(tǒng)中的子項(xiàng)目，主要用于進(jìn)行分布式圖處理，實(shí)際上就是圖算法的并行化實(shí)現(xiàn)，將大圖分割成一個(gè)個(gè)子圖，然后放在分布式集群上并行化處理。Graph X 利用Spark 為其圖的計(jì)算引擎，同時(shí)很好地融合其他Spark 生態(tài)系統(tǒng)中的組件，實(shí)現(xiàn)了大規(guī)模圖計(jì)算的功能[5]。

3 YELP社區(qū)發(fā)現(xiàn)研究

Yelp 是美國(guó)最大點(diǎn)評(píng)網(wǎng)站，于2004年創(chuàng)建，包括各種商戶，其中涵蓋各地餐館、酒店、購(gòu)物中心、旅游等各領(lǐng)域，網(wǎng)站的用戶則可以在Yelp 網(wǎng)站中交流各種購(gòu)物實(shí)踐體驗(yàn)，給體驗(yàn)過(guò)的相關(guān)商戶進(jìn)行打分評(píng)論等。在Yelp 網(wǎng)站中可以通過(guò)名稱等查詢某個(gè)酒店或餐廳，則可以看到酒店或餐廳的簡(jiǎn)要介紹及網(wǎng)友的星級(jí)評(píng)價(jià)和各種體驗(yàn)評(píng)論。通過(guò)各種體驗(yàn)評(píng)論用戶則可以對(duì)酒店或餐廳有更直觀的了解。因此用戶在獲取信息的需求之外，也有獲取服務(wù)的需要。本文對(duì)Yelp 社交網(wǎng)絡(luò)三萬(wàn)多條用戶信息數(shù)據(jù)集進(jìn)行分析，以Spark為平臺(tái)，使用Spark GraphX 為工具，進(jìn)行大規(guī)模的并行圖計(jì)算。關(guān)鍵實(shí)現(xiàn)代碼如下：

經(jīng)計(jì)算分析，雖然有三萬(wàn)多條用戶信息，但有些用戶之間沒(méi)有任何交集，本文通過(guò)sparkGraphX 根據(jù)圖的連通性將這些具有連通性的所有頂點(diǎn)及邊構(gòu)建出來(lái)，共3565 個(gè)頂點(diǎn)，分別用各種顏色的點(diǎn)表示，邊用白色表示，其社交網(wǎng)絡(luò)圖如圖1所示。

圖1：有關(guān)聯(lián)用戶的社交網(wǎng)絡(luò)圖

并且將此3565 個(gè)相關(guān)用戶的重要屬性數(shù)據(jù)抽取出來(lái)，計(jì)算出每個(gè)頂點(diǎn)的度，然后根據(jù)度的大小進(jìn)行倒序排序，如圖2所示。

圖2：用戶度中心度的冪律分布圖

通過(guò)圖2 可以看出，其符合冪律分布規(guī)律，因此該社交網(wǎng)絡(luò)屬于復(fù)雜網(wǎng)絡(luò)中的無(wú)標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)[6]。該Yelp 社交網(wǎng)絡(luò)中只有極少數(shù)的用戶和非常多的用戶有關(guān)聯(lián)，而大部分用戶只和少部分的用戶存在關(guān)聯(lián)關(guān)系。通過(guò)了解其社交網(wǎng)絡(luò)結(jié)構(gòu)，對(duì)于該網(wǎng)絡(luò)中重要用戶的度量及相關(guān)研究都有重要的作用。

4 結(jié)束語(yǔ)

本文重點(diǎn)研究了復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問(wèn)題，并采用Spark GraphX 對(duì)YELP 數(shù)據(jù)集進(jìn)行社區(qū)發(fā)現(xiàn)實(shí)現(xiàn)及可視化。YELP 社交網(wǎng)絡(luò)屬于復(fù)雜網(wǎng)絡(luò)中的無(wú)標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)，其特征是網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)只和很少節(jié)點(diǎn)連接，其社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)對(duì)于后續(xù)研究其社交網(wǎng)絡(luò)中信息傳播具有一定的實(shí)際意義。