R的網(wǎng)絡(luò)分析初步《R語言數(shù)據(jù)挖掘》學(xué)習(xí)目標(biāo)·

理論方面，掌握數(shù)據(jù)關(guān)系網(wǎng)絡(luò)拓?fù)浠硎镜囊话闼悸罚?/p>

掌握網(wǎng)絡(luò)描述性分析的層次、角度和各種測度量的意

義，適用性和應(yīng)用場景。了解規(guī)則網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、

無標(biāo)度網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)的特點(diǎn)和聯(lián)系·

實(shí)踐方面，掌握R的復(fù)雜網(wǎng)絡(luò)構(gòu)建、分析和可視化實(shí)

現(xiàn)、應(yīng)用以及結(jié)果解讀，能夠正確運(yùn)用復(fù)雜網(wǎng)絡(luò)分析

實(shí)際數(shù)據(jù)中的關(guān)系《R語言數(shù)據(jù)挖掘》網(wǎng)

絡(luò)

分

析■研究網(wǎng)絡(luò)構(gòu)成及網(wǎng)絡(luò)成員間的相互影響，是揭示事物

相關(guān)性的另一個(gè)獨(dú)特視角■網(wǎng)絡(luò)分析的基本框架■構(gòu)建網(wǎng)絡(luò)：網(wǎng)絡(luò)由系統(tǒng)內(nèi)部各成員(網(wǎng)絡(luò)中稱為節(jié)

點(diǎn))和成員之間的聯(lián)系(網(wǎng)絡(luò)中稱為連接)構(gòu)成■網(wǎng)絡(luò)的基本分析：通常按照個(gè)體層次、中間層次和

全局層次，逐層遞進(jìn)展開。不同層次的分析服務(wù)于

不同的研究目標(biāo)■網(wǎng)絡(luò)的深入分析：將依據(jù)網(wǎng)絡(luò)類型，從統(tǒng)計(jì)角度采

用不同模型，對網(wǎng)絡(luò)的靜態(tài)特征和動(dòng)態(tài)發(fā)展做進(jìn)一

步的分析和預(yù)測《R語言數(shù)據(jù)挖掘》■網(wǎng)絡(luò)分析的基礎(chǔ)是網(wǎng)絡(luò)的定義及表示，通常有兩種相

互聯(lián)系的表示方式：圖論表示方式、矩陣表示方式■圖論表示方式：從圖論角度看，網(wǎng)絡(luò)由多個(gè)節(jié)點(diǎn)和節(jié)

點(diǎn)間的連接(也稱邊)組成，是一種廣義的圖■網(wǎng)絡(luò)可記為G=(N,E)。網(wǎng)絡(luò)G

中沿著連接在不同節(jié)

點(diǎn)間的移動(dòng)，稱為游走■依連接的方向性，網(wǎng)絡(luò)分為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)；

依連接的類型，網(wǎng)絡(luò)分為無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)。依

節(jié)點(diǎn)類型，網(wǎng)絡(luò)分為1-模網(wǎng)絡(luò)和2-模網(wǎng)絡(luò)網(wǎng)絡(luò)的定義表示及構(gòu)建《R語言數(shù)據(jù)挖掘》■無向網(wǎng)絡(luò)：網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接沒有方向性■涉及很多基本概念■在網(wǎng)絡(luò)G中，若存在節(jié)點(diǎn)沿連接“一步”游走回自

身，則稱網(wǎng)絡(luò)G存在環(huán)■在網(wǎng)絡(luò)G中，若一對節(jié)點(diǎn)被兩個(gè)以上的連接相連，

則稱網(wǎng)絡(luò)G存在多邊■若網(wǎng)絡(luò)G存在環(huán)或者多邊，則稱網(wǎng)絡(luò)G為多重圖。否

則為簡單圖。網(wǎng)絡(luò)的分析中，通常需將多重圖簡化

為簡單圖后再研究圖論表示方式：無向網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》■涉及很多基本概念■若從網(wǎng)絡(luò)G

中的節(jié)點(diǎn)n,出發(fā)沿著連接游走可“抵達(dá)”

節(jié)點(diǎn)n,,

稱為節(jié)點(diǎn)n,可達(dá)節(jié)點(diǎn)n,■若從網(wǎng)絡(luò)G

中的任意節(jié)點(diǎn)n,出發(fā)沿著連接游走可達(dá)

網(wǎng)絡(luò)中其他任意節(jié)點(diǎn)n,

