文本挖掘：社交网络、社群划分

作者：Matt

自然语言处理实习生

http://blog.csdn.net/sinat_26917383/article/details/51444536

一、关系网络数据类型

关系网络需要什么样子的数据呢？ 笔者接触到了两种数据结构，擅自命名：平行关系型、文本型。根据数据关联，也有无向数据、有向数据。

并且关系网络生成之后，R里面就不是用真实的名字来做连接，是采用编号的。例如（小明-小红）是好朋友，在R里面就显示为（1-2），所以需要单独把名字属性加到序号上。

1、平行关系型

（1）无向平行数据。直接上例子比较直观，社交网络中的好友关系，你-我，我-他。这样排列，是无向

1. id1 di2
2. 小明 小红
3. 小张 小白
4. 小红 小胖
5. 小胖 小蓝
6. 小白 小明
7. 小白 小张
8. 小明 小胖

很简单的两列数据，说明了小明-小红、小张-小白的社会关系。当然需要注意，重名问题，名字可能有重叠，可以给每个人一个编号，这样就不会出现重名。

实战中，一般是拿编号作为输入变量，拿名字作为编号的标签，加入到关系网络中。

（2）有向平行数据。举一个书（《R语言与网站分析》）上的例子。解读一下这个图，这是一条微博的转发情况，“老牛”用户这个微博号转发，让“晴”、“四眼看八方”两个用户看到了。

“老牛”用户发出，“晴”、“四眼看八方”用户分别接收到。

2、文本型

文本型主要针对的是文本数据，笔者在参赛时就用到这个。文本型也有两种情况：有向型以及词条-文本矩阵。这部分内容跟文本挖掘相关，关于分词内容可以参考中文分词包Rwordseg。

（1）有向型就如同平行关系型有向数据结构一样，人名-词条两个

（2）词条-文本矩阵

文本挖掘中，一般都能获得这个矩阵，可以看一下tm包，文档-词频矩阵。tm包中用DocumentTermMatrix函数可以获得。

跟上面的对比一下就了解，变成了一个稀疏矩阵，相关的关联规则、随机森林中中也会用到这个矩阵。tm包可以实现，也可以通过reshape包中的cast函数，构造这个函数。

需要原来的数据框调整为以每个词作为列名称（变量）的数据框。也就是一定意义上的稀疏矩阵（同关联规则），也就是将long型数据框转化为wide型数据框。转换可以用的包有reshape2以及data.table。

其中，data.table里的`dcast`函数比reshape2包里的`dcast`好用，尽管他们的参数都一样，但是很多人还是比较喜欢老朋友reshape2包,然而这一步需要大量的内存，本书在服务器上完成的，如果你的电脑报告内存不足的错误，可以使用data.table包里的`dcast`函数试试。转化为稀疏矩阵，1表示访问，0表示未访问。

二、构造关系网络

1、自编译函数init.igraph

看到了数据类型，大概知道其实需要两样东西，一个起点数据列、一个终点数据列。那么构造数据就只需要调用一下函数，在这里选用《R语言与网站分析》书中第九章关系网络分析中，李明老师自己编译的函数来直接构造。

在使用之前需要library调用igraph包，该函数的好处就是直接帮你打上点标签以及线标签。

1. init.igraph<-function(data,dir=F,rem.multi=T){
2. labels<-union(unique(data[,1]),unique(data[,2]))
3. ids<-1:length(labels);names(ids)<-labels
4. from<-as.character(data[,1]);to<-as.character(data[,2])
5. edges<-matrix(c(ids[from],ids[to]),nc=2)
6. g<-graph.empty(directed = dir)
7. g<-add.vertices(g,length(labels))
8. V(g)$label=labels
9. g<-add.edges(g,t(edges))
10. if (rem.multi){
11. E(g)$weight<-count.multiple(g)
12. g<-simplify(g,remove.multiple = TRUE,
13. remove.loops = TRUE,edge.attr.comb = "mean")
14. }
15. g
16. }

这个函数有这么几个参数：

data,是两列关系数据，前面已经讲过了，只能两列，而且要同等长度；

