本系列文章是Coursera上密歇根大学的《Social Network Analysis》课的笔记。这门课现在已经不开了,课程的视频可以在这里下载:课程视频 | MOOC学院
一、介绍
社交网络可以用图(Graph)表示,它包含一系列结点和结点之间的边。
在不同领域,结点和边会有不同的叫法:
points | lines | 领域 |
vertices | edges, arcs | math |
nodes | links | computer science |
sites | bonds | physics |
actors | ties, relations | sociology |
二、Gephi
这门课用到的3个软件
Gephi (对网络进行可视化以及计算基本的网络参数)
NetLogo (modeling network dynamics)
iGraph (for programming assignments)
其他有用的软件:Pajek, UCINet, NodeXL, NetworkX, sna package for R, SoNIA
Gephi下载地址:Gephi – The Open Graph Viz Platform
视频里的示例数据是和谁一起吃晚饭的数据:dining.gephi
这个网络中,每个结点代表一个女孩,每个女孩选择2个自己最想和她一起吃晚饭的人(分第一选择和第二选择)。图中结点A指向结点B有一条边的话,就代表A愿意和B一起吃饭。
打开后界面如下图:
最中间是显示图的区域,这部分左侧有一列工具,目前使用的是第三个拖拽。此时鼠标右键可以移动图,滚轮用来缩放,左键用来拖拽结点位置。
最下面的按钮,鼠标带一个问号,是编辑结点属性按钮。
使用后选择一个结点,会在外观窗口显示结点的属性,可以进行修改。
布局(layout)
左下方的布局窗口,可以选择一个布局算法,调整参数后运行。布局就是自动调整结点的位置。我们刚打开的时候结点是随机布局的。
选择一个布局,点击run就可以运行。这里运行ForceAtlas 2后,大概变成了这样
在图形的下方有一栏工具条,用来调整图的外观。
标签也是结点的一个属性,在这个图中标签就是女孩的名字。
外观
左上方的外观窗口,可以根据结点或边的属性来设置图的外观。
Nodes选项卡对应结点的外观,Edges对应边。
右边四个按钮分别是颜色,结点大小,标签颜色,标签大小。
Unique下面是针对所有的结点进行设置。Attribute下面就是针对结点的属性来设置(不同属性的结点或边有不同外观)。
这个图中愿意和谁吃饭,是分成了第一选择和第二选择,记录在边的属性choice中。我们选择Edges,Attribute,然后选择属性choice
Data Laboratory面板
上面说的都是在Overview中的,这个面板用来可视化图形。Data Laboratory面板用来直接查看或修改图的数据。
三、度和连通分支(Degree, connected components)
边(Edges)
根据边是不是有向边,可以把图分成有向(Directed)图和无向(Undirected)图。
边也会有一些属性:
weight 权重。例如人和人之间联系图中,权重可能代表联系的频率
ranking 等级。例如吃晚饭的例子中的第一选择和第二选择。
type 类型。例如多关系网络中有的边代表朋友关系,有的边代表同事关系。
还会有一些其他需要的属性。
边的权值也可能有负数,例如表示人与人的信任关系里,正数表示信任,负数可以表示不信任。
图的数据表示(物理存储)
1. 邻接矩阵(adjacency matrix)
邻接矩阵表示图,如果从i和到j有边,那么矩阵A的元素A(i,j)=1 (有权图中等于权值)
2. 边表(Edge list)
边表每行表示一条边,格式为node1 node2 (可选的其他属性)
3. 邻接列表(Adjacency list)
每行一个结点,然后是一个冒号,后面是这个节点指向的所有结点
度和度的分布(Degree & Degree Distribution)
度是结点的属性,指的是一个节点连接的边的数量。
在有向图中,度分为入度(indegree)和出度(outdegree)。一个结点的入度是指向它的边有多少个,一个结点的出度是从它出发的边有多少个。在无向图中,度就是一个节点连接的边的个数。
在邻接矩阵表示的图中,第i个结点的出度(outdegree)就看第i行有多少个1,第j个结点的入度(indegree)就看第j列有多少个1
度的序列(Degree sequence)是每个结点的度组成的有序列表:
度的分布(Degree distribution)
是一个直方图,显示各个结点的度的分布情况
连通分支(Connected component)
有向图中,连通分支有强连通分支和弱连通分支之分。
强连通分支中,每个结点可以通过其余所有结点通过有向边到达。
A结点不在BCDE中是因为,从A出发不能到达其余结点。虽然从其余结点可以到达A。
弱连通分支和上面的区别是,把边都看做无向的。这样,上面的A B C D E就是一个弱连通分支。
无向图中由于边是无向的,我们通常只说连通分支。
Giant Component(规模很大的连通分支)
在很大的图中,可能分成了很多个联通分支。可能有一个连通分支包含了大部分结点(例如80%以上的结点),那这个分支称作Giant Component
四、Gephi示例
在和谁一起吃晚饭的例子中,由于每个人选择2个愿意一起的人,每个结点的出度都是2.
这时结点的入度就很重要了,入度越多,这个人就越受欢迎。
在Gephi中,结点的度是自动计算了的。选择外观中的结点,属性选In-Degree,可以根据结点的入度设置不同的颜色
还可以点击四个按钮中第二个,通过结点大小来区分
这样可以方便的看出谁比较受欢迎。
要想在数据中看到结点的度的信息,可以在右下方Statistics面板,选择 Average Degree 来运行,计算每个节点的度
运行后会显示度的分布,之后在Data Laboratory面板也可以看到结点的度的信息。
连通分支
假设女孩愿意和她们希望一起吃饭的人分享秘密,我们想看秘密可以在多大范围内传播。
运行后结点会有Strongly-Connected属性,然后设置不同颜色,就可以看到各个连通分支了。