則稱網(wǎng)絡(luò)G是連通的■若從網(wǎng)絡(luò)G

的某個(gè)節(jié)點(diǎn)開始沿著連接游走，能夠返

回同一節(jié)點(diǎn)，則稱該網(wǎng)絡(luò)G

存在回路■對于網(wǎng)絡(luò)G

中的一個(gè)連通子網(wǎng)絡(luò)G'=(N’,E'),若將

G’之外的屬于G

的任意節(jié)點(diǎn)加到網(wǎng)絡(luò)G’中，網(wǎng)絡(luò)G'

就不再具有連通性，則稱G’為網(wǎng)絡(luò)G

的一個(gè)組件圖論表示方式：無向網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》圖論表示方式：無向網(wǎng)絡(luò)■涉及很多基本概念■若網(wǎng)絡(luò)G

中任意節(jié)點(diǎn)n,和n

間均存在一個(gè)連接e

(

直

接相連),則稱網(wǎng)絡(luò)G

是完備的，否則為非完備的G1:無向網(wǎng)絡(luò)(多重圖)

G2:

無向連通網(wǎng)絡(luò)G3:

無向不連通網(wǎng)絡(luò)

G4:完備圖《R語言數(shù)據(jù)挖掘》■涉及很多R函數(shù)■

graph.formula

(公式)■

graph.empty(n=N,directe

d=TRUE/FALSE)■vcount(graph=網(wǎng)絡(luò)類對象

名)■ecount(graph=

網(wǎng)絡(luò)類對象

名)■V

(網(wǎng)絡(luò)類對象名)■E

(網(wǎng)絡(luò)類對象名)■

add.edges

(網(wǎng)絡(luò)類對象名

,連接)■e(no.of.nodes=N,k=N

一1,directed=FALSE/TRUE,mul

tiple=FALSE/TRUE)■simplify(graph=網(wǎng)絡(luò)類對象

名)■

plot(網(wǎng)絡(luò)類對象名，layout=

可視化方法名)■is.connected(graph=

網(wǎng)絡(luò)

類對象名)■subcomponent(graph=網(wǎng)絡(luò)類

對象名，v=指定節(jié)點(diǎn))圖論表示：無向網(wǎng)絡(luò)的R函數(shù)《R語言數(shù)據(jù)挖掘》■有向網(wǎng)絡(luò)：網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接有方向性■涉及很多基本概念■互惠關(guān)系■若從有向網(wǎng)絡(luò)G

中的任意節(jié)點(diǎn)n

出發(fā)沿有向連接e游走，可“抵達(dá)”其他任意節(jié)點(diǎn)n,則稱有向網(wǎng)絡(luò)

G

是強(qiáng)連通的■若從有向網(wǎng)絡(luò)G

中的任意節(jié)點(diǎn)n,出發(fā)，忽略連接的

方向性做無向游走，并可“抵達(dá)”其他任意節(jié)點(diǎn)n,

則稱有向網(wǎng)絡(luò)G

是弱連通圖論表示方式：有向網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》有向網(wǎng)絡(luò)G

均稱為有向不循環(huán)圖網(wǎng)絡(luò)■涉及很多R函數(shù)■

is.mutual(graph=網(wǎng)絡(luò)類對象

名

)■is.dag(graph=

網(wǎng)絡(luò)類對象名)G7:

有向不循環(huán)網(wǎng)絡(luò)(弱連通)■涉及很多基本概念■若有向網(wǎng)絡(luò)G

中存在有方向的回路，則稱網(wǎng)絡(luò)G

中存在循環(huán)■若有向網(wǎng)絡(luò)G

中不存在有方向的回路，無論是否存在回路，圖論表示方式：有向網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》G8:

有向加權(quán)網(wǎng)絡(luò)■無權(quán)網(wǎng)絡(luò)：是在忽略網(wǎng)絡(luò)中不同節(jié)點(diǎn)間關(guān)系強(qiáng)弱差異

性的前提下，各節(jié)點(diǎn)連接有相同的連接強(qiáng)度的無向或

有向網(wǎng)絡(luò)■加權(quán)網(wǎng)絡(luò)：是在不能忽略網(wǎng)絡(luò)中不同節(jié)點(diǎn)間關(guān)系強(qiáng)弱

差異性的前提下，各節(jié)點(diǎn)連接有不同的連接強(qiáng)度的無

向或有向網(wǎng)絡(luò)■無權(quán)網(wǎng)絡(luò)是一種特殊的加權(quán)網(wǎng)絡(luò)。若兩節(jié)點(diǎn)間存在連