dir，逻辑值，T代表有向图，F无向图；

rem.multi，逻辑，T删除重复变量并更新线权重weight，F不删除并且线权重为1。 使用方法直接init.igraph(data，dir=T,rem.multi=T)即可。

2、文本型数据

一般数据结构都可以套用上面的函数，包括平行关系型的有向、无向；文本型。其中对于文本矩阵型数据还有一个办法，参考于统计词画番外篇（一）：谁共我，醉明月？

利用igragh包中的graph_from_adjacency_matrix函数。

1. adjm <- matrix(sample(0:1, 100, replace=TRUE, prob=c(0.9,0.1)), nc=10)
2. g1 <- graph_from_adjacency_matrix( adjm ,weighted=TRUE,mode="undirected")
4. ## 给稀疏矩阵行列进行命名
5. rownames(adjm) <- sample(letters, nrow(adjm))
6. colnames(adjm) <- seq(ncol(adjm))
7. g10 <- graph_from_adjacency_matrix(adjm, weighted=TRUE, add.rownames="row",add.colnames="col")

代码解读：adjm是随便构造的一个矩阵，函数；

graph_from_adjacency_matrix中，

weighted=TRUE，是否需要加入权重； mode有directed, undirected, upper, lower, max, min, plus有这么几种，min代表把无向图中，只选取最小数字的线（1,1）与（1,2）只选择（1,1）。具体请参看函数官方解释。

add.rownames以及add.colnames，因为前面的自编译函数init.igraph可以自定义标签，这里定义名称，可以用add.rownames加入标签列，这样你可以用V（g10）$row以及V（g10）$col直接看到标签。其中还可以自己定义名字，row，col都是笔者自己定义的。

三、一些基本操作

关系网络中，每一个点的信息存放在V中，每一个线的信息存放在E中。并且通过自编译的init.igraph函数，V（g）$label以及E(g)$weight都是自带的属性。

可以生成一个空的关系网络。

并且关系网络生成之后，R里面就不是用真实的名字来做连接，是采用编号的。例如（小明-小红）是好朋友，在R里面就显示为（1-2），所以需要单独把名字属性加到序号上。

1. g<-graph.empty(directed=F)

1、关系网络中的点集V

点集就是网络中所有的点，如有向文本型那个数据格式，包括了14个点；7条线。

（1）点集属性

点集与数据框的操作很相似，属性是可以自己赋上去的，比如V（g）$label就是赋上去的，你还可以给点集加上颜色（V(g)$color）、加上每个点的尺寸(V(g)$size)，加上分类（V(g)$member）

点集的选择跟数据框操作一样，比如我要选择群落为1的点集，就是V(g)[which(V(g)$member==1)]

比如我要选择点度数大于1的点集，V(g)[degree(g)>1]

如果我想知道一下这两个点之间是否有关系，可以用edge.connectivit函数，edge.connectivity(g, 4,9) 代表着第四个点与第九个点之间是否有连接关系。返回的0/1。0是没有线，1代表有线。

（2）点集加减操作

我想在原来的基础上加入一些点，用add.vertices

1. g<-add.vertices(g,length(labels))#关系网络中加入“点”

如果我想减去点度数为0的点

1. g<-g-V(g)[degree(g)==0]

（3）相邻点的集合——neighbors（很重要）

1. neighbors(g.zn,v=which(V(g.zn)$label=="会计"))
2. V(g.zn)$label[neighbors(g.zn,v=which(V(g.zn)$label=="取向"),mode="total")]
3. #默认mode设置是out，还有 in,total；其中V(g.zn)$label和V(g.zn)一个返回标签，一个返回值

eighbors可以找出标签如果是“会计”的点，与之有关系的点的序号是啥；不过你也可以通过V（g.zn）$label让临近点的标签一起筛选出来

其中mode代表点出度（out）以及点入度（in），还有两个都有的点度（total）。 该函数可以对于点集，做附近的画像，比较好用。

2、关系网络中的线集E

（1）线集的类型

关系网络中线的关系比较多，loop线就是循环到自己的点，1-2-1；multiple代表线的重叠。

