1 數(shù)據(jù)介紹
1.1 數(shù)據(jù)背景
該數(shù)據(jù)集來(lái)源于斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站（http://snap.stanford.edu/data/ego-Facebook.html）顽铸，由facebook的朋友列表組成吼过，facebook上用戶(hù)間的社交網(wǎng)絡(luò)岳枷，共有節(jié)點(diǎn)數(shù)4039個(gè)烙肺，邊緣數(shù)88233條饮焦。
1.2 數(shù)據(jù)預(yù)處理
本社交網(wǎng)絡(luò)分析案例是基于R 語(yǔ)言程序?qū)崿F(xiàn)的掏秩。原始數(shù)據(jù)為.txt文件疯特，讀入R語(yǔ)言中囱皿，展示如下：
建立社交網(wǎng)絡(luò)關(guān)系圖：
代碼如下：
g <- graph.data.frame(facebook)#加載數(shù)據(jù)框jpeg(filename='facebook.jpg',width=2000,height=2000,units='px')#生成圖片勇婴，大小是2000*2000px
plot(g,? ?
vertex.size=2, #節(jié)點(diǎn)大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #帶邊框
vertex.label.cex=0.5, #節(jié)點(diǎn)字體大小
vertex.label.color='black', #節(jié)點(diǎn)字體顏色
edge.arrow.size=0) #連線(xiàn)的箭頭的大小
dev.off() #關(guān)閉圖形設(shè)備，將緩沖區(qū)中的數(shù)據(jù)寫(xiě)入文件
建立某個(gè)人的社交網(wǎng)絡(luò)關(guān)系圖嘱腥，以其中某4個(gè)人為例：
建立某個(gè)用戶(hù)的二層社交網(wǎng)絡(luò)關(guān)系圖：
同時(shí)建立某兩個(gè)人的社交網(wǎng)絡(luò)關(guān)系圖：
根據(jù)聯(lián)系人的多少?zèng)Q定節(jié)點(diǎn)的大小和色彩耕渴，連線(xiàn)設(shè)成弧線(xiàn)，如下圖：
? ? ? 鄰接矩陣即反映節(jié)點(diǎn)之間是否有連邊的方形矩陣齿兔，維度為結(jié)點(diǎn)的個(gè)數(shù)橱脸，如果兩個(gè)結(jié)點(diǎn)之間有連邊，則矩陣中相應(yīng)的位置為1分苇，沒(méi)有連邊則為0添诉。無(wú)向網(wǎng)絡(luò)的鄰接矩陣是對(duì)稱(chēng)矩陣亏掀，而有向網(wǎng)絡(luò)的鄰接矩陣是非對(duì)稱(chēng)矩陣蟹漓。將數(shù)據(jù)轉(zhuǎn)換成鄰接矩陣如下：
代碼如下：
g1<-graph.data.frame(as.matrix(facebook))
g2<-get.adjacency(g1,sparse=FALSE) ###轉(zhuǎn)換為鄰接矩陣
2 統(tǒng)計(jì)特征分析
2.1 網(wǎng)絡(luò)基本屬性
我們發(fā)現(xiàn)網(wǎng)絡(luò)的網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)為4029，邊條數(shù)為88233耿眉，為有向網(wǎng)絡(luò)靖秩。網(wǎng)絡(luò)密度用來(lái)形容網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜程度须眷，越大說(shuō)明網(wǎng)絡(luò)越復(fù)雜竖瘾，網(wǎng)絡(luò)越能夠放在一塊，facebook社交網(wǎng)絡(luò)的網(wǎng)絡(luò)密度為0.00540992花颗，說(shuō)明該網(wǎng)絡(luò)不是很容易聚一塊兒捕传。該網(wǎng)絡(luò)的直徑為17，整個(gè)網(wǎng)絡(luò)的平均距離為4.337746扩劝。
2.2 度分布
節(jié)點(diǎn)的度：度越大庸论，該節(jié)點(diǎn)越重要，就facebook朋友間社交網(wǎng)絡(luò)而言棒呛，度越大聂示，表示與該用戶(hù)相聯(lián)系的用戶(hù)越多。經(jīng)計(jì)算条霜，我們發(fā)現(xiàn)催什，最小的度為1，節(jié)點(diǎn)數(shù)為75宰睡，最大的度為1045蒲凶，節(jié)點(diǎn)數(shù)為1。該facebook社交網(wǎng)絡(luò)為有向網(wǎng)絡(luò)拆内，故又分為入度和出度旋圆。就入度而言，最小入度為2麸恍，節(jié)點(diǎn)數(shù)為1灵巧。最大入度為1134，節(jié)點(diǎn)數(shù)為5抹沪。就出度而言刻肄，最小出度為1，節(jié)點(diǎn)數(shù)為16融欧，最大出度為1134敏弃，節(jié)點(diǎn)數(shù)為6。
度分布：
degree.distribution(g)
plot(degree.distribution(g))
入度與出度：
2.3 網(wǎng)絡(luò)聚類(lèi)系數(shù)
網(wǎng)絡(luò)聚類(lèi)系數(shù)可以衡量網(wǎng)絡(luò)中關(guān)聯(lián)性如何噪馏，值越大代表交互關(guān)系越大麦到。說(shuō)明網(wǎng)絡(luò)越復(fù)雜，越能放在一塊兒聚類(lèi)欠肾。Facebook社交網(wǎng)絡(luò)的網(wǎng)絡(luò)聚類(lèi)系數(shù)為0.5191893瓶颠；網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)為0.6169473；每個(gè)節(jié)點(diǎn)的聚類(lèi)系數(shù)如下圖（截取部分）：
2.4 節(jié)點(diǎn)重要性
（1）點(diǎn)的中心度
用于描述在某個(gè)點(diǎn)上刺桃，有多少條線(xiàn)粹淋，強(qiáng)調(diào)某點(diǎn)單獨(dú)的價(jià)值。
（截取部分如下）：
（2）中間中心度
代表最短距離是否都經(jīng)過(guò)該點(diǎn)，如果都經(jīng)過(guò)說(shuō)明這個(gè)點(diǎn)很重要廓啊，其中包括線(xiàn)的中心度欢搜。強(qiáng)調(diào)點(diǎn)在其他點(diǎn)之間調(diào)節(jié)能力，控制能力指數(shù)谴轮，中介調(diào)節(jié)效應(yīng)。
點(diǎn)的中間中心度（截取部分如下）：
線(xiàn)的中間中心度（截取部分如下）：
（3）接近中心度
接近中心度吹埠，用于描述該點(diǎn)與網(wǎng)絡(luò)中其他點(diǎn)距離之和的倒數(shù)第步，越大說(shuō)明越在中心，越能夠很快到達(dá)其他點(diǎn)缘琅，強(qiáng)調(diào)點(diǎn)在網(wǎng)絡(luò)的價(jià)值粘都。
截取部分如下：
（4）特征向量中心度
根據(jù)相鄰點(diǎn)的重要性來(lái)衡量該點(diǎn)的價(jià)值。首先計(jì)算鄰接矩陣刷袍，然后計(jì)算鄰接矩陣的特征向量翩隧。強(qiáng)調(diào)點(diǎn)在網(wǎng)絡(luò)的價(jià)值，并且比接近中心度厲害的是呻纹，點(diǎn)價(jià)值是根據(jù)近鄰點(diǎn)來(lái)決定的堆生。
截取部分如下：
（5）排序
將節(jié)點(diǎn)中心度、接近中心度雷酪、中間中心度淑仆、特征向量中心度排序如下：
我們發(fā)現(xiàn)，在facebook社交網(wǎng)絡(luò)中哥力，擁有低“特征向量中心度”和高“中間性”的人是很重要的聯(lián)系人蔗怠，而擁有高“特征向量中心度”和低“中間性”的人與重要的人有關(guān)聯(lián)。
2.5社區(qū)結(jié)構(gòu)
社群劃分跟聚類(lèi)差不多吩跋，社群內(nèi)邊密度要高于社群間邊密度寞射，社群內(nèi)部連接相對(duì)緊密，各個(gè)社群之間連接相對(duì)稀疏锌钮。
1桥温、 社區(qū)劃分
上圖圖1為我們將社區(qū)劃分為8個(gè)，圖2為在劃分完的社區(qū)中轧粟，社區(qū)成員1構(gòu)成的網(wǎng)絡(luò)關(guān)系圖策治。
2、 基于隨機(jī)游走的社區(qū)劃分
隨機(jī)游走兰吟，利用距離相似度通惫，用合并層次聚類(lèi)方法建立社群，其特點(diǎn)是運(yùn)行時(shí)間短混蔼，但是效果不是特別好履腋，也會(huì)出現(xiàn)某類(lèi)巨多。從中我們可以看出facebook社交網(wǎng)絡(luò)被劃分為了68個(gè)社區(qū)。
從圖中可以直觀(guān)地看出好友網(wǎng)絡(luò)已經(jīng)被劃分為若干相對(duì)獨(dú)立的子群
查看不同子群中的成員如下遵湖，以其中兩個(gè)子群為例：
查看起中介作用的好友悔政，畫(huà)出散點(diǎn)圖如下：
3、 基于點(diǎn)連接的社區(qū)發(fā)現(xiàn)
點(diǎn)連接為某點(diǎn)與某社群有關(guān)系就是某社群的延旧，通常社區(qū)劃分效果最差谋国，常常是某一大類(lèi)超級(jí)多。對(duì)于該facebook社交網(wǎng)絡(luò)來(lái)說(shuō)迁沫，因其為有向圖芦瘾，所以分為強(qiáng)關(guān)聯(lián)與弱關(guān)聯(lián)，兩點(diǎn)間有雙向連線(xiàn)為強(qiáng)關(guān)聯(lián)集畅，有單向連線(xiàn)近弟，則為弱關(guān)聯(lián)。
3 鏈接預(yù)測(cè)
我選擇的是基于鄰居的相似度指標(biāo)進(jìn)行鏈路預(yù)測(cè)挺智。
根據(jù)基于鄰居的8種相似度鏈路預(yù)測(cè)算法的AUC值的對(duì)比祷愉，RA指標(biāo)的AUC值在各種情況下都表現(xiàn)較優(yōu)，因此選擇RA指標(biāo)來(lái)進(jìn)行鏈路預(yù)測(cè)赦颇。
此處考慮最簡(jiǎn)單的情況二鳄，每一個(gè)起傳遞作用的中間節(jié)點(diǎn)都有一個(gè)單位資源，將資源等可能的分配給它所有鄰居節(jié)點(diǎn)沐扳，因此相似度定義為：節(jié)點(diǎn)i從j接受到的資源總量(同樣為節(jié)點(diǎn)j從i接收到的資源總量)泥从。計(jì)算公式為：
算法過(guò)程：
（1）首先按照8:2的比例劃分訓(xùn)練集和測(cè)試集，并得到訓(xùn)練集鄰接矩陣和測(cè)試集鄰接矩陣沪摄；
（2）得到未觀(guān)測(cè)邊集躯嫉、測(cè)試邊集和未存在邊集；
（3）得到每個(gè)訓(xùn)練集中杨拐，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)祈餐；
（4）得到未觀(guān)測(cè)邊連接的兩節(jié)點(diǎn)的公共鄰居節(jié)點(diǎn)，并計(jì)算未觀(guān)測(cè)邊得分r哄陶，將得分按降序排序帆阳，取前10，即為尚未存在的邊中可能會(huì)首先產(chǎn)生連接的10條邊屋吨。
（5）評(píng)估精度（AUC）蜒谤，AUC值約為0.50。
附代碼：
install.packages("igraph")
library(igraph)
library("Matrix")
demo(package="igraph") #查看igraph子項(xiàng)目
demo(package="igraph", community) #查看igraph子項(xiàng)目中community示例
facebook<-read.table("/Users/zhangyuhao/Desktop/facebook.txt",header = T)
g <- graph.data.frame(facebook)#加載數(shù)據(jù)框
head(facebook)#看數(shù)據(jù)表的前6行
tail(facebook)#看數(shù)據(jù)表的后6行
data1 = as.matrix(facebook)
g1<-graph.data.frame(as.matrix(facebook))
g2<-get.adjacency(g1,sparse=FALSE) ###轉(zhuǎn)換為鄰接矩陣
###建立社交網(wǎng)絡(luò)圖
jpeg(filename='facebook.jpg',width=2000,height=2000,units='px')#生成圖片至扰，大小是2000*2000px
plot(g,
? ? vertex.size=2, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=0.5, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
? ? edge.arrow.size=0) #連線(xiàn)的箭頭的大小
#關(guān)閉圖形設(shè)備鳍徽，將緩沖區(qū)中的數(shù)據(jù)寫(xiě)入文件
dev.off()
####關(guān)系圖中某人或某幾個(gè)人的關(guān)系圖
#某個(gè)人的關(guān)系圖：
jpeg(filename='mem1_1.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=1)
plot(gn[[1]],
? ? vertex.size=5, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=2, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
? ? )
dev.off()
jpeg(filename='mem1_2.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=1)
plot(gn[[2]],
? ? vertex.size=5, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=2, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
)
dev.off()
jpeg(filename='mem1_100.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=1)
plot(gn[[100]],
? ? vertex.size=5, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=1, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
)
dev.off()
jpeg(filename='mem1_4039.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=1)
plot(gn[[4039]],
? ? vertex.size=5, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=2, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
)
dev.off()
#某個(gè)人的兩層關(guān)系圖：
jpeg(filename='mem2_2.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=2)
plot(gn[[2]],
? ? vertex.size=5, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=2, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
? ? vertex.label.color ='pink',
)
dev.off()
#某個(gè)人的兩層關(guān)系圖：
jpeg(filename='mem2_10.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=2)
plot(gn[[10]],
? ? vertex.size=5, #節(jié)點(diǎn)大小
? ? layout=layout.fruchterman.reingold, #布局方式
? ? vertex.shape='circle', #帶邊框
? ? vertex.label.cex=2, #節(jié)點(diǎn)字體大小
? ? vertex.label.color='black', #節(jié)點(diǎn)字體顏色
? ? )
dev.off()
#某兩個(gè)人的關(guān)系圖：
jpeg(filename='mem4.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=1)
plot(gn[[2]]+gn[[3]], layout=layout.fruchterman.reingold)
dev.off()
#根據(jù)聯(lián)系人的多少?zèng)Q定節(jié)點(diǎn)的大小和色彩，連線(xiàn)設(shè)成弧線(xiàn)
source("http://michael.hahsler.net/SMU/ScientificCompR/code/map.R")
E(g)$curved <- 0.2 #將連線(xiàn)設(shè)成弧線(xiàn)敢课，數(shù)值越大弧線(xiàn)越彎
jpeg(filename='mem5.jpg',width=2000,height=2000,units='px')
layout=layout.fruchterman.reingold
plot(g,
? layout=layout,
? ? vertex.size=map(degree(g),c(1,20)),
? ? vertex.color=map(degree(g),c(1,20)))
dev.off()
#####統(tǒng)計(jì)特征分析
###網(wǎng)絡(luò)基本屬性
V(g) #V(g)可以用來(lái)查看網(wǎng)絡(luò)g的節(jié)點(diǎn)
E(g) #E(g)可以用來(lái)查看網(wǎng)絡(luò)g的邊
length(V(g)) #節(jié)點(diǎn)個(gè)數(shù)
length(E(g)) #邊條數(shù)
is.igraph(g) #判斷
is.directed(g) #判斷是否有向圖
graph.density(g) #網(wǎng)絡(luò)密度
dm <- diameter(g)#計(jì)算網(wǎng)路的直徑阶祭，即MAX（任意兩個(gè)節(jié)點(diǎn)之間的最短路徑）
dm
average.path.length(g)#計(jì)算整個(gè)網(wǎng)路的平均距離（任意兩節(jié)點(diǎn)直接的最短路徑的平均值）
clusters(g)$no#孤立點(diǎn)個(gè)數(shù)
edge.connectivity(g)
graph.adhesion(g)
reciprocity(g)
shortest.paths(g)#兩點(diǎn)間的最短路徑
###網(wǎng)絡(luò)聚類(lèi)系數(shù)
transitivity(g,type = "global") #網(wǎng)絡(luò)的聚類(lèi)系數(shù)
transitivity(g,type = "average") #網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)
transitivity(g,type = "local") #每個(gè)節(jié)點(diǎn)的聚類(lèi)系數(shù)
###度分布
degree<-degree(g,mode="all") #統(tǒng)計(jì)節(jié)點(diǎn)的度
table(degree)
degree.distribution(g)
plot(degree.distribution(g), xlab="node degree")
lines(degree.distribution(g))
degree(g,mode="in") #mode=in點(diǎn)入度绷杜；out=點(diǎn)出度；total點(diǎn)度中心度濒募，三者統(tǒng)稱(chēng)絕對(duì)點(diǎn)中心度
degree(g,mode="out") #mode=in點(diǎn)入度鞭盟；out=點(diǎn)出度；total點(diǎn)度中心度瑰剃，三者統(tǒng)稱(chēng)絕對(duì)點(diǎn)中心度
degree(g,normalized = T) #相對(duì)點(diǎn)中心度=絕對(duì)點(diǎn)中心度/最大度數(shù)（可以作為不同網(wǎng)絡(luò)結(jié)構(gòu)的比較齿诉，相對(duì)數(shù)與絕對(duì)數(shù)的區(qū)別）
###節(jié)點(diǎn)的重要性
#- 擁有較高出/入度數(shù)的節(jié)點(diǎn)也擁有較高的“度中心性”
#- 與其他節(jié)點(diǎn)之間有短路徑的節(jié)點(diǎn)擁有較高的“密集中心性”
#- 與其他節(jié)點(diǎn)對(duì)之間有最短路徑的節(jié)點(diǎn)擁有較高的“中間性”
#- 連接了許多中心性較高節(jié)點(diǎn)的節(jié)點(diǎn)擁有較高的“特征向量中心性”
#- 本地簇系數(shù)意味著相鄰節(jié)點(diǎn)的互聯(lián)性
degree(g) #點(diǎn)的中心度
closeness(g)#接近中心度
betweenness(g,normalized = T) #點(diǎn)的中間中心度
edge.betweenness(g) #線(xiàn)的中間中心度
evcent(g)$vector #特征向量中心度
transitivity(g, type="local") #本地簇
order(degree(g))[1:10]
order(closeness(g))[1:10]
order(betweenness(g))[1:10]
order(evcent(g)$vector)[1:10]
order(degree(g),decreasing = T)[1:10]
order(closeness(g),decreasing = T)[1:10]
order(betweenness(g),decreasing = T)[1:10]
order(evcent(g)$vector,decreasing = T)[1:10]
###社區(qū)結(jié)構(gòu)
#1、設(shè)定社區(qū)的數(shù)目
sg1 <- cluster_spinglass(g, spins=8, gamma=1.0) #spins是社區(qū)的數(shù)目
jpeg(filename='dolphins_commu9.jpg',width=800,height=800,units='px')
layout=layout.fruchterman.reingold
plot(g, layout=layout, vertex.size=5, vertex.color= rainbow(10, .8, .8, alpha=.8)[sg1$membership],)
dev.off()
#畫(huà)出某一社區(qū)培他，畫(huà)出上面社區(qū)中鹃两，membership為1的社區(qū)。
sg1 <- cluster_spinglass(g, spins=8, gamma=1.0)
jpeg(filename='mem10.jpg',width=2000,height=2000,units='px')
layout=layout.fruchterman.reingold
subg <- induced.subgraph(g, which(membership(sg1)==1))
plot(subg,
? ? layout=layout,
? ? vertex.size=5,
? ? vertex.color= 1,)
dev.off()
###2舀凛、基于隨機(jī)游走的社會(huì)劃分
com = walktrap.community(g, steps = 5)
sg = data.frame(name = com$names, sg = com$membership + 1)
subgroup = vector("list", length(unique(com$membership)))
for(i in 1:length(unique(com$mem))){
subgroup[[i]] = as.character(sg[sg[, 2]== i, 1])}
rm(i)
## subgroup
V(g)$sg = com$membership + 1
V(g)$color = rainbow(max(V(g)$sg))[V(g)$sg]
png("net_walktrap.jpg", width = 2000, height = 2000)
par(mar = c(0, 0, 0, 0))
set.seed(14)
plot(g, layout = layout.fruchterman.reingold,
? ? vertex.size = 5,
? ? vertex.color = V(g)$color,
? ? vertex.label = NA,
? ? edge.color = grey(0.5),
? ? edge.arrow.mode = "-")
dev.off()
subgroup[[9]]
subgroup[[2]]
V(g)$bte = betweenness(g, directed = F)
png("net_betweenness.png", width = 500, height = 500)
par(mar = c(0, 2, 0, 0))
plot(V(g)$bte)
dev.off()
#基于點(diǎn)連接的社群發(fā)現(xiàn)——clusters
clusters(g,mode="strong")
clusters(g,mode="weak")
###鏈接預(yù)測(cè)
###基于鄰居的相似度指標(biāo)——資源分配(RA)指標(biāo)
#劃分訓(xùn)練集和測(cè)試集
edge = matrix(0,nrow=88233,ncol=2,dimnames=list(c(1:88233),c("Source","Target")))
k=1
for(i in 1:length(data1[,1]))
{
for(j in i:length(data1[1,]))
{
? if(facebook[i,j]==1)
{
? ? edge[k,1]=i
? ? edge[k,2]=j
? ? k=k+1
}
}
}#得到邊數(shù)據(jù)
v = length(data1[,1])
e = length(edge[,1])
set.seed(20181231)
sp = sample(2, nrow(facebook), replace = TRUE, prob=c(0.8, 0.2))
train_edge = as.data.frame(edge[sp == 1,])
test_edge = as.data.frame(edge[sp == 2,])
#轉(zhuǎn)換為鄰接矩陣形式
train = matrix(0,nrow=1000,ncol=1000,dimnames=list(c(1:1000),c(1:1000)))
test = matrix(0,nrow=1000,ncol=1000,dimnames=list(c(1:1000),c(1:1000)))
for(i in 1:length(train_edge[,1]))
{
train[train_edge[i,1],train_edge[i,2]]=1
}
for(i in 1:length(test_edge[,1]))
{
test[test_edge[i,1],test_edge[i,2]]=1
}
g_train = graph.adjacency(train,mode="undirected",weighted=T)
g_test = graph.adjacency(test,mode="undirected",weighted=T)
#未觀(guān)測(cè)邊集
train_edge = train_edge[order(train_edge[,1],train_edge[,2]),]
max = (v*(v-1))/2
row = max-length(train_edge[,1])
edge_no = matrix(0,nrow=row,ncol=2,dimnames=list(c(1:row),c("Source","Target")))
t=1
s=1
for(i in 1:v)
{
x = matrix(1:v,nrow=v,ncol=1)
for(j in 1:v)
{
? if(s<=length(train_edge[,1])&&train_edge[s,1]==i)
{
? ? x[train_edge[s,2],1]=0
? ? s=s+1
}
? else
? ? break
}
k=i+1
while(k<=v)
{
? if(x[k,1]!=0)
{
? ? edge_no[t,1] = i
? ? edge_no[t,2] = x[k,1]
? ? t=t+1
}
? k=k+1
}
}
rm(x)
#計(jì)算兩點(diǎn)間的公共鄰居結(jié)點(diǎn)及其度
degree_train = degree(g_train)
degree_train_each = as.data.frame(matrix(0,nrow=v,ncol=2,dimnames=list(c(1:v),c("Id","Degree"))))
for(i in 1:v)
{
degree_train_each[i,1]=i
degree_train_each[i,2]=degree_train[[i]]
}#得到訓(xùn)練集每個(gè)節(jié)點(diǎn)的度
#得到每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)
naber = as.data.frame(matrix(0,nrow=max(degree),ncol=v,dimnames=list(c(1:max(degree)),c(1:v))))
for(i in 1:v)
{
k=1
for(j in 1:v)
{
? if(train[i,j]==1)
{
? ? naber[k,i]=j
? ? k=k+1
}
}
}
#得到未觀(guān)測(cè)邊連接的兩節(jié)點(diǎn)的公共鄰居節(jié)點(diǎn)，并計(jì)算未觀(guān)測(cè)邊得分r
r = as.data.frame(matrix(0,nrow=row,ncol=1))
edge_no = cbind(edge_no,r)
names(edge_no)=c("Source","Target","r")
for(i in 1:length(edge_no[,1]))
{
x = edge_no[i,1]
y = edge_no[i,2]
r=0
same = intersect(naber[,x],naber[,y])
if(same[1]==0)
? edge_no[i,3]=r
else
{
? for(k in 1:length(same))
{
? ? if(same[k]==0)
? ? ? break
? ? else
? ? ? if(degree_train_each[same[k],2]!=0)
? ? ? ? r=r+1/(degree_train_each[same[k],2])
}
? edge_no[i,3]=r
}
}
#排序
edge_no = edge_no[order(edge_no[,1],edge_no[,2]),]
Top10 = edge_no[order(edge_no[,3],decreasing=T),][1:10,]
####評(píng)估精度（AUC）
#計(jì)算測(cè)試邊集中的邊的得分
r = as.data.frame(matrix(0,nrow=length(test_edge[,1]),ncol=1))
test_edge = cbind(test_edge,r)
names(test_edge)=c("Source","Target","r")
i=1
j=1
while(i<=length(test_edge[,1])&&j<=length(edge_no[,1]))
{
if(edge_no[j,1]>test_edge[i,1])
? i=i+1
else
? if(edge_no[j,1]
? ? j=j+1
? else
? ? if(edge_no[j,2]>test_edge[i,2])
? ? ? i=i+1
? ? else
? ? ? if(edge_no[j,2]
? ? ? ? j=j+1
? else
? ? ? {
? ? ? ? test_edge[i,3]=edge_no[j,3]
? ? ? ? i=i+1
? ? ? ? j=j+1
? ? ? }
}
#計(jì)算未存在邊集中的邊的得分
#構(gòu)建未存在邊集
max = (v*(v-1))/2
row1 = max-length(edge[,1])
edge_not_exist = matrix(0,nrow=row1,ncol=2,dimnames=list(c(1:row1),c("Source","Target")))
t=1
s=1
for(i in 1:v)
{
x = matrix(1:v,nrow=v,ncol=1)
for(j in 1:v)
{
? if(s<=e&&edge[s,1]==i)
{
? ? x[edge[s,2],1]=0
? ? s=s+1
}
? else
? ? break
}
k=i+1
while(k<=v)
{
? if(x[k,1]!=0)
{
? ? edge_not_exist[t,1] = i
? ? edge_not_exist[t,2] = x[k,1]
? ? t=t+1
}
? k=k+1
}
}
rm(x)
r = as.data.frame(matrix(0,nrow=length(edge_not_exist[,1]),ncol=1))
edge_not_exist = cbind(edge_not_exist,r)
names(edge_not_exist)=c("Source","Target","r")
i=1
j=1
while(i<=length(edge_not_exist[,1])&&j<=length(edge_no[,1]))
{
if(edge_no[j,1]>edge_not_exist[i,1])
? i=i+1
else
? if(edge_no[j,1]
? ? j=j+1
? else
? ? if(edge_no[j,2]>edge_not_exist[i,2])
? ? ? i=i+1
? ? else
? ? ? if(edge_no[j,2]
? ? ? ? j=j+1
? ? ? else
? ? ? {
? ? ? ? edge_not_exist[i,3]=edge_no[j,3]
? ? ? ? i=i+1
? ? ? ? j=j+1
? ? ? }
}
#比較測(cè)試邊集和未存在邊集途蒋，得AUC
len1 = length(test_edge[,1])
len2 = length(edge_not_exist[,1])
down = len1*len2
n1 = 0
n0 = 0
for(i in 1:length(test_edge[,1]))
{
for(j in 1:length(edge_not_exist[,1]))
{
? if(test_edge[i,3]>edge_not_exist[j,3])
? ? n1=n1+1
? if(test_edge[i,3]==edge_not_exist[j,3])
? ? n0=n0+1
}
}
AUC = (n1+0.5*n0)/down