接，權(quán)重等于1;若兩節(jié)點(diǎn)間不存在連接，權(quán)重等于0■無向加權(quán)網(wǎng)絡(luò)分析是加權(quán)網(wǎng)絡(luò)分析的重點(diǎn)■R函

數(shù)

：is.weighted(graph=網(wǎng)絡(luò)類對象名)圖論表示：無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》圖論表示：1-模網(wǎng)絡(luò)和2-模網(wǎng)絡(luò)■模指網(wǎng)絡(luò)中節(jié)點(diǎn)的類型■若網(wǎng)絡(luò)中所有節(jié)點(diǎn)均屬于同一類型集合，該網(wǎng)絡(luò)稱

為1-模網(wǎng)絡(luò)■若網(wǎng)絡(luò)中節(jié)點(diǎn)分屬兩個(gè)不同的類型集合，該網(wǎng)絡(luò)稱

為2-模網(wǎng)絡(luò)G9:

完備的有向2-模網(wǎng)絡(luò)

G10:無向2-模網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》■R函數(shù)■grartite(n1=n,n2=m,directed=TRUE/FALSE,mode

=方向類型)■graph.bipartite(types=節(jié)點(diǎn)類型邏輯向量，

edges=連接，directed=TRUE/FALSE)圖論表示：1-模網(wǎng)絡(luò)和2-模網(wǎng)絡(luò)《R語言數(shù)據(jù)挖掘》網(wǎng)絡(luò)的矩陣表示■鄰接矩陣：Y是一個(gè)N×N的方陣，反映網(wǎng)絡(luò)中各節(jié)點(diǎn)

間的連接情況。行號和列號為各節(jié)點(diǎn)的索引編碼■無向網(wǎng)絡(luò)的鄰接矩陣：■若節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連接，則令矩陣中第i行第j列上的元素y,=1■若節(jié)點(diǎn)i和節(jié)點(diǎn)之間不存在連接，則令矩陣元素y,=0■有向網(wǎng)絡(luò)的鄰接矩陣：鄰接矩陣Y的列號代表頭節(jié)點(diǎn)

索引編碼，行號代表尾節(jié)點(diǎn)索引編碼■若節(jié)點(diǎn)和節(jié)點(diǎn)j之間存在有向連接，則令矩陣元素y;=1■若節(jié)點(diǎn)和節(jié)點(diǎn)j之間不存在有向連接，則令矩陣元素y;=0■有向圖的鄰接矩陣Y一般是非對稱的《R語言數(shù)據(jù)挖掘》■相關(guān)R函數(shù)■get.adjacency(graph=

網(wǎng)絡(luò)類對象名，type=

特征名，attr=

屬性名)網(wǎng)絡(luò)的矩陣表示《R語言數(shù)據(jù)挖掘》■關(guān)系矩陣也稱隸屬關(guān)系矩陣，用于反映2-模網(wǎng)絡(luò)中各

類節(jié)點(diǎn)間的連接情況■設(shè)2-模網(wǎng)絡(luò)中第一類節(jié)點(diǎn)個(gè)數(shù)為N?

,

第二類節(jié)點(diǎn)個(gè)數(shù)為節(jié)

點(diǎn)N?

。

關(guān)系矩陣B

是一個(gè)N?

×N?的矩陣，通常不是方陣■無向2-模網(wǎng)絡(luò)的關(guān)系矩陣：矩陣B的行列分別為兩類

節(jié)點(diǎn)的索引編號■有向2-模網(wǎng)絡(luò)的關(guān)系矩陣：矩陣B列號代表頭節(jié)點(diǎn)索

引編碼，行號代表尾節(jié)點(diǎn)索引編碼■相關(guān)R函數(shù)■get.incidence(graph=

網(wǎng)絡(luò)類對象名)關(guān)系矩陣表示《R語言數(shù)據(jù)挖掘》R建立網(wǎng)絡(luò)對象■利用鄰接矩陣建立網(wǎng)絡(luò)對象■

graph.adjacency(adjmatrix=鄰接矩陣名，mode=網(wǎng)絡(luò)類型

名，weighted=TURE/NULL)■示例■利用關(guān)系矩陣建立2-模網(wǎng)絡(luò)對象■graph.incidence(incidence=關(guān)系矩陣名

,directed=TRUE/FALSE,mode=方向類型,weighted=TURE/NULL)■示例《R語言數(shù)據(jù)挖掘》■利用連接列表建立網(wǎng)絡(luò)對象■