1. which_loop(g) #线是否能够指回自己，1-1就是指回自己
2. which_multiple(g) #是否有重复线，后面1-1与前面1-1重复了

（2）线集属性

线的属性中，自编译函数能够拿到线权重，E(g)$weight。但是没有标签项，这时候需要用set_vertex_attr加入线标签。

1. g<-set_vertex_attr(g,"name",value=V(g)$label)

原理就是把点集的标签，打到线集上来，name是默认的设置。 线集的属性中也可以跟数据集一样进行筛选操作。

1. temp<-E(g)[order(E(g)$weight>25000)]

（3）线集加减

线集的加减可以用add.edges以及-来实现

1. g<-add.edges(g,t(edges)) #edges需要先转置
2. g<-g-E(g)[(weight>1)] #删除部分线

其中需要注意，add.edges中，需要把列数据，转置为行数据，平放id与词条。

同时线集也会有重复性的问题，见下文count.multiple(g) 以及simplify函数。

还有一些特别的函数，diameter(g)可以做到最长的链接经过了多少根线。

4、关系网络的重复性问题

在关系网络中，重复是常见的，而且无向线中1-2与2-1是重复的，重复线的数量也可以作为线的权重。也就是E（g）$weight。其中igrarh包中笔者看到两个函数跟重复性问题有关。count.multiple(g) 以及simplify函数。

（1）count.multiple(g) 函数

可以获得网络中线的重复情况。不重复是1，重复一次+1。比如：无向网络（1-2,2-3，2-1）就是（2，1，2）

等价于E（g）$weight

（2）simplify函数

函数常规式:simplify(g,remove.multiple = TRUE,remove.loops = TRUE,edge.attr.comb = "mean")

其中loops是指是否循环回自己，比如1-2-1就是一个循环到自己；multiple是指重复比如1-2,2-1。

1. h <- graph( c(1,2,1,2,3,3,2,1,4,4) );h
2. is_simple(h)
3. simplify(h, remove.loops=FALSE) #线重复，删除a->b,a->b删掉
4. simplify(h, remove.loops=TRUE) #在线方向性重复基础上删掉点重复，a->a,b->b
5. simplify(h, remove.multiple=FALSE)#删掉点重复
6. simplify(h, remove.multiple=TRUE)#删掉点重复同时，删除线a->b,a->b
7. simplify(h, remove.multiple=TRUE,remove.loops=TRUE) #删掉线重复、点重复

simplify函数识别了两种重复方式，一种是线重复，比如1-2,2-1,；一种是点重复比如1-1,2-2就是点重复。

remove.multiple=TRUE，把重复的线删除 edge.attr.comb,使用重复次数来更新线权重E(g)$weight

SNA社会关系网络分析中，关键的就是通过一些指标的衡量来评价网络结构稳定性、集中趋势等。主要有中心度以及中心势两大类指标。

以下的代码都是igraph包中的。

中心度指标的对比

一、中心度

中心度指标有四类点度中心度、接近中心度、中间中心度、特征向量中心度。

1、点度中心度——点出度、点入度、相对点中心度、点度频率

有两个部分：绝对中心度+相对中心度。是最基本的概念，就是在某个点上，有多少条线。比如以下这个数列，“小明”这个点，有三个度（小明-小红，小白-小明，小明-小胖）。

绝对中心度中，在有向图中还有点出度、点入度之分。比如“小明”这个点，有两个点出度（小明-小红，小明-小胖）；一个点入度（小白-小明）。

相对点中心度中，相对点中心度=绝对点中心度/最大度数（可以作为不同网络结构的比较，相对数与绝对数的区别），此时小明的相对点中心度就是3/3=1。

id1 di2 小明 小红 小张 小白 小红 小胖 小胖 小蓝 小白 小明 小白 小张 小明 小胖

1. degree(g,mode="in") #mode=in点入度；out=点出度；total点度中心度，三者统称绝对点中心度
2. degree(g,normalized = T) #相对点中心度=绝对点中心度/最大度数（可以作为不同网络结构的比较，相对数与绝对数的区别）

