iGraph——图挖掘助力社会网络分析

社交网络（如Facebook，Twitter）可以完整地表现人们的生活。人们用不同的方式与他人互动，并且这些信息都可以在社交网络中抓取到。挖掘某个站点的有用信息可以帮助一些团体增加竞争力。

我最近无意中发现一款叫做“iGraph”的工具，它提供了一些非常有效的挖掘功能。以下列举几条我觉得有意思的：

创建图表

图表由节点和连线组成，两者都可以附上一系列属性值（键/值对）。此外，连线可以是有向的也可以是无向的，还可以给它加上权重。

> library(igraph)  # Create a directed graph g <- graphc(0,1 23),0)"> directed=T g Vertices:4 EdgesDirected TRUE []0->123 # Create a directed graph using adjacency matrix m  matrixrunif4* nrow=[,]0.40863890.21609240.15579890.28962390.46694560.10710710.12906730.37158090.20316780.39116910.59062730.74177640.88081190.76874930.97343230.4487252.adjacencym 0.55 plotg layoutlayoutfruchtermanreingold>

iGraph也提供了多种创建各种图形的图表的简单方法

 #Create a full graph g1 full g1 6 FALSE --5 #Create a ring graph g2 ring g2  #Combine 2 graphs%du79678differenceF)) # Create a latticelattice # Create a treetree12 childreng1g2tilford)

iGraph还提供了另外两种图表生成的机制。“随机图表”可以在任意两个节点之间进行连线。而“优先连接”会给已经拥有较大度数的节点再增加连线（也就是多者更多）。

# Generate random graph,fixed probability erdosrenyigame200.3 vertexlabelNAsize # Generate random graph,fixed number of arcs15 type='gnm' # Generate preferential attachment graph barabasi60 power zeroappeal1.3 
 简单图表算法
 
 这一节会介绍如何使用iGraph来实现一些简单的图表算法。
 
 最小生成树算法可以在图表里连接所有的节点，并使所有的连线权重最小。
 
# Create the graph and assign random edge weights0.35 E$weight  roundlengthE))),0)">*50 edge$weight # Compute the minimum spanning tree mst  minimumspanningmst 
 连通分支算法可以找到会连通其他节点的连接，也就是说，两个节点之间的路径会穿过其他节点。需要注意的是，在无向图里连通是要对称的，在有向图（节点A指向节点B，但节点B不指向节点A的图表）里不是必须的。因此在有向图中存在一种连接的概念叫做“强”，也就是只有两个节点都分别指向对方才意味着它们是连通的。“弱”的连接意味着它们不是连通的。
 
91011 # Nodes reachable from node4 subcomponent mode"out"8 # Nodes who can reach node4"in" clusters"weak" $membership  $csize  $no  myc "strong" myc $membership  mycolor  c('green' 'yellow''red''skyblue' V$color  mycolor[myc$membership + 最短路径算法是最普遍的算法，它能找到节点A和节点B之间最短的路径。在iGraph里，如果图表是未加权的（也就是权重为1的）而且在权重为正时使用了迪杰斯特拉算法，会使用“breath-first search”算法。要是连线的权重是负数，则会使用Bellman-ford算法。
 
0.25 pa  getshortestpaths)[[]])[pa'green''grey' path'red'$width  
 
 图表统计
 
 通过大量统计信息我们可以大致看到图表的形状。在最高权限下，我们可以看到图表的各类信息，它包括:
 - 图表的大小（节点和连线的数量）
 - 图表的密度是紧密的（|E|与|V|的平方成正比）还是稀疏的（|E|与|V|成正比）?
 - 图表是连通的（大部分节点是互通的）还是非连通的（节点是孤立的）？
 - 图表中最长的两点之间距离
 - 有向图的对称性
 - 出/入“度”的分布
 
 # Create a random graph 2000.01 # No of nodes lengthV200 # No of edges197 # Density (No of edges / possible edges)density0.009899497 # Number of islands$no 34 # Global cluster coefficient: #(close triplets/all triplets) transitivity"global"0.015 # Edge connectivity,0 since graph is disconnectedconnectivity # Same as graph adhesionadhesion # Diameter of the graph diameter18 # Reciprocity of the graph reciprocity degreedistribution0.1350.2800.3150.1100.0950.0500.0050.010degree xlab"node degree" lines))
 
 
 往下一点，我们也可以看到每对节点的统计信息，比如:
 - 计算两点之间没有公用连线的路径（也就是需要移除多少条连线可以使两节点不连通）
 - 计算两点之间的最短路径
 - 计算两点之间路径的数量和长度
 
 # Create a random graph # Compute the shortest path matrix shortest # Compute the connectivity matrix M rep81fori in:{j ifi == j Mi+-}else i 
 
 
 
 中心性计算
 
 在细节方面，我们可以看到各个节点的统计信息。根据这些数字可以测出节点的“中心性”
 - 拥有较高出/入度数的节点也拥有较高的“度中心性”
 - 与其他节点之间有短路径的节点拥有较高的“密集中心性”
 - 与其他节点对之间有最短路径的节点拥有较高的“中间性”
 - 连接了许多中心性较高节点的节点拥有较高的“特征向量中心性”
 - 本地簇系数意味着相邻节点的互联性
 
 # Degree # Closeness (inverse of average dist) closeness0.44444440.53333330.50000000.61538460.8000000 # Betweenness betweenness0.83333332.33333330.00000006.333333318.8333333 # Local cluster coefficient"local"1.00000000.66666670.1333333 # Eigenvector centrality evcent$vector 0.30198570.41971530.53812940.66931420.5170651 # Now rank them orderclosenessbetweennessevcent$vector9
 
 从中Drew Conway发现拥有低“特征向量中心性”和高“中间性”的人是很重要的联系人，而拥有高“特征向量中心性”和低“中间性”的人与重要的人有关联。现在我们来绘制“特征向量中心性”和“中间性”的图表。
 
 # Create a graph100u lay  # Plot the eigevector and betweenness centrality text cex0.6 pos)[laycex