me(x=網(wǎng)絡(luò)類對象名，

what="edges")■grme(d=連接列表數(shù)據(jù)框，directed=TRUE/FALSE)

■示例R建立網(wǎng)絡(luò)對象《R語言數(shù)據(jù)挖掘》■網(wǎng)絡(luò)可視化的核心是以怎樣的外觀輪廓展示網(wǎng)絡(luò)，尤

其對較為龐大的網(wǎng)絡(luò)更為如此■合理安排網(wǎng)絡(luò)外觀輪廓的算法■

最小分割法：目的是最小化連接間的交叉數(shù)■最小空間法：基于幾何意義上的空間距離，令空間距離較

近的節(jié)點(diǎn)擺放在相鄰的位置上■譜分解法：依據(jù)節(jié)點(diǎn)的特征向量中心度安排節(jié)點(diǎn)的位置■樹形/層次法：根據(jù)節(jié)點(diǎn)間的連接將節(jié)點(diǎn)安排成樹形形狀，或組織成層次圖■算法體現(xiàn)在plot函數(shù)的layout

參數(shù)中R的網(wǎng)絡(luò)可視化《R語言數(shù)據(jù)挖掘》■節(jié)點(diǎn)重要性測度是網(wǎng)絡(luò)基本分析的第一個(gè)層次，目的

是刻畫節(jié)點(diǎn)個(gè)體與其他節(jié)點(diǎn)有怎樣“強(qiáng)度”的關(guān)系，

發(fā)現(xiàn)網(wǎng)絡(luò)中的重要節(jié)點(diǎn)■節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性一般表現(xiàn)■第一，它是網(wǎng)絡(luò)一個(gè)“局部范圍”內(nèi)的“中心”■第二，它是一個(gè)具有強(qiáng)連接的“樞紐”■涉及兩個(gè)基本測度■度■測地線距離網(wǎng)絡(luò)節(jié)點(diǎn)重要性的測度《R語言數(shù)據(jù)挖掘》■節(jié)點(diǎn)n

的度：指節(jié)點(diǎn)n有多少個(gè)與其直接連接的鄰居

節(jié)點(diǎn)■

無

向

網(wǎng)

絡(luò)

：d(n,)=v?=

∑,y?=v=

∑AVn■有向網(wǎng)絡(luò)：入度、出度d(n)=v+=∑

=Vn

d毗(n)=y+=∑

,yd(n)=dn(n;)+dm(n;)■相關(guān)R函數(shù)■degree(graph=網(wǎng)絡(luò)類對象名，v=節(jié)點(diǎn)對象，mode

=方向類

型

)■

graph.strength(graph=網(wǎng)絡(luò)類對象名，vids=節(jié)點(diǎn)對象，

mode

=方向類型)《R語言數(shù)據(jù)挖掘》度和相關(guān)R函數(shù)■最短路徑的距離，稱為節(jié)點(diǎn)n,和

n,間的測地線距離■節(jié)點(diǎn)n

和n,間可能存在多條不同的最短路徑■有向網(wǎng)絡(luò)需依方向游走，根據(jù)帶方向的最短路徑計(jì)算■測地線距離可基于鄰接矩陣計(jì)算得到■若網(wǎng)絡(luò)G具有連通性，網(wǎng)絡(luò)中所有節(jié)點(diǎn)對測地線距離

中的最大值，稱為網(wǎng)絡(luò)G的直徑■

相

關(guān)R函

數(shù)

：■shortest.paths(graph=網(wǎng)絡(luò)類對象名，v=起始節(jié)點(diǎn)對象，

to=

終止節(jié)點(diǎn)對象，mode=方向類型)■diameter(graph=網(wǎng)絡(luò)類對象名,directed=TRUE/FALSE,unconnected=TRUE/FALSE)測地線距離和相關(guān)R函數(shù)《R語言數(shù)據(jù)挖掘》■點(diǎn)度中心度等于0:節(jié)點(diǎn)n

是個(gè)“孤立”點(diǎn)，不于

其他任何節(jié)點(diǎn)相連，不可能是“局部范圍”內(nèi)的連

接“中心”,重要性很低■點(diǎn)度中心度越大說明節(jié)點(diǎn)n,越重要節(jié)點(diǎn)“中心”作用的測度可能度數(shù)之比■無向網(wǎng)絡(luò)：■有向網(wǎng)絡(luò)：■節(jié)點(diǎn)n