代码解读：Mode是点入度、点出度的区别；normallized=T是计算相对点中心度。

1. degree.distribution(g)

点度频率每种点度数的个数/所有点个数（比如（1,2,4,4）点度数分别为1,1,0,2，密度是1/4，1/4,0/4,2/4）。

点度频率跟相对点中心度有一定的相似性，相对来说，点度频率、相对数比绝对数更好，因为相对数可以跨越不同网络进行比较。实战中，点度频率以及相对数中心度比较有用。

2、接近中心度——点出度、点入度、相对接近中心度

该点与网络中其他点距离之和的倒数，越大说明越在中心，越能够很快到达其他点。与点度中心度不同的是，点度更强调某点的相对价值；而接近中心度是某点在网络的价值。

在g的1-2 2-1 3-4中，点2的接近中心度为1/（1+4+4）（1为2与1的距离，4为2到3的距离，因为没有指向3的，所以用网络点的总数量）

1. closeness(g,vids=which(V(g)$label=="c")) #某点四周的接近中心度，mode="out"是有向图，默认是无向图为in
2. #设置normalized = T为相对接近中心度

与点度中心度一样，有出度、入度还有相对中心度之分。

3、中间中心度——点的中心度以及线的中心度

中心度可以说明，哪些点、线中介效应最强。

（1）点的中心度——betweenness

点的中心度，代表最短距离是否都经过该点，如果都经过说明这个点很重要。也是强调点与网络的价值，而且更能说明转发、中介的情况。

1. betweenness(g,normalized = T)
2. #normalized = T代表相对数，默认值为F为绝对值
3. #mode有Out和in分别代表有向和无向

点的中心度也有点出、点入以及相对数情况。

这里可以看到某点的中间中心度，某点betweenness(g,V(g)$label=="c") 同时igraph包在操作过程中，会返回所有点的中心度，比如（1,2,4,5）则会返回5个数字，没有的3也会有位置。

（2）线的中间中心度——edge.betweenness

1. edge.betweenness(g)
2. #normalized = T代表相对数，默认值为F为绝对值
3. #mode有Out和in分别代表有向和无向

如果你要返回某条线的中间中心度，edge.betweenness(g,e=E(g,path=c(which(V(g)$label=="a"),which(V(g)$label=="c"))))，e就代表起点，终点的线。

4、点的特征向量中心度——evcent

如果某人四周都是大牛人，那么这个人也很牛逼，这个方法是根据相邻点的重要性来衡量该点的价值。首先计算邻接矩阵，然后计算邻接矩阵的特征向量。

1. evcent(g,scale = F)$vector #系统不论是否重要，都会计算所有点四周的相邻矩阵，根据矩阵求得点的特征向量，耗时巨大
2. #scale=F没有归一化，T代表输出数据进行标准化
3. #mode有Out和in分别代表有向和无向

该函数会计算所有点的相邻矩阵，所以耗时巨大。算法原理中的，如果计算邻接矩阵，每个邻接点的权重笔者还不是很能看懂。。。

同时，scale=T，可以将输出的数据归一化。

另外一个机遇特征向量中心度的指标是：page.rank特征向量中心度。这个是谷歌开发的，对于一些搜索的竞价排名做的指标。原理跟特征向量中心度差不多：

计算邻接矩阵——按行标准化——计算矩阵的特征向量。

1. page.rank(g,scale=F)$vector
2. #scale=F没有归一化，T代表输出数据进行标准化
3. #mode有Out和in分别代表有向和无向

二、中心势

中心度都是在说点-点，点-网络。如果单论网络的话，有哪些指标呢？ 用中心势来表示。前叙述的三个中心度指标都可以分别打造一款中心势。

中心势的原理就是比较一个网络的边缘点以及中心点的中心度的情况，

如果一个网络很集中，那么势必是中心点，中心度高；而边缘点中心度低。

如果一个网络很稀疏，那么中心点、边缘点的中心度没有多少差异。

这边笔者么有看到太多的关于中心势的指标，在这从网络中找到了这两个：网络聚类系数、网络密度。

1、网络聚类系数——transitivity

