基于SPARK GraphX的YELP社區發現研究

袁麗娜 王紅勤 潘正軍

（廣州軟件學院軟件工程系 廣東省廣州市 510990）

隨著互聯網的快速發展，網絡分析逐漸成為研究熱點，而社區發現是復雜網絡研究中的重要領域。在這大數據時代，分布式計算平臺在大數據處理領域發揮著舉足輕重的作用，使用分布式計算平臺不僅能夠快速處理海量數據，還能提高算法的執行效率，在實際生產中起著非常重要的作用。Hadoop 和Spark 是目前主流的開源分布式處理平臺。本文重點研究使用Spark GraphX 對YELP 數據集進行社區發現及可視化。

1 社區發現

1.1 復雜網絡

現實世界中，每個個體或者事物都至少屬于一個系統中，不同的個體之間通過各種方式進行著交互，如社會關系、萬維網、交通運輸系統等，若將這些個體看成一個個節點，個體間的交互關系看成邊，即可將這些高度復雜性的網絡抽象成為一個復雜網絡。復雜網絡理論的研究最早來自于1736年數學家歐拉關于七橋問題的解決，進而哈佛大學心理學家通過“六度分離”理論研究了人與人之間的社交關系網絡圖，從此復雜網絡正式進入了全新的領域。而對于復雜網絡的研究最具開創性的文章主要有兩篇，其一為1998年6月在Nature 雜志上發表《“小世界”網絡的集體動力學》的文章；其二為是1999年10月在Science 雜志上發表的《隨機網絡中標度的涌現》的文章。后續復雜網絡在學術界開始進行大量研究[1]。

復雜網絡區別于正常普通網絡主要表現在網絡規模龐大，節點種類繁多，結構復雜，連接多樣化、具有動態性等[2]。

復雜網絡在探索其網絡拓撲結構中，主要涉及以下統計類指標：

（1）度及度的分布：某節點的度指的是與該節點直接相連的節點總數。有向網絡度分布包括出度、入度兩種特征，從不相關節點到連接相關節點之間通過邊連接，這種邊的總數量稱為入度；從目標節點到其它節點的邊的總數稱為出度。復雜網絡中，描述節點度分布狀況的函數是度分布函數。

（2）平均最短路徑：連接兩個不同節點所需最少邊的數量稱為兩節點之間的最短路徑。而任一節點到其余節點的平均距離叫做平均最短路徑，通常用來描述網絡的大小和節點及節點是否緊密聯系。

（3）聚類系數：一個節點能夠連接的鄰居節點之間實際存在的邊數與最大可能邊數之比稱為聚類系數，通常用來描述網絡中一個節點的聚集程度。

（4）介數中心性：介數中心性是基于最短路徑的，用來衡量網絡圖的中心性。介數分為節點介數和邊介數。節點介數可以通過網絡中經過某節點的最短路徑的數目除以所有最短路徑數目計算得到。邊介數可以通過網絡中經過某條邊的最短路徑的數目除以所有最短路徑數目得到[3]。

復雜網絡發展不斷演化，網絡拓撲結構的發展從開始的規則網絡模型、隨機網絡模型，然后到小世界網絡模型、無標度網絡模型等。

（1）規則網絡。規則網絡是指網絡中任意兩個節點之間通過既定的規則進行連接，各個節點的鄰居節點數目相同。常見的包括全局耦合網絡、最近鄰耦合網絡和星型耦合網絡。

（2）隨機網絡。隨機網絡即指網絡當中的任意節點不是按照確定的規則連線，而是使用純粹的隨機方式進行連線。如果節點按照某種自組織原則方式連線，將演化成各種不同網絡。

（3）小世界網絡。規則網絡和隨機網絡兩個極端并不能完全展示真實網絡的相關特征，而小世界網絡模型則作為兩者的過渡。

無標度網絡。很多網絡中其實只有少數節點與大量節點之間存在鏈接關系，在度分布上具有冪律形式，而多數節點則是存在極少數幾個鏈接，這些具有大量鏈接的節點稱為“集散節點”，所擁有的鏈接數可能高達幾百、幾千甚至幾百萬。無標度網絡就是包含這種集散節點的網絡，且網絡節點的度沒有明顯的特征長度。

1.2 社區發現

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

近幾年社區發現發展快速，目前，已經有一些算法被提出來用于社區發現，這些算法從不同的角度出發，在不同的網絡上進行模擬實驗，研究了不同類型的社區結構，同時也提出了模塊度等衡量社區質量的指標。按照社區結構來劃分社區發現算法，通常可以分為重疊社區發現算法和非重疊社區發現算法。按照算法檢測的網絡來劃分，通常分為可以應用在無向網絡、有向網絡、符號網絡以及無符號網絡的社區發現算法。社區發現算法主要包括基于圖分割的Kernighan‐Lin 算法，基于層次聚類的GN 算法，基于模塊度優化的貪婪算法，模擬退火算法，半監督聚類的標簽傳播算法等。

2 SPARK GraphX

Apache 下的頂級開源項目Spark，是一款專門為快速處理大規模數據而設計的計算引擎，如今已經形成了一套完整的生態系統，在此生態系統中既可以提供內存計算框架進行大規模數據計算，也可以使用Spark SQL 提供SQL 即席查詢，使用GraphX 進行圖計算和處理，使用MLlib 機器學習，使用Spark Streaming 對流數據進行流式計算。

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

3 YELP社區發現研究

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

經計算分析，雖然有三萬多條用戶信息，但有些用戶之間沒有任何交集，本文通過sparkGraphX 根據圖的連通性將這些具有連通性的所有頂點及邊構建出來，共3565 個頂點，分別用各種顏色的點表示，邊用白色表示，其社交網絡圖如圖1所示。

圖1：有關聯用戶的社交網絡圖

并且將此3565 個相關用戶的重要屬性數據抽取出來，計算出每個頂點的度，然后根據度的大小進行倒序排序，如圖2所示。

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

通過圖2 可以看出，其符合冪律分布規律，因此該社交網絡屬于復雜網絡中的無標度網絡結構[6]。該Yelp 社交網絡中只有極少數的用戶和非常多的用戶有關聯，而大部分用戶只和少部分的用戶存在關聯關系。通過了解其社交網絡結構，對于該網絡中重要用戶的度量及相關研究都有重要的作用。

4 結束語

本文重點研究了復雜網絡中的社區發現問題，并采用Spark GraphX 對YELP 數據集進行社區發現實現及可視化。YELP 社交網絡屬于復雜網絡中的無標度網絡結構，其特征是網絡中的大部分節點只和很少節點連接，其社區結構的發現對于后續研究其社交網絡中信息傳播具有一定的實際意義。