的點(diǎn)度中心度：為標(biāo)準(zhǔn)化度，度d(n)與其最大《R語言數(shù)據(jù)挖掘》■接近點(diǎn)度中心度越大，說明節(jié)點(diǎn)n

與所有其他節(jié)點(diǎn)的測地線距離之和越小，越可能成為幾何意義上的中心，節(jié)點(diǎn)n越重要節(jié)點(diǎn)“中心”作用的測度■節(jié)點(diǎn)n

的接近點(diǎn)度中心度《R語言數(shù)據(jù)挖掘》■相關(guān)R函數(shù)■degree(graph=網(wǎng)絡(luò)類對象名，v=節(jié)

點(diǎn)對象，mode=方向類型，normalized

=TRUE)■

closeness(graph=網(wǎng)絡(luò)類對象名

vids=

節(jié)點(diǎn)對象，mode=方向類

型，normalized=FALSE/TRUE)■計(jì)算點(diǎn)度中心度和接近中心度的必要性探討節(jié)點(diǎn)“中心”作用的測度《R語言數(shù)據(jù)挖掘》■中間中心度越大，表明必須經(jīng)過節(jié)點(diǎn)n

的最短路徑條數(shù)

越多，節(jié)點(diǎn)n的“樞紐”作用越強(qiáng)越重要■

標(biāo)準(zhǔn)化中間中心度：克服網(wǎng)絡(luò)規(guī)模對中間中心度結(jié)果的

影響■中間中心度■直觀上，若節(jié)點(diǎn)n是網(wǎng)絡(luò)的連接“樞紐”,則一定有很多

“線路”經(jīng)過n;。可依“路線”的多少測度節(jié)點(diǎn)“樞紐”節(jié)點(diǎn)“樞紐”作用的測度作用的高低《R語言數(shù)據(jù)挖掘》■

相

關(guān)R函

數(shù)■betweenness(graph=網(wǎng)絡(luò)類對象名，v=節(jié)點(diǎn)對象，

normalized

=FALSE/TRUE)■

edge.betweenness(graph=

網(wǎng)絡(luò)類對象名),可計(jì)算連接的

中間中心度節(jié)點(diǎn)“樞紐”作用的測度《R語言數(shù)據(jù)挖掘》■結(jié)構(gòu)洞■一個(gè)系統(tǒng)(網(wǎng)絡(luò))中，若某個(gè)成員(節(jié)點(diǎn))退出系統(tǒng)，使

得局部系統(tǒng)中的其他成員(節(jié)點(diǎn))間不再有任何聯(lián)系(連

接)。從結(jié)構(gòu)上看就像局部網(wǎng)絡(luò)中出現(xiàn)了一個(gè)關(guān)系斷裂的

“洞穴”,該成員稱為一個(gè)結(jié)構(gòu)洞■關(guān)節(jié)點(diǎn)■是那些若剔除網(wǎng)絡(luò)將導(dǎo)致網(wǎng)絡(luò)的組件數(shù)大大增加的節(jié)點(diǎn)。關(guān)節(jié)點(diǎn)不存在，網(wǎng)絡(luò)將變成兩個(gè)或多個(gè)互不連接的獨(dú)立子

網(wǎng)絡(luò)或單個(gè)“孤立”節(jié)點(diǎn)。關(guān)節(jié)點(diǎn)在構(gòu)成組件中起到了一

個(gè)“中樞”作用■相關(guān)R函數(shù)：articulation.points(graph=網(wǎng)絡(luò)類對象名)節(jié)點(diǎn)重要性的其他方面《R語言數(shù)據(jù)挖掘》■特征向量中心度：節(jié)點(diǎn)重要性的測度量■基本出發(fā)點(diǎn)是：如果節(jié)點(diǎn)n,較為重要，則節(jié)點(diǎn)n

應(yīng)

與其他重要節(jié)點(diǎn)有較多的連接節(jié)點(diǎn)重要性的其他方面■相關(guān)R函數(shù)■

evcent(graph=網(wǎng)絡(luò)類對象名，

scale

=TRUE/FALSE)《R語言數(shù)據(jù)挖掘》■PageRank得分■是S.Brin

和L.Page

于1998年提出的度量網(wǎng)絡(luò)節(jié)點(diǎn)

重要性的測度得分，也稱PageRank