按照图形理论，聚集系数是表示一个图形中节点聚集程度的系数，一个网络一个值。

1. transitivity(g)

可以衡量网络中关联性如何，值越大代表交互关系越大。说明网络越复杂，越能放在一块儿，聚类。 比如c(1,2,2,3,3,1)=1；c(1,2,2,3,3,1,1,4,4,3)=0.75，他是衡量是否有loop，能否找到循环到自己的线，三元组。

2、网络密度——graph.density

跟网路聚类系数差不多，也是用来形容网络的结构复杂程度。越大，说明网络越复杂，说明网络越能够放在一块。

1. graph.density(g.zn)
2. graph.density(group1)
3. graph.density(group2)
4. #从中可以看到不同社群与整体之间的网络密度情况（关联程度）

以上两个汉字表，都是比较好的用来描述社群划分是否合理的指标，社群之中的密度越大，三元组聚类系数越多，越好。

社群划分跟聚类差不多，参照《R语言与网站分析》第九章，社群结构特点：社群内边密度要高于社群间边密度，社群内部连接相对紧密，各个社群之间连接相对稀疏。

社群发现有五种模型：点连接、随机游走、自旋玻璃、中间中心度、标签发现。

评价社群三个指标：模块化指标Q、网络聚类系数、网络密度。

画图有三种方法：直接plot、书中自编译函数、SVG。

不同社群划分模型的区别

一、社群发现模型

1、基于点连接的社群发现——clusters

如果一个点与社群有联系则放在一个网络中，简单易懂，耗时短，但是分类效果并不特别好。

1. clusters(g.dir,mode="weak")

mode是用来选择强关联还是弱关联，weak or strong.

2、随机游走的社群发现

1. member<-walktrap.community(g.undir,weights=E(g)$weight,step=4)

weight代表线权重，默认就是E(g)$label;step代表游走步长，越大代表分类越粗糙，分类类别越小。默认为4.

3、自旋玻璃社群发现

1. member<-spinglass.community(g.undir,weights=E(g.undir)$weight,spins=2)
2. #需要设置参数weights，因为无默认值

weight代表线权重，但是与随机游走不同，其要自己赋上去，weight=E(g)$label不能少;spins代表产生的社群数，默认值为25。 这个社群分类函数有了自己定义分类数量的效果。

4、中间中心度社群发现

1. member<-edge.betweenness.community(g.undir,weight=E(g)$weight,directed=F)

有默认的线权重，并且默认是无向线的，directed=T时就代表有向线。

5、传播标签社群发现

1. #社群发现方法五：标签传播社群发现
2. member<-label.propagation.community(g.undir,weights=V(g.undir)$weight)
3. V(g.undir)$member
4. member<-label.propagation.community(g.undir,weights = E(g.undir)$weight,initial = c(1,1,-1,-1,2,-1,1))
5. V(g.undir)$member
6. member<-label.propagation.community(g.undir,weights = E(g.undir)$weight,
7. initial = c(1,1,-1,-1,2,-1,1),fixed=c(T,F,F,F,F,F,T))

initial是社群初始化函数，默认为-1（不设置初始值），当然这里你也可以设置；如initial=c(1,1,-1,-1,2)就代表1,2个数为社群1；3、4不设置初始值；5个为社群2 fixed是用来固定函数的，当然如果没有设定初始值，如3.4.6则T，F都无效；如果设定了初始值，T则代表固定在原设定上。

二、衡量社群的指标

1、模块化指标Q——modularity

相当于是组内误差。

1. modularity(g.undir,membership=c(1,1,1,2,2,2,2)) #社群总差异，membership设置社群号

membership是每个点的各自分组情况。

2、网络聚类系数——transitivity

按照图形理论，聚集系数是表示一个图形中节点聚集程度的系数，一个网络一个值。

1. transitivity(g)

可以衡量网络中关联性如何，值越大代表交互关系越大。说明网络越复杂，越能放在一块儿，聚类。 比如c(1,2,2,3,3,1)=1；c(1,2,2,3,3,1,1,4,4,3)=0.75，他是衡量是否有loop，能否找到循环到自己的线，三元组。

