圖處理系列 (一)–網(wǎng)絡(luò)生成與圖入度計(jì)算

圖論和網(wǎng)絡(luò)科學(xué)都會(huì)涉及到大量對(duì)圖的特性的統(tǒng)計(jì)計(jì)算，一般將與圖數(shù)據(jù)相關(guān)的統(tǒng)計(jì)、挖掘、可視化統(tǒng)稱(chēng)為圖處理。本系列文章主要希望探討多方面的圖處理理論與方法，包括圖的統(tǒng)計(jì)性質(zhì)、表示方法、計(jì)算算法、計(jì)算模型以及基于圖論的數(shù)據(jù)挖掘等 內(nèi)容 。文章只有在

圖論和網(wǎng)絡(luò)科學(xué)都會(huì)涉及到大量對(duì)圖的特性的統(tǒng)計(jì)計(jì)算，一般將與圖數(shù)據(jù)相關(guān)的統(tǒng)計(jì)、挖掘、可視化統(tǒng)稱(chēng)為圖處理。本系列文章主要希望探討多方面的圖處理理論與方法，包括圖的統(tǒng)計(jì)性質(zhì)、表示方法、計(jì)算算法、計(jì)算模型以及基于圖論的數(shù)據(jù)挖掘等內(nèi)容。文章只有在必要的情況下區(qū)分圖和網(wǎng)絡(luò)的概念，所以文章術(shù)語(yǔ)中的圖與網(wǎng)絡(luò)將混用。

?1.圖處理引擎

目前通用的圖處理軟件主要包括兩種。一種主要基于遍歷算法、實(shí)時(shí)的圖數(shù)據(jù)庫(kù)，如?Neo4j?,?OrientDB?,?DEX?, 和?InfiniteGraph?.另一種則是以圖頂點(diǎn)為中心的消息傳遞批處理的并行引擎，如Hama?,?Golden Orb?,?Giraph?, 和?Pregel?.前者基本都基于tinkerpop的圖基礎(chǔ)框架，tinkerpop項(xiàng)目關(guān)系如圖1所示：

圖1 thinkerpop項(xiàng)目框架

其后者則主要是基于BSP模型所實(shí)現(xiàn)的并行圖處理包。BSP是由哈佛大學(xué)Viliant和牛津大學(xué)Bill McColl提出的并行計(jì)算模型。一個(gè)BSP模型由大量相互關(guān)聯(lián)的處理器(processor)所組成，它們之間形成了一個(gè)通信網(wǎng)絡(luò)。每個(gè)處理器都有快速的本地內(nèi)存和不同的計(jì)算線(xiàn)程。一次BSP計(jì)算過(guò)程包括一系列全局超步組成，虛擬主機(jī)，超步就是計(jì)算中一次迭代。每個(gè)超步主要包括三個(gè)組件：

?2.網(wǎng)絡(luò)生成

現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)包括無(wú)標(biāo)度網(wǎng)絡(luò)(Scale-free Network)、隨機(jī)網(wǎng)絡(luò)(Random Network)，依賴(lài)網(wǎng)絡(luò)(Dependency network)等。其中無(wú)標(biāo)度網(wǎng)絡(luò)是由匈牙利物理學(xué)家Albert-László Barabási在繪制互聯(lián)網(wǎng)拓?fù)涞难芯恐兴岢龅母拍?，他發(fā)現(xiàn)隨機(jī)網(wǎng)絡(luò)(社會(huì)、生物網(wǎng)絡(luò))中一些節(jié)點(diǎn)(hubs)有比其它節(jié)點(diǎn)更多的連接，從而整個(gè)網(wǎng)絡(luò)服從冪次定律(power-law)分布。于是Barabási和Albert提出了無(wú)標(biāo)度網(wǎng)絡(luò)的生成機(jī)制–“優(yōu)先連接”，用于解釋冪次定律分布的現(xiàn)象。因而優(yōu)先連接算法生成的網(wǎng)絡(luò)能夠模擬現(xiàn)實(shí)世界的網(wǎng)絡(luò)，我們采用R來(lái)實(shí)現(xiàn)BA 模型的網(wǎng)絡(luò)生成，采用的igraph包。

igraph是一個(gè)開(kāi)源的圖(有向、無(wú)向圖)生成和操作的類(lèi)庫(kù)，它底層由C實(shí)現(xiàn)，美國(guó)服務(wù)器，并實(shí)現(xiàn)了python, R語(yǔ)言的發(fā)行包，覆蓋全平臺(tái)(linux,window,MacOS)。它能夠生成正則圖(regular ?graphs)、隨機(jī)圖(random graphs)等,能給頂點(diǎn)和邊賦值，香港服務(wù)器，還可以計(jì)算不同的結(jié)構(gòu)屬性、圖同構(gòu)等。igraph支持的格式包括:Edge list,Pajek,GraphML等。Edge list是簡(jiǎn)單的txt文件，使用頂點(diǎn)id來(lái)定義邊。GraphML基于XML，用來(lái)存儲(chǔ)圖的邊和頂點(diǎn)屬性。更多的格式內(nèi)容請(qǐng)參考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)