算法，是Google搜索算法的基礎(chǔ)■相關(guān)R函數(shù)■page.rank(graph=網(wǎng)絡(luò)類對象名，

vids

=網(wǎng)絡(luò)節(jié)點(diǎn)，

directed=TRUE,damping=0.85)節(jié)點(diǎn)重要性的其他方面《R語言數(shù)據(jù)挖掘》■子群分析是網(wǎng)絡(luò)分析的第二個(gè)層次。它將研究范圍從

單個(gè)節(jié)點(diǎn)拓展到某些覆蓋多個(gè)節(jié)點(diǎn)的局部區(qū)域。這些

局部區(qū)域中節(jié)點(diǎn)間的關(guān)系更為密切或更特殊，成為相

對獨(dú)立的小群體，也稱子群。子群類型■二元關(guān)系，三元關(guān)系

■派系■k-核■子群分析的主要目標(biāo)是基于子群類型，找到網(wǎng)絡(luò)中包

含的各種子群和數(shù)量，并借助子群特點(diǎn)和所體現(xiàn)的局

部關(guān)系，細(xì)致刻畫網(wǎng)絡(luò)的結(jié)構(gòu)組成特征網(wǎng)絡(luò)子群構(gòu)成特征研究《R語言數(shù)據(jù)挖掘》■二元關(guān)系：通常針對有向網(wǎng)絡(luò)而言，是有向網(wǎng)絡(luò)中僅

涉及兩個(gè)節(jié)點(diǎn)的最小子群■節(jié)點(diǎn)n,和n,間的二元關(guān)系有三種狀態(tài)■第一，y,=y,=1■

第

二

，y,=1且y,=0(

或y,=0且y,=1■

第

三

，y;=y;=0■網(wǎng)絡(luò)中各種二元關(guān)系狀態(tài)的數(shù)量稱為二元關(guān)系

普查量二元關(guān)系和三元關(guān)系《R語言數(shù)據(jù)挖掘》1:均無連接2:A→B,C?AC3:A→B.CAB4:A←B→CAB

C5:A→B←C?B

C

?6:A→B→CB

C?7:A→B←CAB

C8:A→B→CA)B

C

?9:A→B←C.A→C?AB

C

?10:A←B←C.A→C?AB

C

e11:A→B→CA)B

C12:A←B→C.A→C?AB

C

?13:A→B←C.A→C?AB

c14:A→B→C.A→CAB

C?15:A→B→C.A→CAB

C16:A→B→C.A?CAB二元關(guān)系和三元關(guān)系■三元關(guān)系：體現(xiàn)了關(guān)系的傳遞性和循環(huán)性表11.1三元關(guān)系的16種情況《R語言數(shù)據(jù)挖掘》??■相關(guān)R函數(shù)■dyad.census(graph=網(wǎng)絡(luò)類對象名)■triad.census(graph=網(wǎng)絡(luò)類對象名)二元關(guān)系和三元關(guān)系《R語言數(shù)據(jù)挖掘》派系和k-核■派系：若網(wǎng)絡(luò)G

中的一個(gè)組件G’是完備的，且不被其

他的完備組件所包含，則稱G’為網(wǎng)絡(luò)G

的一個(gè)派系■派系是一個(gè)局部意義上的最大完備子網(wǎng)絡(luò)■相關(guān)R函數(shù)■maximal.cliques(graph=網(wǎng)絡(luò)類對象名，min=n1,max=

n2)■

largest.cliques(graph=網(wǎng)絡(luò)類對象名)《R語言數(shù)據(jù)挖掘》派系和k-核■k-核：派系若G’是網(wǎng)絡(luò)G

的一個(gè)最大連通性子圖，且

G’中的每個(gè)節(jié)點(diǎn)均至少與其他k個(gè)節(jié)點(diǎn)直接連接，即G'

中每個(gè)節(jié)點(diǎn)的度均大于等于k,則稱G’是網(wǎng)絡(luò)G

的一個(gè)

k-核■節(jié)點(diǎn)n

的核等于m

如果它屬于m-核但不屬于(m+1)-

核■只要節(jié)點(diǎn)n

不是“孤立”點(diǎn)，它至少是一個(gè)1-核成員，

也可能屬于更大的核■相關(guān)R函

數(shù)■graph.coreness(graph=網(wǎng)絡(luò)類對象名，mode=方向類型)《R語言數(shù)據(jù)挖掘》社

區(qū)

和

組

件■社區(qū)也稱模塊：是一個(gè)子網(wǎng)絡(luò)，特點(diǎn)是子網(wǎng)絡(luò)內(nèi)部各