3、网络密度——graph.density

跟网路聚类系数差不多，也是用来形容网络的结构复杂程度。越大，说明网络越复杂，说明网络越能够放在一块。

1. graph.density(g.zn)
2. graph.density(group1)
3. graph.density(group2)
4. #从中可以看到不同社群与整体之间的网络密度情况（关联程度）

三、画 图

由于关系网络图很复杂，而且数据量一大，小的图片形式网路图基本就是一坨浆糊。所以这里JPEG一定要足够大，最好的就是SVG格式。SVG格式的好处就是矢量图，你可以自己放大缩小，而且还可以用工具进行修改。但是最不好就是，一般的工具还打开不了，要用一些特有的工具，打开之后也会出现一些问题。

当然你是可以直接plot的。

1、直接plot

1. plot(g.test,layout=layout.fruchterman.reingold,edge.arrow.size=0.1,vertex.color=rainbow(7,alpha=0.3),edge.arrow.mode = "-")

代码解读：edge.arrow.size=0.1箭头大小；

vertex.color=rainbow(7,alpha=0.3)颜色，七种；

edge.arrow.mode = "-"连接方式用-。

其中还有很多参数类型：

1. #vertex.size=1表示节点的大小
2. #layout表示布局方式（发散性）
3. #vertex.label=NA,不显示任何点信息，默认显示idx号
4. #vertex.color=V(g)$color 点的颜色设置
5. #mark.groups表示设置分组
6. #vertex.shape='none'不带边框
7. #vertex.label.cex=1.5, #节点字体大小
8. #vertex.label.color='red'
9. #edge.arrow.size=0.7 #连线的箭头的大小
10. #edge.color = grey(0.5)#线的颜色
11. #edge.arrow.mode = "-" 箭头换成线
12. #vertex.label.dist=5 点标签和节点之间的距离一般0.1，便于错开重叠

2、简易画图自编译函数

R语言与网站分析中还专门写了一个画图函数。

1. plot.membership<-function(graph,membership,main=""){
2. V(graph)$member<-membership
3. mem.col<-rainbow(length(unique(membership)),alpha=0.3)
4. V(graph)$color<-mem.col[membership]
5. plot(graph,edge.width=E(graph)$weight,vertex.color=V(graph)$color,main=main)
6. }

函数需要输入三样东西（关系网络，分组情况，标题）。这里借助上面的社群分类都是可以得到的。用点连接来举个例子：

1. plot.membership(g.undir,clusters(g.undir)$membership,"无向图的社群发现")

3、SVG如何画高质量图

画一个好看的图你需要考虑这么几个问题：

不同重要性的点是否需要不同的大小？——V(g)$size

重要的点是否要加入其名字标签？——V(g)$label

不同社群的点，是否需要不同的颜色？——V(g)$member

（1）设置点大小

1. V(gg)$size = 5
2. V(gg)[degree(g)>=3000]$size = 15

其他节点尺寸都是5，而点度数大于3000的节点尺寸是15；

（2）设置不同社群颜色

1. mem.col<-rainbow(length(unique(V(g)$member)),alpha = 0.3)
2. V(g)$color<-mem.col[V(g)$member]

rainbow是生成颜色的参数，比如"#FF00004D" "#00FFFF4D" 第二句话是将每个点附上颜色。

（3）设置重点词标签

1. V(g)$label=NA
2. V(g)[degree(g)>=3000]$label=V(gg)[degree(g)>=3000]$name

非重点词不给标签，重点词点度大于3000的给标签名字。

最后的SVG画图函数就是：

1. svg(filename=paste("C:/Users/long/Desktop","/1.svg",sep = ""),width = 40,height = 40)
2. plot(data.g,layout=layout.fruchterman.reingold,vertex.color=V(g)$color,vertex.label=V(g)$label,<span style="font-family: Arial, Helvetica, sans-serif;">vertex.size=V(g)$size</span>)
3. dev.off()

其中layout.fruchterman.reingold是发散式的布局方式。

打开SVG可以用adobe illustrator,而且也可以修改，就是笔者遇到的问题是，图中会出现很多问题。