雅乐网

计算机技术、学习成长

数学 » 社团检测 » Social Network Analysis笔记1:介绍

Social Network Analysis笔记1:介绍

本系列文章是Coursera上密歇根大学的《Social Network Analysis》课的笔记。这门课现在已经不开了,课程的视频可以在这里下载:课程视频 | MOOC学院

一、介绍

社交网络可以用图(Graph)表示,它包含一系列结点和结点之间的边。

scrn20160922163155

在不同领域,结点和边会有不同的叫法:

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一起吃饭。

打开后界面如下图:

scrn20160922164748

最中间是显示图的区域,这部分左侧有一列工具,目前使用的是第三个拖拽。此时鼠标右键可以移动图,滚轮用来缩放,左键用来拖拽结点位置。

最下面的按钮,鼠标带一个问号,是编辑结点属性按钮。

scrn20160922165304

使用后选择一个结点,会在外观窗口显示结点的属性,可以进行修改。

布局(layout)

左下方的布局窗口,可以选择一个布局算法,调整参数后运行。布局就是自动调整结点的位置。我们刚打开的时候结点是随机布局的。

2016-09-22-16_58_19-gephi-0-9-1-dining-gephi

选择一个布局,点击run就可以运行。这里运行ForceAtlas 2后,大概变成了这样

scrn20160922165912

在图形的下方有一栏工具条,用来调整图的外观。

scrn20160923105219

标签也是结点的一个属性,在这个图中标签就是女孩的名字。

外观

左上方的外观窗口,可以根据结点或边的属性来设置图的外观。

scrn20160923110139

Nodes选项卡对应结点的外观,Edges对应边。

右边四个按钮分别是颜色,结点大小,标签颜色,标签大小。

Unique下面是针对所有的结点进行设置。Attribute下面就是针对结点的属性来设置(不同属性的结点或边有不同外观)。

这个图中愿意和谁吃饭,是分成了第一选择和第二选择,记录在边的属性choice中。我们选择Edges,Attribute,然后选择属性choice

scrn20160923110603

Data Laboratory面板

上面说的都是在Overview中的,这个面板用来可视化图形。Data Laboratory面板用来直接查看或修改图的数据。

scrn20160923110833

三、度和连通分支(Degree, connected components)

边(Edges)

根据边是不是有向边,可以把图分成有向(Directed)图和无向(Undirected)图。

边也会有一些属性:

weight 权重。例如人和人之间联系图中,权重可能代表联系的频率

ranking 等级。例如吃晚饭的例子中的第一选择和第二选择。

type 类型。例如多关系网络中有的边代表朋友关系,有的边代表同事关系。

还会有一些其他需要的属性。

边的权值也可能有负数,例如表示人与人的信任关系里,正数表示信任,负数可以表示不信任。

图的数据表示(物理存储)

1. 邻接矩阵(adjacency matrix)

scrn20160923111806

邻接矩阵表示图,如果从i和到j有边,那么矩阵A的元素A(i,j)=1 (有权图中等于权值)

2. 边表(Edge list)

边表每行表示一条边,格式为node1 node2 (可选的其他属性)

scrn20160923112032

3. 邻接列表(Adjacency list)

每行一个结点,然后是一个冒号,后面是这个节点指向的所有结点

scrn20160923112309

度和度的分布(Degree & Degree Distribution)

度是结点的属性,指的是一个节点连接的边的数量。

scrn20160923112541

在有向图中,度分为入度(indegree)和出度(outdegree)。一个结点的入度是指向它的边有多少个,一个结点的出度是从它出发的边有多少个。在无向图中,度就是一个节点连接的边的个数。

在邻接矩阵表示的图中,第i个结点的出度(outdegree)就看第i行有多少个1,第j个结点的入度(indegree)就看第j列有多少个1

度的序列(Degree sequence)是每个结点的度组成的有序列表:

scrn20160923152711

度的分布(Degree distribution)

是一个直方图,显示各个结点的度的分布情况

scrn20160923152817

连通分支(Connected component)

有向图中,连通分支有强连通分支和弱连通分支之分。

强连通分支中,每个结点可以通过其余所有结点通过有向边到达。

scrn20160923153209

A结点不在BCDE中是因为,从A出发不能到达其余结点。虽然从其余结点可以到达A。

弱连通分支和上面的区别是,把边都看做无向的。这样,上面的A B C D E就是一个弱连通分支。

无向图中由于边是无向的,我们通常只说连通分支。

Giant Component(规模很大的连通分支)

在很大的图中,可能分成了很多个联通分支。可能有一个连通分支包含了大部分结点(例如80%以上的结点),那这个分支称作Giant Component

scrn20160923153708

四、Gephi示例

在和谁一起吃晚饭的例子中,由于每个人选择2个愿意一起的人,每个结点的出度都是2.

这时结点的入度就很重要了,入度越多,这个人就越受欢迎。

在Gephi中,结点的度是自动计算了的。选择外观中的结点,属性选In-Degree,可以根据结点的入度设置不同的颜色

scrn20160923154215

还可以点击四个按钮中第二个,通过结点大小来区分

scrn20160923154400

这样可以方便的看出谁比较受欢迎。

要想在数据中看到结点的度的信息,可以在右下方Statistics面板,选择 Average Degree 来运行,计算每个节点的度

scrn20160923154552

运行后会显示度的分布,之后在Data Laboratory面板也可以看到结点的度的信息。

scrn20160923154836

连通分支

假设女孩愿意和她们希望一起吃饭的人分享秘密,我们想看秘密可以在多大范围内传播。

scrn20160923155048

运行后结点会有Strongly-Connected属性,然后设置不同颜色,就可以看到各个连通分支了。

scrn20160923155245

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/social_network_analysis_note_1_introduction.html

上一篇:

下一篇:

我要评论

验证码*: 0 + 0 =