結(jié)點(diǎn)的連接相對緊密，子網(wǎng)絡(luò)之間的連接相對稀疏■社區(qū)結(jié)構(gòu)劃分算法■基于劃分的方法■模塊度方法■隨機(jī)游走方法■

密度子圖方法■相關(guān)R函數(shù)■模塊度《R語言數(shù)據(jù)挖掘》■組件作為最大連通性子網(wǎng)絡(luò)，其凝聚程度可能低于派

系等，但因“對外”沒有連接而具有強(qiáng)獨(dú)立性■相關(guān)R函數(shù)■clusters(graph=網(wǎng)絡(luò)類對象名，

mode=組件類型)■

decompose.graph(graph=網(wǎng)絡(luò)類對象名，

mode=組件類型)社

區(qū)

和

組

件《R語言數(shù)據(jù)挖掘》網(wǎng)絡(luò)整體特征刻畫■網(wǎng)絡(luò)整體特征的刻畫是網(wǎng)絡(luò)分析的最高層次，目的是

從全局角度揭示網(wǎng)絡(luò)的整體樣貌。

一般有兩種方式：■第一，利用關(guān)于網(wǎng)絡(luò)整體特征的測度■第二，通過各種分布刻畫■網(wǎng)絡(luò)整體特征的測度主要有■網(wǎng)絡(luò)密度■平均測地線距離■網(wǎng)絡(luò)聚類系數(shù)■

譜半徑《R語言數(shù)據(jù)挖掘》網(wǎng)絡(luò)密度■網(wǎng)絡(luò)密度是網(wǎng)絡(luò)分析中常用的一種度量全局網(wǎng)絡(luò)特征

的測度量■從連接個(gè)數(shù)的角度測度網(wǎng)絡(luò)節(jié)點(diǎn)間的密集程度■當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)N確定后，節(jié)點(diǎn)之間的連接線越多，

表明該圖的密度越大■相關(guān)R函數(shù)■graph.density(graph=

網(wǎng)絡(luò)類對象名)《R語言數(shù)據(jù)挖掘》■平均測地線距離也是刻畫網(wǎng)絡(luò)整體特征的常用測度■從幾何距離的角度測度節(jié)點(diǎn)連接的緊密程度，有與

網(wǎng)絡(luò)直徑類似的意義，但更具穩(wěn)健性■平均測地線距離是各個(gè)節(jié)點(diǎn)測地線距離的均值■該值越大表明網(wǎng)絡(luò)整體的“覆蓋”區(qū)域越大，網(wǎng)絡(luò)

節(jié)點(diǎn)連接的密集程度較低。反之，網(wǎng)絡(luò)節(jié)點(diǎn)連接的

密集程度較高■相關(guān)R函數(shù)■avergth(graph=

網(wǎng)絡(luò)類對象名

,directed=TRUE/FALSE)平均測地線距離《R語言數(shù)據(jù)挖掘》■還可定義為以節(jié)點(diǎn)連接三方組頻率為權(quán)重的節(jié)點(diǎn)聚

類系數(shù)的加權(quán)平均■相關(guān)R函數(shù)■

transitivity(graph=網(wǎng)絡(luò)類對象名，

type=類型名)網(wǎng)絡(luò)聚類系數(shù)■節(jié)點(diǎn)n,聚類系數(shù)用于測度節(jié)點(diǎn)n

的聚類能力■可定義為所有節(jié)點(diǎn)聚類系數(shù)的簡單平均■網(wǎng)絡(luò)聚類系數(shù)《R語言數(shù)據(jù)挖掘》譜

半

徑■網(wǎng)絡(luò)的譜半徑也是度量網(wǎng)絡(luò)整體連接程度的測度量■

譜半徑是網(wǎng)絡(luò)鄰接矩陣Y的最大非零特征值■譜半徑在兼顧拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上測度網(wǎng)絡(luò)的整體連

接程度，更適用于不同網(wǎng)絡(luò)間的對比■譜半徑越大，網(wǎng)絡(luò)的整體連接程度越高■相關(guān)R函數(shù)■

evcent(graph=網(wǎng)絡(luò)類對象名，scale

=TRUE/FALSE)《R語言數(shù)據(jù)挖掘》■度的熵越大，度取值的平均不確定性越大，反之，度取值

的平均不確定性越小■網(wǎng)絡(luò)分析中，度的熵也稱為網(wǎng)絡(luò)熵■相關(guān)R函數(shù)■entropy(y=頻數(shù)分布，method="ML",unit="log2")■刻畫網(wǎng)絡(luò)整體特征更細(xì)致的方式是分布，如：■網(wǎng)絡(luò)的節(jié)點(diǎn)度分布、點(diǎn)度中心度分布、中間中心度分布、

