1 数据介绍
1.1 数据背景
该数据集来源于斯坦福大型网络数据集网站（http://snap.stanford.edu/data/ego-Facebook.html），由facebook的朋友列表组成，facebook上用户间的社交网络，共有节点数4039个，边缘数88233条。
1.2 数据预处理
本社交网络分析案例是基于R 语言程序实现的。原始数据为.txt文件，读入R语言中，展示如下：
建立社交网络关系图：
代码如下：
g <- graph.data.frame(facebook)#加载数据框jpeg(filename='facebook.jpg',width=2000,height=2000,units='px')#生成图片，大小是2000*2000px
plot(g,
vertex.size=2, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=0.5, #节点字体大小
vertex.label.color='black', #节点字体颜色
edge.arrow.size=0) #连线的箭头的大小
dev.off() #关闭图形设备，将缓冲区中的数据写入文件
建立某个人的社交网络关系图，以其中某4个人为例：
建立某个用户的二层社交网络关系图：
同时建立某两个人的社交网络关系图：
根据联系人的多少决定节点的大小和色彩，连线设成弧线，如下图：
邻接矩阵即反映节点之间是否有连边的方形矩阵，维度为结点的个数，如果两个结点之间有连边，则矩阵中相应的位置为1，没有连边则为0。无向网络的邻接矩阵是对称矩阵，而有向网络的邻接矩阵是非对称矩阵。将数据转换成邻接矩阵如下：
代码如下：
g1<-graph.data.frame(as.matrix(facebook))
g2<-get.adjacency(g1,sparse=FALSE) ###转换为邻接矩阵
2 统计特征分析
2.1 网络基本属性
我们发现网络的网络的节点个数为4029，边条数为88233，为有向网络。网络密度用来形容网络的结构复杂程度，越大说明网络越复杂，网络越能够放在一块，facebook社交网络的网络密度为0.00540992，说明该网络不是很容易聚一块儿。该网络的直径为17，整个网络的平均距离为4.337746。
2.2 度分布
节点的度：度越大，该节点越重要，就facebook朋友间社交网络而言，度越大，表示与该用户相联系的用户越多。经计算，我们发现，最小的度为1，节点数为75，最大的度为1045，节点数为1。该facebook社交网络为有向网络，故又分为入度和出度。就入度而言，最小入度为2，节点数为1。最大入度为1134，节点数为5。就出度而言，最小出度为1，节点数为16，最大出度为1134，节点数为6。
度分布：
degree.distribution(g)
plot(degree.distribution(g))
入度与出度：
2.3 网络聚类系数
网络聚类系数可以衡量网络中关联性如何，值越大代表交互关系越大。说明网络越复杂，越能放在一块儿聚类。Facebook社交网络的网络聚类系数为0.5191893；网络的平均聚类系数为0.6169473；每个节点的聚类系数如下图（截取部分）：
2.4 节点重要性
（1）点的中心度
用于描述在某个点上，有多少条线，强调某点单独的价值。
（截取部分如下）：
（2）中间中心度
代表最短距离是否都经过该点，如果都经过说明这个点很重要，其中包括线的中心度。强调点在其他点之间调节能力，控制能力指数，中介调节效应。
点的中间中心度（截取部分如下）：
线的中间中心度（截取部分如下）：
（3）接近中心度
接近中心度，用于描述该点与网络中其他点距离之和的倒数，越大说明越在中心，越能够很快到达其他点，强调点在网络的价值。
截取部分如下：
（4）特征向量中心度
根据相邻点的重要性来衡量该点的价值。首先计算邻接矩阵，然后计算邻接矩阵的特征向量。强调点在网络的价值，并且比接近中心度厉害的是，点价值是根据近邻点来决定的。
截取部分如下：
（5）排序
将节点中心度、接近中心度、中间中心度、特征向量中心度排序如下：
我们发现，在facebook社交网络中，拥有低“特征向量中心度”和高“中间性”的人是很重要的联系人，而拥有高“特征向量中心度”和低“中间性”的人与重要的人有关联。
2.5社区结构
社群划分跟聚类差不多，社群内边密度要高于社群间边密度，社群内部连接相对紧密，各个社群之间连接相对稀疏。
1、 社区划分
上图图1为我们将社区划分为8个，图2为在划分完的社区中，社区成员1构成的网络关系图。
2、 基于随机游走的社区划分
随机游走，利用距离相似度，用合并层次聚类方法建立社群，其特点是运行时间短，但是效果不是特别好，也会出现某类巨多。从中我们可以看出facebook社交网络被划分为了68个社区。
从图中可以直观地看出好友网络已经被划分为若干相对独立的子群
查看不同子群中的成员如下，以其中两个子群为例：
查看起中介作用的好友，画出散点图如下：
3、 基于点连接的社区发现
点连接为某点与某社群有关系就是某社群的，通常社区划分效果最差，常常是某一大类超级多。对于该facebook社交网络来说，因其为有向图，所以分为强关联与弱关联，两点间有双向连线为强关联，有单向连线，则为弱关联。
3 链接预测
我选择的是基于邻居的相似度指标进行链路预测。
根据基于邻居的8种相似度链路预测算法的AUC值的对比，RA指标的AUC值在各种情况下都表现较优，因此选择RA指标来进行链路预测。
此处考虑最简单的情况，每一个起传递作用的中间节点都有一个单位资源，将资源等可能的分配给它所有邻居节点，因此相似度定义为：节点i从j接受到的资源总量(同样为节点j从i接收到的资源总量)。计算公式为：
算法过程：
（1）首先按照8:2的比例划分训练集和测试集，并得到训练集邻接矩阵和测试集邻接矩阵；
（2）得到未观测边集、测试边集和未存在边集；
（3）得到每个训练集中，节点的邻居节点；
（4）得到未观测边连接的两节点的公共邻居节点，并计算未观测边得分r，将得分按降序排序，取前10，即为尚未存在的边中可能会首先产生连接的10条边。
（5）评估精度（AUC），AUC值约为0.50。
附代码：
install.packages("igraph")
library(igraph)
library("Matrix")
demo(package="igraph") #查看igraph子项目
demo(package="igraph", community) #查看igraph子项目中community示例
facebook<-read.table("/Users/zhangyuhao/Desktop/facebook.txt",header = T)
g <- graph.data.frame(facebook)#加载数据框
head(facebook)#看数据表的前6行
tail(facebook)#看数据表的后6行
data1 = as.matrix(facebook)
g1<-graph.data.frame(as.matrix(facebook))
g2<-get.adjacency(g1,sparse=FALSE) ###转换为邻接矩阵
###建立社交网络图
jpeg(filename='facebook.jpg',width=2000,height=2000,units='px')#生成图片，大小是2000*2000px
plot(g,
vertex.size=2, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=0.5, #节点字体大小
vertex.label.color='black', #节点字体颜色
edge.arrow.size=0) #连线的箭头的大小
#关闭图形设备，将缓冲区中的数据写入文件
dev.off()
####关系图中某人或某几个人的关系图
#某个人的关系图：
jpeg(filename='mem1_1.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=1)
plot(gn[[1]],
vertex.size=5, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=2, #节点字体大小
vertex.label.color='black', #节点字体颜色
)
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, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=2, #节点字体大小
vertex.label.color='black', #节点字体颜色
)
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, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=1, #节点字体大小
vertex.label.color='black', #节点字体颜色
)
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, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=2, #节点字体大小
vertex.label.color='black', #节点字体颜色
)
dev.off()
#某个人的两层关系图：
jpeg(filename='mem2_2.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=2)
plot(gn[[2]],
vertex.size=5, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=2, #节点字体大小
vertex.label.color='black', #节点字体颜色
vertex.label.color ='pink',
)
dev.off()
#某个人的两层关系图：
jpeg(filename='mem2_10.jpg',width=2000,height=2000,units='px')
gn<-graph.neighborhood(g, order=2)
plot(gn[[10]],
vertex.size=5, #节点大小
layout=layout.fruchterman.reingold, #布局方式
vertex.shape='circle', #带边框
vertex.label.cex=2, #节点字体大小
vertex.label.color='black', #节点字体颜色
)
dev.off()
#某两个人的关系图：
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()
#根据联系人的多少决定节点的大小和色彩，连线设成弧线
source("http://michael.hahsler.net/SMU/ScientificCompR/code/map.R")
E(g)$curved <- 0.2 #将连线设成弧线，数值越大弧线越弯
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()
#####统计特征分析
###网络基本属性
V(g) #V(g)可以用来查看网络g的节点
E(g) #E(g)可以用来查看网络g的边
length(V(g)) #节点个数
length(E(g)) #边条数
is.igraph(g) #判断
is.directed(g) #判断是否有向图
graph.density(g) #网络密度
dm <- diameter(g)#计算网路的直径，即MAX（任意两个节点之间的最短路径）
dm
average.path.length(g)#计算整个网路的平均距离（任意两节点直接的最短路径的平均值）
clusters(g)$no#孤立点个数
edge.connectivity(g)
graph.adhesion(g)
reciprocity(g)
shortest.paths(g)#两点间的最短路径
###网络聚类系数
transitivity(g,type = "global") #网络的聚类系数
transitivity(g,type = "average") #网络的平均聚类系数
transitivity(g,type = "local") #每个节点的聚类系数
###度分布
degree<-degree(g,mode="all") #统计节点的度
table(degree)
degree.distribution(g)
plot(degree.distribution(g), xlab="node degree")
lines(degree.distribution(g))
degree(g,mode="in") #mode=in点入度；out=点出度；total点度中心度，三者统称绝对点中心度
degree(g,mode="out") #mode=in点入度；out=点出度；total点度中心度，三者统称绝对点中心度
degree(g,normalized = T) #相对点中心度=绝对点中心度/最大度数（可以作为不同网络结构的比较，相对数与绝对数的区别）
###节点的重要性
#- 拥有较高出/入度数的节点也拥有较高的“度中心性”
#- 与其他节点之间有短路径的节点拥有较高的“密集中心性”
#- 与其他节点对之间有最短路径的节点拥有较高的“中间性”
#- 连接了许多中心性较高节点的节点拥有较高的“特征向量中心性”
#- 本地簇系数意味着相邻节点的互联性
degree(g) #点的中心度
closeness(g)#接近中心度
betweenness(g,normalized = T) #点的中间中心度
edge.betweenness(g) #线的中间中心度
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]
###社区结构
#1、设定社区的数目
sg1 <- cluster_spinglass(g, spins=8, gamma=1.0) #spins是社区的数目
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()
#画出某一社区，画出上面社区中，membership为1的社区。
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、基于随机游走的社会划分
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()
#基于点连接的社群发现——clusters
clusters(g,mode="strong")
clusters(g,mode="weak")
###链接预测
###基于邻居的相似度指标——资源分配(RA)指标
#划分训练集和测试集
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
}
}
}#得到边数据
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,])
#转换为邻接矩阵形式
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)
#未观测边集
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)
#计算两点间的公共邻居结点及其度
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]]
}#得到训练集每个节点的度
#得到每个节点的邻居节点
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
}
}
}
#得到未观测边连接的两节点的公共邻居节点，并计算未观测边得分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,]
####评估精度（AUC）
#计算测试边集中的边的得分
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
}
}
#计算未存在边集中的边的得分
#构建未存在边集
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
}
}
#比较测试边集和未存在边集，得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
