前情回顧：
Gephi網(wǎng)絡(luò)圖極簡(jiǎn)教程
Network在單細(xì)胞轉(zhuǎn)錄組數(shù)據(jù)分析中的應(yīng)用
網(wǎng)絡(luò)數(shù)據(jù)統(tǒng)計(jì)分析筆記|| 為什么研究網(wǎng)絡(luò)
網(wǎng)絡(luò)數(shù)據(jù)統(tǒng)計(jì)分析筆記|| 操作網(wǎng)絡(luò)數(shù)據(jù)
網(wǎng)絡(luò)數(shù)據(jù)統(tǒng)計(jì)分析筆記|| 網(wǎng)絡(luò)數(shù)據(jù)可視化
前面的幾節(jié)的內(nèi)容基本是在講如何構(gòu)建一個(gè)圖，接下來(lái)我們看看拿到圖之后可以做哪些分析。當(dāng)我們提到圖時(shí)，腦海中反應(yīng)的是一張網(wǎng)。要仔細(xì)描述清楚網(wǎng)的特點(diǎn)就需要一些術(shù)語(yǔ)，就像我們描述一組數(shù)據(jù)會(huì)用到平均值和標(biāo)準(zhǔn)差一樣。網(wǎng)絡(luò)數(shù)據(jù)的描述分析的目的是把圖講清楚，這就需要一套統(tǒng)計(jì)量。
網(wǎng)絡(luò)數(shù)據(jù)的描述分析過(guò)程是網(wǎng)絡(luò)的特征化過(guò)程。
- 節(jié)點(diǎn)和邊的特征
- 網(wǎng)絡(luò)的凝聚性度量
- 社團(tuán)發(fā)現(xiàn)
- 同配性與混合
節(jié)點(diǎn)和邊的特征
網(wǎng)絡(luò)圖中最基本的元素是節(jié)點(diǎn)和邊。首先我們需要的就是對(duì)他們的度量。我們之前介紹過(guò)節(jié)點(diǎn)度（degree）的概念：節(jié)點(diǎn)鏈接邊的數(shù)量。節(jié)點(diǎn)的強(qiáng)度（strength）是指于該節(jié)點(diǎn)所連邊的權(quán)重之和。
library(sand)
data(karate)
degree(karate)
Mr Hi Actor 2 Actor 3 Actor 4 Actor 5 Actor 6 Actor 7 Actor 8 Actor 9 Actor 10 Actor 11
16 9 10 6 3 4 4 4 5 2 3
Actor 12 Actor 13 Actor 14 Actor 15 Actor 16 Actor 17 Actor 18 Actor 19 Actor 20 Actor 21 Actor 22
1 2 5 2 2 2 2 2 3 2 2
Actor 23 Actor 24 Actor 25 Actor 26 Actor 27 Actor 28 Actor 29 Actor 30 Actor 31 Actor 32 Actor 33
2 5 3 3 2 4 3 4 4 6 12
John A
17
strength(karate)
Mr Hi Actor 2 Actor 3 Actor 4 Actor 5 Actor 6 Actor 7 Actor 8 Actor 9 Actor 10 Actor 11
42 29 33 18 8 14 13 13 17 3 8
Actor 12 Actor 13 Actor 14 Actor 15 Actor 16 Actor 17 Actor 18 Actor 19 Actor 20 Actor 21 Actor 22
3 4 17 5 7 6 3 3 5 4 4
Actor 23 Actor 24 Actor 25 Actor 26 Actor 27 Actor 28 Actor 29 Actor 30 Actor 31 Actor 32 Actor 33
5 21 7 14 6 13 6 13 11 21 38
John A
48
hist(degree(karate), col="lightblue", xlim=c(0,50),
xlab="Vertex Degree", ylab="Frequency", main="",breaks = 50)
# CHUNK 2
hist(strength(karate), col="pink",
xlab="Vertex Strength", ylab="Frequency", main="")
不同的數(shù)據(jù)集有不同的度分布情況，如酵母蛋白的互作網(wǎng)絡(luò)：
library(igraphdata)
data(yeast)
yeast
IGRAPH 65c41bb UN-- 2617 11855 -- Yeast protein interactions, von Mering et al.
+ attr: name (g/c), Citation (g/c), Author (g/c), URL (g/c), Classes (g/x), name (v/c), Class
| (v/c), Description (v/c), Confidence (e/c)
+ edges from 65c41bb (vertex names):
[1] YLR197W--YDL014W YOR039W--YOR061W YDR473C--YPR178W YOR332W--YLR447C YER090W--YKL211C YDR394W--YGR232W
[7] YER021W--YPR108W YPR029C--YKL135C YIL106W--YGR092W YKL166C--YIL033C YGL026C--YKL211C YOR061W--YGL019W
[13] YGL115W--YER027C YGL049C--YGR162W YDR394W--YOR117W YDL140C--YML010W YLR291C--YKR026C YGR158C--YDL111C
[19] YDR328C--YDL132W YOL094C--YNL290W YDR460W--YPR025C YBR154C--YOR341W YBR154C--YOR116C YIL062C--YKL013C
[25] YBR154C--YOR207C YBR154C--YPR010C YER027C--YDR477W YLR291C--YGR083C YPL093W--YDR496C YER006W--YMR049C
[31] YER006W--YMR290C YFR052W--YHR200W YOR261C--YFR004W YHR052W--YDR496C YDL140C--YBR154C YDR394W--YOR259C
[37] YDR280W--YGR195W YOR260W--YDR211W YMR193W--YML009C YGR162W--YOL139C YPR187W--YPR110C YPL093W--YDR101C
+ ... omitted several edges
ecount(yeast) #邊數(shù)量
[1] 11855
vcount(yeast) # 節(jié)點(diǎn)數(shù)
[1] 2617
d.yeast <- degree(yeast)
head(d.yeast)
YLR197W YOR039W YDR473C YOR332W YER090W YDR394W
40 19 9 13 21 37
hist(d.yeast,col="blue",
xlab="Degree", ylab="Frequency",
main="Degree Distribution")
考慮到分布遞減的趨勢(shì)，雙對(duì)數(shù)坐標(biāo)在表達(dá)度的信息時(shí)更為有效。
dd.yeast <- degree_distribution(yeast)
head(dd.yeast)
[1] 0.00000000 0.26518915 0.12877340 0.09247230 0.06763470 0.05502484
d <- 1:max(d.yeast)-1
ind <- (dd.yeast != 0)
plot(d[ind], dd.yeast[ind], log="xy", col="blue",
xlab=c("Log-Degree"), ylab=c("Log-Intensity"),
main="Log-Log Degree Distribution")
可以計(jì)算下降的速率，來(lái)反映度指數(shù)（degree exponent）。
衡量節(jié)點(diǎn)以何種方式彼此連接的方式，用節(jié)點(diǎn)鄰居的平均度（Average nearest neighbor degree）。
a.nn.deg.yeast <- knn(yeast,V(yeast))$knn
plot(d.yeast, a.nn.deg.yeast, log="xy",
col="goldenrod", xlab=c("Log Vertex Degree"),
ylab=c("Log Average Neighbor Degree"))
節(jié)點(diǎn)中心性
關(guān)于圖節(jié)點(diǎn)的問(wèn)題很多，本質(zhì)上都是在試圖理解他在網(wǎng)絡(luò)中的重要性。度量中心性（centrality）正是為了量化重要性。節(jié)點(diǎn)中心性度量有：節(jié)點(diǎn)度中心性、接近中心性、介數(shù)中心性以及特征向量中心性
節(jié)點(diǎn)度中心性（Degree centrality）
在一個(gè)網(wǎng)絡(luò)圖G=(V,E)中，節(jié)點(diǎn)v的度指的是與v相連的E中邊的數(shù)量。接近中心性（closeness centrality）
接近中心性主要用于計(jì)算每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離之和。然后將得到的和反過(guò)來(lái)確定該節(jié)點(diǎn)的接近中心性得分。原生的接近中心性計(jì)算方式如下：
- 介數(shù)中心性（betweenness centrality）
度量試圖概括的是某個(gè)節(jié)點(diǎn)在多大程度上“介于”（between）其他節(jié)點(diǎn)對(duì)之間。節(jié)點(diǎn)的“重要性”與其再網(wǎng)絡(luò)路徑中的位置有關(guān)。
- 特征向量中心性（eigenvector centrality）
特征向量中心性的基本思想是，一個(gè)節(jié)點(diǎn)的中心性是相鄰節(jié)點(diǎn)中心性的函數(shù)。也就是說(shuō)，與你連接的人越重要，你也就越重要。
特征向量中心性和點(diǎn)度中心性不同，一個(gè)點(diǎn)度中心性高即擁有很多連接的節(jié)點(diǎn)特征向量中心性不一定高，因?yàn)樗械倪B接者有可能特征向量中心性很低。同理，特征向量中心性高并不意味著它的點(diǎn)度中心性高，它擁有很少但很重要的連接者也可以擁有高特征向量中心性。
簡(jiǎn)而言之：
點(diǎn)度中心性：一個(gè)人的社會(huì)關(guān)系越多，他/她就越重要
中介中心性：如果一個(gè)成員處于其他成員的多條最短路徑上，那么該成員就是核心成員
接近中心性：一個(gè)人跟所有其他成員的距離越近，他/她就越重要
特征向量中心性：與你連接的人社會(huì)關(guān)系越多，你就越重要
展示節(jié)點(diǎn)中心性的一種直觀方式是使用輻射布局?？帐值谰銟?lè)部網(wǎng)絡(luò)中心性描述，可以看出主管和教練處于中心位置。
A <- as_adjacency_matrix(karate, sparse=FALSE)
library(network)
g <- network::as.network.matrix(A)
library(sna)
sna::gplot.target(g, degree(g,gmode="graph"),
main="Degree", circ.lab = FALSE,
circ.col="skyblue", usearrows = FALSE,
vertex.col=c("blue", rep("red", 32), "yellow"),
edge.col="darkgray")
library(CINNA)
visualize_graph( karate, centrality.type="Markov Centrality")
CINNA是一個(gè)提交到CRAN資源庫(kù)的R包，是為網(wǎng)絡(luò)科學(xué)中的中心性分析而編寫(xiě)的。該方法可用于多種中心性測(cè)度的組合、比較、評(píng)價(jià)和可視化。
proper_centralities(karate)
[1] "subgraph centrality scores" "Topological Coefficient"
[3] "Average Distance" "Barycenter Centrality"
[5] "BottleNeck Centrality" "Centroid value"
[7] "Closeness Centrality (Freeman)" "ClusterRank"
[9] "Decay Centrality" "Degree Centrality"
[11] "Diffusion Degree" "DMNC - Density of Maximum Neighborhood Component"
[13] "Eccentricity Centrality" "Harary Centrality"
[15] "eigenvector centralities" "K-core Decomposition"
[17] "Geodesic K-Path Centrality" "Katz Centrality (Katz Status Index)"
[19] "Kleinberg's authority centrality scores" "Kleinberg's hub centrality scores"
[21] "clustering coefficient" "Lin Centrality"
[23] "Lobby Index (Centrality)" "Markov Centrality"
[25] "Radiality Centrality" "Shortest-Paths Betweenness Centrality"
[27] "Current-Flow Closeness Centrality" "Closeness centrality (Latora)"
[29] "Communicability Betweenness Centrality" "Community Centrality"
[31] "Cross-Clique Connectivity" "Entropy Centrality"
[33] "EPC - Edge Percolated Component" "Laplacian Centrality"
[35] "Leverage Centrality" "MNC - Maximum Neighborhood Component"
[37] "Hubbell Index" "Semi Local Centrality"
[39] "Closeness Vitality" "Residual Closeness Centrality"
[41] "Stress Centrality" "Load Centrality"
[43] "Flow Betweenness Centrality" "Information Centrality"
[45] "Dangalchev Closeness Centrality" "Group Centrality"
[47] "Harmonic Centrality" "Local Bridging Centrality"
[49] "Wiener Index Centrality" "Weighted Vertex Degree"
sna::gplot.target(g, closeness(g,gmode="graph"),
main="Degree", circ.lab = FALSE,
circ.col="skyblue", usearrows = FALSE,
vertex.col=c("blue", rep("red", 32), "yellow"), # 顏色與節(jié)點(diǎn)對(duì)應(yīng)
edge.col="darkgray")
sna::gplot.target(g, betweenness(g,gmode="graph"),
main="Degree", circ.lab = FALSE,
circ.col="skyblue", usearrows = FALSE,
vertex.col=c("blue", rep("red", 32), "yellow"),
edge.col="darkgray")
sna::gplot.target(g, evcent(g),
main="Degree", circ.lab = FALSE,
circ.col="skyblue", usearrows = FALSE,
vertex.col=c("blue", rep("red", 32), "yellow"),
edge.col="darkgray")
在有向圖中，節(jié)點(diǎn)的中心性用樞紐hub與權(quán)威authority來(lái)描述。有名的算法是HIST。1999年，Jon Kleinberg 提出了HITS算法。作為幾乎是與PageRank同一時(shí)期被提出的算法，HITS同樣以更精確的搜索為目的，并到今天仍然是一個(gè)優(yōu)秀的算法。
HITS算法的全稱(chēng)是Hyperlink-Induced Topic Search。在HITS算法中，每個(gè)節(jié)點(diǎn)被賦予兩個(gè)屬性：hub屬性和authority屬性。同時(shí)，節(jié)點(diǎn)被分為兩種：hub節(jié)點(diǎn)和authority節(jié)點(diǎn)。hub，中心的意思，所以hub節(jié)點(diǎn)指那些包含了很多指向authority節(jié)點(diǎn)的鏈接的節(jié)點(diǎn)。
# CHUNK 10
par(mfrow = c(1,2))
l <- layout_with_kk(aidsblog)
plot(aidsblog, layout=l, main="Hubs", vertex.label="",
vertex.size=10 * sqrt(hub_score(aidsblog)$vector))
plot(aidsblog, layout=l, main="Authorities",
vertex.label="", vertex.size=10 *
sqrt(authority_score(aidsblog)$vector))
邊的特征
同樣地，我們會(huì)問(wèn)在網(wǎng)絡(luò)中哪條邊是比較重要的呢？邊也可以用中心性的指標(biāo)進(jìn)行度量。
> eb <- edge_betweenness(karate)
> E(karate)[order(eb, decreasing=T)[1:3]]
+ 3/78 edges from 4b458a1 (vertex names):
[1] Actor 20--John A
Mr Hi --Actor 20
Mr Hi --Actor 32
網(wǎng)絡(luò)圖的凝聚性特征
網(wǎng)絡(luò)圖的凝聚性，是為了描述這樣一種性質(zhì)，即網(wǎng)絡(luò)圖中節(jié)點(diǎn)的子集與相應(yīng)的邊以何種程度凝聚在一起。在網(wǎng)絡(luò)工作中，許多問(wèn)題歸結(jié)為涉及網(wǎng)絡(luò)工作內(nèi)聚性的問(wèn)題，即頂點(diǎn)的子集在多大程度上內(nèi)聚(形象來(lái)說(shuō)，就是粘在一起)。在社交網(wǎng)絡(luò)中，你的朋友的朋友是否彼此之間也會(huì)成為朋友呢？細(xì)胞內(nèi)的蛋白質(zhì)集合是如何緊密結(jié)合在一起的？萬(wàn)維網(wǎng)的頁(yè)面結(jié)構(gòu)是否傾向于區(qū)分不同類(lèi)型的內(nèi)容？一個(gè)互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)的那一部分似乎構(gòu)成了’主干’。
“凝聚性”節(jié)點(diǎn)子集一般指這樣的節(jié)點(diǎn)集合：
（1）內(nèi)部聯(lián)系緊密，
（2）與其它節(jié)點(diǎn)相對(duì)分離。
更正式地說(shuō)，圖分割算法通常試圖尋找圖G=(V,E)中節(jié)點(diǎn)集V的一個(gè)分割?={C1,…,CK}，使得連接Ck與Ck’之中節(jié)點(diǎn)的邊集合E(Ck,Ck’)規(guī)模相對(duì)較小，而連接Ck內(nèi)部節(jié)點(diǎn)的邊集合E(Ck)=E(Ck,Ck)規(guī)模較大。
分割后的產(chǎn)生的各部分子圖也常被稱(chēng)為“模塊”（Module），各模塊也常視為一種“子圖”類(lèi)型用于描述問(wèn)題。
描述網(wǎng)絡(luò)凝聚性的一種方法是規(guī)定某種感興趣的子圖類(lèi)型，一個(gè)典型的例子是團(tuán)。團(tuán)是一類(lèi)完全子圖，集合內(nèi)所有節(jié)點(diǎn)都由邊相互連接，因而是完全凝聚的節(jié)點(diǎn)子集。所有尺寸的團(tuán)的普查（census）可以提供一個(gè)“快照”，幫助了解圖的結(jié)構(gòu)。不過(guò)經(jīng)常存在冗余問(wèn)題，即大尺寸的團(tuán)包含了小尺寸的團(tuán)?！皹O大團(tuán)”（maximal clique）是不被任何更大的團(tuán)包含的一類(lèi)圖團(tuán)。實(shí)際上，大尺寸的團(tuán)很稀少，團(tuán)的存在要求圖G本身相當(dāng)稠密，但現(xiàn)實(shí)世界的網(wǎng)絡(luò)多是稀疏的。
團(tuán)的概念存在各種弱化了條件的版本。例如，圖G的k核（k-core）是一個(gè)圖G的子圖，其中所有節(jié)點(diǎn)的度至少為k，且不被包含于滿(mǎn)足條件的其它子圖中（即它是滿(mǎn)足條件的最大的子圖）。核的概念在可視化中非常流行，因?yàn)樗峁┝艘环N將網(wǎng)絡(luò)分解到類(lèi)似洋蔥的不同“層”（layer）的方法。這種分解可以與輻射布局有效地結(jié)合起來(lái)。
在團(tuán)及其變體之外，有一些其他類(lèi)型子圖可以用于定義網(wǎng)絡(luò)凝聚性。二元組（dyad）和三元組（triad）是兩個(gè)基本的量（Davis and Leinhardt, 1967; Holland and Leinhardt, 1970）。二元組關(guān)注兩個(gè)節(jié)點(diǎn)，它們?cè)谟邢驁D中有三種可能的狀態(tài)：空（null，不存在邊）、非對(duì)稱(chēng)（asymmetric，存在一條有向邊）、雙向（mutual，兩條有向邊）。類(lèi)似地，三元組是三個(gè)節(jié)點(diǎn)，共有16種可能的狀態(tài)（圖下所示）。對(duì)圖G中每個(gè)狀態(tài)觀察到的次數(shù)進(jìn)行統(tǒng)計(jì)，得到的是這兩類(lèi)子圖可能狀態(tài)的一個(gè)普查，可以幫助深入理解圖中連接的本質(zhì)。
par(mfrow = c(1,2))
table(sapply(cliques(karate), length)) # 團(tuán)的普查
1 2 3 4 5
34 78 45 11 2
##子圖與普查
#所有尺寸的團(tuán)的普查可以提供一個(gè)快照，將顯示各尺寸的團(tuán)的數(shù)量
census <- table(sapply(cliques(karate), length))
census
plot(census)
cliques(karate)[sapply(cliques(karate), length) == 5]
[[1]]
+ 5/34 vertices, named, from 4b458a1:
[1] Mr Hi Actor 2 Actor 3 Actor 4 Actor 14
[[2]]
+ 5/34 vertices, named, from 4b458a1:
[1] Mr Hi Actor 2 Actor 3 Actor 4 Actor 8
clique_num(yeast) # 團(tuán)的數(shù)量
[1] 23
cores <- coreness(karate) # 核
sna::gplot.target(g, cores, circ.lab = FALSE,
circ.col="skyblue", usearrows = FALSE,
vertex.col=cores, edge.col="darkgray")
# CHUNK 17
aidsblog <- simplify(aidsblog)
dyad_census(aidsblog)
$mut
[1] 3
$asym
[1] 177
$null
[1] 10405
密度與相對(duì)密度
一個(gè)圖的“密度”（density）是指實(shí)際出現(xiàn)的邊與可能的邊的頻數(shù)之比，反映了網(wǎng)絡(luò)的凝聚性特征。例如，對(duì)于不存在自環(huán)和多重邊的（無(wú)向）圖G，子圖H=(VH,EH)的密度為：
den(H)的值處于0到1之間，提供了一種H與團(tuán)的接近程度的度量。由于子圖H可以自由選擇，這使簡(jiǎn)單的密度概念變得很有趣。例如，令H=G，得到的是整個(gè)圖G的密度；而令H=Hv為節(jié)點(diǎn)v∈V的鄰居集合以及節(jié)點(diǎn)間的邊，度量的是v直接相鄰鄰居的密度。
detach("package:sna")
detach("package:network")
ego.instr <- induced_subgraph(karate,
neighborhood(karate, 1, 1)[[1]])
ego.admin <- induced_subgraph(karate,
neighborhood(karate, 1, 34)[[1]])
edge_density(karate)
0.1390374
edge_density(ego.instr)
[1] 0.25
edge_density(ego.admin)
[1] 0.2091503
相對(duì)頻率也可以用于定義圖中的“聚集性”（clustering）概念，反映了網(wǎng)絡(luò)的凝聚性特征。例如，術(shù)語(yǔ)“聚類(lèi)系數(shù)”（clustering coefficient）的標(biāo)準(zhǔn)定義如下：
其中，τ? (G)指的是圖G中三角形個(gè)數(shù)（三角形指尺寸為3的團(tuán)），而τ3 (G)是連通的三元組（即由兩條邊連接的三個(gè)節(jié)點(diǎn)，有時(shí)也稱(chēng)為2-星，2-star）個(gè)數(shù)。clT (G)的值也被稱(chēng)為圖的“傳遞性”（transitivity）。表示“傳遞性三元組的比例”。
注意，clT (G)是對(duì)全局聚集性的度量，所概括的是聯(lián)通三元組閉合形成三角形的相對(duì)頻率。
transitivity(karate)
[1] 0.2556818
transitivity(karate, "local", vids=c(1,34))
[1] 0.1500000 0.1102941
有向圖中獨(dú)有的一個(gè)概念是“互惠性”（reciprocity），即有向網(wǎng)絡(luò)中的邊多大程度上是互惠的。計(jì)算相對(duì)頻率的單位可以是二元組或者有向邊，對(duì)應(yīng)有兩種表示這一概念的方法。當(dāng)采用二元組作為基本單位，互惠性被定義為有互惠（雙向）有向邊的二元組數(shù)量，除以只有單一非互惠的二元組數(shù)量。另一種情況下，互惠性定義為互惠邊的總數(shù)除以所有邊的數(shù)量。
reciprocity(aidsblog, mode="default")
# ---
## [1] 0.03278689
# ---
reciprocity(aidsblog, mode="ratio")
# ---
## [1] 0.01666667
# ---
連通性與圖分割與圖流
若圖G中存在從節(jié)點(diǎn)u到另一個(gè)節(jié)點(diǎn)v的一條通路，則可以稱(chēng)節(jié)點(diǎn)v從u是“可達(dá)的”（reachable）。若所有節(jié)點(diǎn)從任一其他節(jié)點(diǎn)均可達(dá)，則稱(chēng)圖G為“連通的”（connected）。圖的“組件”（component）是一個(gè)最大化的連通子圖，即它是圖G的一個(gè)連通子圖，且任意增加V中的一個(gè)剩余節(jié)點(diǎn)時(shí)都會(huì)破壞連通性。
is_connected(yeast)
# ---
## [1] FALSE
# ---
普查尋找組件
comps <- decompose(yeast)
table(sapply(comps, vcount))
2 3 4 5 6 7 2375
63 13 5 6 1 3 1
其中組件1 大約占到90%的節(jié)點(diǎn)，一般現(xiàn)實(shí)組件都發(fā)現(xiàn)了小世界的特性。小世界（small world）網(wǎng)絡(luò)模型將晶格模型的可傳遞性與隨機(jī)網(wǎng)絡(luò)模型的低路徑長(zhǎng)度結(jié)合在一起，其由一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的圖出發(fā)，對(duì)一小部分邊進(jìn)行隨機(jī)重連（rewiring）（Watts and Strogatz, 1998）。具體而言，從排成一圈的Nv個(gè)節(jié)點(diǎn)的集合開(kāi)始，將每個(gè)節(jié)點(diǎn)與其一側(cè)的r個(gè)鄰居進(jìn)行連接；之后以概率p移除每條邊的一個(gè)端點(diǎn)，與另一個(gè)等概率選取的新節(jié)點(diǎn)相連，并避免生成自環(huán)與多重邊。
小世界一般有以下兩個(gè)特性：
- 節(jié)點(diǎn)間最短路徑的長(zhǎng)度同長(zhǎng)較小
- 網(wǎng)絡(luò)的聚集性很高
yeast.gc <- decompose(yeast)[[1]]
# CHUNK 25
mean_distance(yeast.gc)
[1] 5.09597
diameter(yeast.gc)
# ---
## [1] 15
# ---
transitivity(yeast.gc) # 這意味著大約50% 的連通三元形成了三角形。
[1] 0.4686663
與組件概念相比，一個(gè)更好的連通性定義源于以下問(wèn)題：如果從圖中任意移除包括k個(gè)節(jié)點(diǎn)（或邊）的子集，剩余的子圖是否還是連通的？這種思路可以使用節(jié)點(diǎn)和邊連接通度的概念，以及節(jié)點(diǎn)和邊的割等相關(guān)概念進(jìn)行精確定義。若圖G滿(mǎn)足（1）節(jié)點(diǎn)數(shù)Nv>k，（2）移除基數(shù)|X|<k的任意節(jié)點(diǎn)子集X?V，得到的子圖是連通的，則稱(chēng)圖“k節(jié)點(diǎn)連通”（k-vertex-connected）。類(lèi)似地，若（1）Nv≥2，且（2）移除基數(shù)|Y|<k的任意邊的子集，得到的子圖是連通的，則稱(chēng)圖G是“k邊連通”（k-edge-connected）。若圖G是k節(jié)點(diǎn)（邊）連通的，最大的整數(shù)k稱(chēng)為圖的“節(jié)點(diǎn)（邊）連通度”（vertex (edge) connectivity）?？梢宰C明，節(jié)點(diǎn)連通度的上界為邊連通度，而邊連通度的上界為圖G中節(jié)點(diǎn)的最小值dmin。
vertex_connectivity(yeast.gc)
# ---
## [1] 1
# ---
edge_connectivity(yeast.gc)
# ---
## [1] 1
如果移除圖中的某個(gè)節(jié)點(diǎn)（邊）的集合破壞了圖的連通，這個(gè)集合稱(chēng)為“點(diǎn)割集（邊割集）”（vertex-cut，edge-cut）。能破壞圖連通性的單個(gè)節(jié)點(diǎn)稱(chēng)為“割點(diǎn)”（cut vertex），有時(shí)也稱(chēng)為“關(guān)節(jié)點(diǎn)”（articulation point）。
yeast.cut.vertices <- articulation_points(yeast.gc)
length(yeast.cut.vertices)
350
在有向圖中的擴(kuò)展
# CHUNK 30
is_connected(aidsblog, mode=c("weak"))
# ---
## [1] TRUE
# ---
# CHUNK 31
is_connected(aidsblog, mode=c("strong"))
# ---
## [1] FALSE
# ---
# CHUNK 32
aidsblog.scc <- components(aidsblog, mode=c("strong"))
table(aidsblog.scc$csize)
# ---
##
## 1 4
## 142 1
# ---
圖分割
圖分割（graph partitioning）問(wèn)題在復(fù)雜網(wǎng)絡(luò)方面的文獻(xiàn)中也常被稱(chēng)為社團(tuán)發(fā)現(xiàn)（community detection）問(wèn)題。模塊度（modularity）是社團(tuán)發(fā)現(xiàn)中用來(lái)衡量社團(tuán)劃分質(zhì)量的一種方法，一個(gè)相對(duì)好的結(jié)果在社團(tuán)（community）內(nèi)部的節(jié)點(diǎn)連接度較高，而在社團(tuán)外部節(jié)點(diǎn)的連接度較低。
分割（partitioning）泛指將元素的集合劃分到“自然的”子集之中的過(guò)程。更正式地，一個(gè)有限集S的分割?={C1,…,CK}是將S分割為K個(gè)不相交的非空子集Ck，滿(mǎn)足UKk=1Ck=S。在網(wǎng)絡(luò)圖的分析中，分割是一種無(wú)監(jiān)督的方法，用于發(fā)現(xiàn)具有“凝聚性”的節(jié)點(diǎn)子集，揭示潛在的關(guān)系模式。開(kāi)發(fā)社團(tuán)發(fā)現(xiàn)的算法一直是研究的熱點(diǎn)，算法有很多，如層次聚類(lèi)、譜分割等，更多的領(lǐng)域綜述可參考Fortunato等的文章（Fortunato and Lancichinetti, 2009）。
- 層次聚類(lèi)
- 普分割
層次聚類(lèi)
層次聚類(lèi)有兩個(gè)方向，由小到大的凝聚，由大到小的分割，具體可以參考文章數(shù)量生態(tài)學(xué)筆記||層
次聚類(lèi)
貪婪算法的凝聚聚類(lèi)，Community structure via greedy optimization of modularity。
kc <- cluster_fast_greedy(karate)
# CHUNK 34
length(kc)
# ---
## [1] 3
# ---
sizes(kc)
# ---
## Community sizes
## 1 2 3
## 18 11 5
# ---
membership(kc) # 社團(tuán)歸宿
Mr Hi Actor 2 Actor 3 Actor 4 Actor 5 Actor 6 Actor 7 Actor 8 Actor 9 Actor 10 Actor 11
2 2 2 2 3 3 3 2 1 1 3
Actor 12 Actor 13 Actor 14 Actor 15 Actor 16 Actor 17 Actor 18 Actor 19 Actor 20 Actor 21 Actor 22
2 2 2 1 1 3 2 1 2 1 2
Actor 23 Actor 24 Actor 25 Actor 26 Actor 27 Actor 28 Actor 29 Actor 30 Actor 31 Actor 32 Actor 33
1 1 1 1 1 1 1 1 1 1 1
John A
1
分群后的標(biāo)簽顏色與分組
plot(kc,karate)
library(ape)
dendPlot(kc, mode="phylo")
譜聚類(lèi)算法由于其算法流程簡(jiǎn)單、計(jì)算簡(jiǎn)潔與 Kmeans 算法相比不容易陷入局部最優(yōu)解，能夠?qū)Ω呔S度、非常規(guī)分布的數(shù)據(jù)進(jìn)行聚類(lèi)。譜聚類(lèi)算法是利用圖譜理論來(lái)進(jìn)行算法分析，思想是把數(shù)據(jù)分析問(wèn)題看成是圖的最優(yōu)分割問(wèn)題，將數(shù)據(jù)樣本看成是各個(gè)數(shù)據(jù)點(diǎn)，然后將數(shù)據(jù)點(diǎn)描繪成一個(gè)圖表，根據(jù)圖表關(guān)系計(jì)算出相應(yīng)的相似矩陣，找到一種最優(yōu)分割方法計(jì)算出相似矩陣的最小特征向量，最后利用相應(yīng)算法得出最后的聚類(lèi)結(jié)果。
譜聚類(lèi)算法是將樣本點(diǎn)看成為一個(gè)個(gè)頂點(diǎn)，將頂點(diǎn)之間用帶權(quán)的邊連接起來(lái)，帶權(quán)的邊可以看成是頂點(diǎn)之間的相似度。聚類(lèi)從而可以看成如何分割這些帶權(quán)的邊，繼而將聚類(lèi)問(wèn)題轉(zhuǎn)化為怎么進(jìn)行圖分割的問(wèn)題，但是如果這樣的話(huà)新的問(wèn)題又產(chǎn)生了，那就是怎樣找到一種最優(yōu)方法來(lái)劃分這個(gè)圖，才能使同組之間的樣本權(quán)重盡可能高，不同組的權(quán)重盡可能的低。權(quán)重太低的邊是多余的就要舍去，常用保留邊的方法是要建立最鄰近圖譜，在最鄰近圖譜中每個(gè)頂點(diǎn)只與K 個(gè)相似度最高的點(diǎn)連接，其余的邊是要舍棄的邊。
建立最鄰近圖譜的方法就是把聚類(lèi)問(wèn)題轉(zhuǎn)化為圖分割的問(wèn)題，轉(zhuǎn)化之后就存在兩個(gè)問(wèn)題：
（1）數(shù)據(jù)點(diǎn)與數(shù)據(jù)點(diǎn)之間的相似度的定義；
（2）建立最鄰近圖譜之后要從哪條邊或者從哪些邊分割最優(yōu)。
# CHUNK 38
k.lap <- laplacian_matrix(karate)
eig.anal <- eigen(k.lap)
# CHUNK 39
plot(eig.anal$values, col="blue",
ylab="Eigenvalues of Graph Laplacian")
# CHUNK 40
f.vec <- eig.anal$vectors[, 33]
# CHUNK 41
faction <- get.vertex.attribute(karate, "Faction")
f.colors <- as.character(length(faction))
f.colors[faction == 1] <- "red"
f.colors[faction == 2] <- "cyan"
plot(f.vec, pch=16, xlab="Actor Number",
ylab="Fiedler Vector Entry", col=f.colors)
abline(0, 0, lwd=2, col="lightgray")
圖分割說(shuō)白了就是在圖結(jié)構(gòu)空間的聚類(lèi)，同一般的聚類(lèi)一樣，對(duì)結(jié)果的驗(yàn)證很重要，盡管常常不容易。
我們用蛋白網(wǎng)絡(luò)圖做以說(shuō)明。
# CHUNK 42
func.class <- vertex_attr(yeast.gc, "Class")
table(func.class)
# ---
## func.class
## A B C D E F G M O P R T U
## 51 98 122 238 95 171 96 278 171 248 45 240 483
# ---
yc <- cluster_fast_greedy(yeast.gc)
c.m <- membership(yc)
c.m
YLR197W YOR039W YDR473C YOR332W YER090W YDR394W YER021W YPR029C YIL106W YKL166C
5 5 3 7 4 4 4 12 7 27
YGL026C YOR061W YGL115W YGL049C YDL140C YLR291C YGR158C YDR328C YOL094C YDR460W
4 5 12 3 1 3 10 9 7 17
YBR154C YOR116C YIL062C YPR010C YER027C YPL093W YER006W YFR052W YOR261C YHR052W
1 1 8 4 12 5 5 4 4 5
YDR280W YOR260W YMR193W YGR162W YPR187W YDR101C YOL041C YHR197W YBL045C YOR207C
10 3 1 3 1 1 5 5 4 1
YPL259C YLL008W YPL043W YGL220W YOR117W YOR310C YNL002C YBR126C YKL014C YCR077C
12 5 5 4 4 5 (略)
分類(lèi)和聚類(lèi)的結(jié)果做一比較
# CHUNK 44
table(c.m, func.class, useNA=c("no"))
# ---
## func.class
## c.m A B C D E F G M O P R T U
## 1 0 0 0 1 3 7 0 6 3 110 2 35 14
## 2 0 2 2 7 1 1 1 4 39 5 0 4 27
## 3 1 9 7 18 4 8 4 20 10 23 8 74 64
## 4 25 11 10 22 72 84 81 168 14 75 16 27 121
## 5 1 7 5 14 0 4 0 2 3 6 1 34 68
## 6 1 24 1 4 1 4 0 7 0 1 0 19 16
## 7 6 18 6 76 7 9 3 7 8 5 1 7 33
## 8 8 12 67 59 1 34 0 19 60 10 7 6 73
## 9 4 1 7 7 2 10 5 3 2 0 3 0 11
## 10 0 0 0 6 0 0 0 2 0 5 0 11 1
## 11 0 9 0 10 1 3 0 0 0 0 0 2 4
## 12 0 1 3 0 0 0 0 6 10 0 0 0 2
## 13 0 1 1 2 0 1 0 0 2 0 0 16 10
## 14 1 0 4 1 0 1 0 0 4 0 1 0 11
## 15 0 1 0 0 0 2 0 2 0 0 1 0 8
## 16 0 1 2 0 0 1 0 0 10 0 0 0 0
## 17 0 0 1 3 0 0 0 2 0 0 0 2 3
## 18 0 0 0 0 3 1 0 9 0 0 1 0 1
## 19 0 1 1 1 0 0 0 0 0 0 0 0 3
## 20 0 0 0 6 0 0 0 1 0 0 0 1 2
## 21 1 0 0 0 0 0 0 0 6 0 0 1 0
## 22 0 0 0 0 0 0 0 1 0 0 0 0 8
## 23 0 0 0 0 0 0 0 4 0 0 0 0 0
## 24 0 0 0 0 0 0 2 2 0 0 0 1 0
## 25 0 0 0 0 0 0 0 5 0 0 0 0 0
## 26 0 0 1 0 0 0 0 4 0 0 1 0 1
## 27 3 0 4 0 0 1 0 0 0 0 0 0 0
## 28 0 0 0 0 0 0 0 0 0 6 0 0 0
## 29 0 0 0 1 0 0 0 1 0 0 3 0 0
## 30 0 0 0 0 0 0 0 0 0 2 0 0 2
## 31 0 0 0 0 0 0 0 3 0 0 0 0 0
# ---
同配混合（assortative mixing）
節(jié)點(diǎn)間依據(jù)某些特征進(jìn)行選擇性連接，被稱(chēng)為同配混合（assortative mixing），用于量化給定網(wǎng)絡(luò)中同配程度的指標(biāo)稱(chēng)為同配系數(shù)（assortativity coefficient），本質(zhì)上是相關(guān)系數(shù)概念的一種變體。
需要注意的是，這里涉及的節(jié)點(diǎn)特征可以是分類(lèi)、有序或者連續(xù)的變量。
考慮分類(lèi)特征的情況：假設(shè)圖G中每個(gè)節(jié)點(diǎn)可以使用M個(gè)類(lèi)別中的一個(gè)進(jìn)行標(biāo)記，此時(shí)的同配系數(shù)定義為：
其中，fij是G中連接第i類(lèi)節(jié)點(diǎn)與第j類(lèi)節(jié)點(diǎn)的邊所占的比例，而fi+和f+i分別是結(jié)果矩陣5f的邊際行和與列和。
同配系數(shù)ra的值介于-1和1之間。當(dāng)圖的混合模式與保留邊際度分布時(shí)隨機(jī)分配邊的結(jié)果一致，該值為0。類(lèi)似地，當(dāng)圖的混合模式為完全同配（即邊只連接同一類(lèi)節(jié)點(diǎn)）時(shí)該值為1。但是，當(dāng)混合模式為完全異配，即圖中每條邊連接的都是不同類(lèi)型的節(jié)點(diǎn)時(shí)，上式中的系數(shù)不一定為-1。更多分析見(jiàn)Newman的綜述（Newman, 2002）。
當(dāng)感興趣的節(jié)點(diǎn)特征為連續(xù)變量而非離散，使用（xe,ye）表示由一條邊e∈E連接的兩個(gè)節(jié)點(diǎn)的特征。量化這一特征同配性的一個(gè)自然選擇是（xe,ye）的Pearson相關(guān)系數(shù)：
該值是對(duì)所有觀察變量對(duì)(x,y)的概括，fxy、fx+和f+y的定義與分類(lèi)變量類(lèi)似，σx與 σy分別是{fx+}與{f+y}頻率分布的標(biāo)準(zhǔn)差。
同配系數(shù)r經(jīng)常在網(wǎng)絡(luò)結(jié)構(gòu)研究中用于概括相鄰節(jié)點(diǎn)的度-度相關(guān)性。
v.types <- (V(yeast)$Class=="P")+1
v.types[is.na(v.types)] <- 1
assortativity_nominal(yeast, v.types, directed=FALSE)
# ---
## [1] 0.5232879
# ---
# CHUNK 46
assortativity_degree(yeast)
# ---
## [1] 0.4610798
# ---
匯總網(wǎng)絡(luò)描述性質(zhì)
as_adjacency_matrix(yeast) -> igraph
igraph <- network::as.network.matrix(igraph)
nodes_num <- length(V(yeast))
nodes_num
vcount(yeast)
edges_num <- length(E(yeast))
edges_num
#平均度（average degree）
average_degree <- mean(degree(yeast))
#或者，2x邊數(shù)量/節(jié)點(diǎn)數(shù)量
average_degree <- 2*edges_num/nodes_num
average_degree
#平均加權(quán)度（average weighted degree），僅適用于含權(quán)網(wǎng)絡(luò)
#average_weight_degree <- mean(strength(igraph))
#節(jié)點(diǎn)和邊連通度（connectivity）
nodes_connectivity <- vertex.connectivity(yeast)
nodes_connectivity
edges_connectivity <- edge.connectivity(yeast)
edges_connectivity
#平均路徑長(zhǎng)度（average path length）
average_path_length <- average.path.length(yeast, directed = FALSE)
average_path_length
#網(wǎng)絡(luò)直徑（diameter）
graph_diameter <- diameter(yeast, directed = FALSE)
graph_diameter
#圖密度（density）
graph_density <- graph.density(yeast)
graph_density
#聚類(lèi)系數(shù)（clustering coefficient）
clustering_coefficient <- transitivity(yeast)
clustering_coefficient
#介數(shù)中心性（betweenness centralization)
betweenness_centralization <- centralization.betweenness(yeast)$centralization
betweenness_centralization
#度中心性（degree centralization）
degree_centralization <- centralization.degree(yeast)$centralization
degree_centralization
#模塊性（modularity），詳見(jiàn) ?cluster_fast_greedy，?modularity，有多種模型
fc <- cluster_fast_greedy(yeast)
modularity <- modularity(yeast, membership(fc))
#互惠性（reciprocity），僅適用于有向網(wǎng)絡(luò)
#reciprocity(igraph, mode = 'default')
#reciprocity(igraph, mode = 'ratio')
#選擇部分做個(gè)匯總輸出
igraph_character <- data.frame(
nodes_num, #節(jié)點(diǎn)數(shù)量（number of nodes）
edges_num, #邊數(shù)量（number of edges）
average_degree, #平均度（average degree)
nodes_connectivity, #節(jié)點(diǎn)連通度（vertex connectivity）
edges_connectivity, #邊連通度（edges connectivity）
average_path_length, #平均路徑長(zhǎng)度（average path length）
graph_diameter, #網(wǎng)絡(luò)直徑（diameter）
graph_density, #圖密度（density）
clustering_coefficient, #聚類(lèi)系數(shù)（clustering coefficient）
betweenness_centralization, #介數(shù)中心性（betweenness centralization)
degree_centralization, #度中心性
modularity #模塊性（modularity）
)
igraph_character %>%
+ knitr::kable(caption = "Power Centrality Descriptives for NEO Big 5 correlation network")
Table: Descriptives
| nodes_num| edges_num| average_degree| nodes_connectivity| edges_connectivity| average_path_length| graph_diameter| graph_density| clustering_coefficient| betweenness_centralization| degree_centralization| modularity|
|---------:|---------:|--------------:|------------------:|------------------:|-------------------:|--------------:|-------------:|----------------------:|--------------------------:|---------------------:|----------:|
| 2617| 11855| 9.059992| 0| 0| 5.095629| 15| 0.0034633| 0.4686178| 0.1299893| 0.0416437| 0.6957512|
https://zhuanlan.zhihu.com/p/40227203
https://kateto.net/networks-r-igraph
http://www.itdecent.cn/p/9f9108983bcd
https://blog.csdn.net/yyl424525/article/details/103108506
https://www.cnblogs.com/rubinorth/p/5800624.html
https://tidygraph.data-imaginist.com/reference/index.html
https://cran.r-project.org/web/packages/CINNA/vignettes/CINNA.html
https://cloud.tencent.com/developer/article/1667095
http://www.itdecent.cn/p/6c980d6aaeb4
https://blog.csdn.net/qq_32416677/article/details/80496756
https://zhuanlan.zhihu.com/p/27874050
https://cloud.tencent.com/developer/article/1667115
https://blog.csdn.net/makenothing/article/details/50110221