測度線距離分布，等■

網(wǎng)絡(luò)分析中研究最多的分布是度分布網(wǎng)絡(luò)特征的各種分布和度量■度分布特征的度量■度的熵《R語言數(shù)據(jù)挖掘》■網(wǎng)絡(luò)科學(xué)研究中，依據(jù)度分布將眾多網(wǎng)絡(luò)劃分成四種類

型

：■規(guī)則網(wǎng)絡(luò)■小世界網(wǎng)絡(luò)■無標(biāo)度網(wǎng)絡(luò)■隨機(jī)網(wǎng)絡(luò)■不同網(wǎng)絡(luò)類型的主要差異在于：■網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)n,和n,間具有連接是確定性的

還是是隨機(jī)性的■確定性和隨機(jī)性的不同程度的混合主要網(wǎng)絡(luò)類型及特點(diǎn)《R語言數(shù)據(jù)挖掘》■規(guī)則網(wǎng)絡(luò)是指網(wǎng)絡(luò)中任意兩個(gè)節(jié)

點(diǎn)n,和

n;間■具有連接是確定性的■連接的規(guī)律性導(dǎo)致規(guī)則網(wǎng)絡(luò)的

拓?fù)浣Y(jié)構(gòu)往往具有特定的“形

態(tài)”■k-規(guī)則網(wǎng)絡(luò)：典型的規(guī)則網(wǎng)絡(luò)■所謂k-規(guī)則網(wǎng)絡(luò)是指網(wǎng)絡(luò)中的

每個(gè)節(jié)點(diǎn)均與k(k≤N—1,N

為

節(jié)點(diǎn)個(gè)數(shù))個(gè)節(jié)點(diǎn)存在直接連

接的網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò)及特點(diǎn)《R語言數(shù)據(jù)挖掘》平均測地線距離1.33平均測地線距離1.11平均測地線距離平均測地線距離平均測地線距離平均測地線距離平均測地線距離平均測地線距離2.78■

星形網(wǎng)絡(luò)：規(guī)則網(wǎng)絡(luò)■有N-1

個(gè)節(jié)點(diǎn)均與剩下的一個(gè)節(jié)點(diǎn)n,直接相連，它

們的節(jié)點(diǎn)度均等于1,節(jié)點(diǎn)n,的度等于N—1■平衡2-叉樹網(wǎng)絡(luò)：規(guī)則網(wǎng)絡(luò)■除葉節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，共有N

-1條連接。根節(jié)點(diǎn)的度等于2,葉節(jié)點(diǎn)的度等于1,

其余節(jié)點(diǎn)的度都等于3,節(jié)點(diǎn)度只可能取1,2,3規(guī)則網(wǎng)絡(luò)及特點(diǎn)■相關(guān)R函數(shù)■graph.star■graph.tree星形網(wǎng)絡(luò)平均測地線距離1.8《R語言數(shù)據(jù)挖掘》2-叉樹網(wǎng)絡(luò)平均測地線距離3.5■大規(guī)模隨機(jī)網(wǎng)絡(luò)的最大特點(diǎn)■

節(jié)點(diǎn)的度分布服從泊松分布■網(wǎng)絡(luò)熵隨網(wǎng)絡(luò)密度的增加呈非線性變化■網(wǎng)絡(luò)密度為0.5的隨機(jī)網(wǎng)絡(luò)具有最大的網(wǎng)絡(luò)熵■

將包含N個(gè)節(jié)點(diǎn)和E條連接的隨機(jī)網(wǎng)絡(luò)看做是，包含N個(gè)節(jié)點(diǎn)的

空網(wǎng)絡(luò)隨時(shí)間t=0,1,2,…E推移逐步演變的結(jié)果。每個(gè)時(shí)刻t均

在上個(gè)時(shí)刻t—1的基礎(chǔ)上隨機(jī)挑選一對節(jié)點(diǎn)并在其間增加一條

連接，經(jīng)過E步直到添加E條連接為止■該規(guī)則是E.N.Gilbert提出的，網(wǎng)絡(luò)稱為Gilbert隨機(jī)網(wǎng)絡(luò)■相關(guān)R函數(shù)■ere(n=節(jié)點(diǎn)數(shù)，p.or.m=概率或連接數(shù)，type=類型名)隨機(jī)網(wǎng)絡(luò)及特點(diǎn)《R