圖論和網絡科學都會涉及到大量對圖的特性的統計計算，一般將與圖數據相關的統計、挖掘、可視化統稱為圖處理。本系列文章主要希望探討多方面的圖處理理論與方法，包括圖的統計性質、表示方法、計算算法、計算模型以及基于圖論的數據挖掘等 內容 。文章只有在
圖論和網絡科學都會涉及到大量對圖的特性的統計計算，一般將與圖數據相關的統計、挖掘、可視化統稱為圖處理。本系列文章主要希望探討多方面的圖處理理論與方法，包括圖的統計性質、表示方法、計算算法、計算模型以及基于圖論的數據挖掘等內容。文章只有在必要的情況下區分圖和網絡的概念，所以文章術語中的圖與網絡將混用。
?1.圖處理引擎
目前通用的圖處理軟件主要包括兩種。一種主要基于遍歷算法、實時的圖數據庫，如?Neo4j?,?OrientDB?,?DEX?, 和?InfiniteGraph?.另一種則是以圖頂點為中心的消息傳遞批處理的并行引擎，如Hama?,?Golden Orb?,?Giraph?, 和?Pregel?.前者基本都基于tinkerpop的圖基礎框架，tinkerpop項目關系如圖1所示：
圖1 thinkerpop項目框架
其后者則主要是基于BSP模型所實現的并行圖處理包。BSP是由哈佛大學Viliant和牛津大學Bill McColl提出的并行計算模型。一個BSP模型由大量相互關聯的處理器(processor)所組成，它們之間形成了一個通信網絡。每個處理器都有快速的本地內存和不同的計算線程。一次BSP計算過程包括一系列全局超步組成，虛擬主機，超步就是計算中一次迭代。每個超步主要包括三個組件：
?2.網絡生成
現實世界的復雜網絡包括無標度網絡(Scale-free Network)、隨機網絡(Random Network)，依賴網絡(Dependency network)等。其中無標度網絡是由匈牙利物理學家Albert-László Barabási在繪制互聯網拓撲的研究中所提出的概念，他發現隨機網絡(社會、生物網絡)中一些節點(hubs)有比其它節點更多的連接，從而整個網絡服從冪次定律(power-law)分布。于是Barabási和Albert提出了無標度網絡的生成機制–“優先連接”，用于解釋冪次定律分布的現象。因而優先連接算法生成的網絡能夠模擬現實世界的網絡，我們采用R來實現BA 模型的網絡生成，采用的igraph包。
igraph是一個開源的圖(有向、無向圖)生成和操作的類庫，它底層由C實現，美國服務器，并實現了python, R語言的發行包，覆蓋全平臺(linux,window,MacOS)。它能夠生成正則圖(regular ?graphs)、隨機圖(random graphs)等,能給頂點和邊賦值，香港服務器，還可以計算不同的結構屬性、圖同構等。igraph支持的格式包括:Edge list,Pajek,GraphML等。Edge list是簡單的txt文件，使用頂點id來定義邊。GraphML基于XML，用來存儲圖的邊和頂點屬性。更多的格式內容請參考igraph幫助文檔。用法如下所示：
barabasi.game(n, power = 1, m = NULL, out.dist = NULL, out.seq = NULL, out.pref = FALSE, zero.appeal = 1, directed = TRUE, algorithm = c(, , ), start.graph = NULL)
