复杂网络学习笔记

关于【数据分析小组】的事宜请见文末。

最近在撸复杂网络，刚刚入门，把总结的一些信息跟大家分享一下：

一、什么是复杂网络

复杂网络就是比较复杂的网络（-_-!!），比如人际关系网：

（我也不知道什么电视剧，没看过）

交通网络：

生物基因网络：

（图片来自东南大学，“乳腺癌发生发展及其分型中的基因调控网络特征”，http://ils.seu.edu.cn/d9/bb/c12282a121275/page.htm）

等等。

二、复杂网络的应用场景

1. 社交平台“引荐”功能

很多社交网站上都开通了“引荐”功能，如果你想认识某个大牛，网站会根据你的社交网络给你推荐一条“路径”：

（Linkedin上的引荐功能）

2. 搜索推荐

在百度或者谷歌上搜索人名，右边都会给你推荐一些相关的信息，此为“知识图谱”。早在2012年的时候，谷歌就发布了这个“知识图谱”，为用户提供有完整知识体系的搜索结果。

知识图谱：把所有不同种类的信息连接在一起而得到的一个关系网络。知识图谱提供了从“关系”角度去分析问题的能力。

3. 反欺诈

基于知识图谱的复杂网络同样也应用于银行的反欺诈。其中最难也是最重要的一点就是把不同来源的数据整合在一起。比如，把一个借款者相关的所有数据，比如消费记录、行为记录、网络浏览记录、人际关系等数据整合到知识图谱网络中，用以对该借款者的欺诈行为进行检测。

这个例子来源于“普惠大数据中心”：

（图来源于“普惠大数据中心”）

如果借款人张三和李四填了同一个电话，但是公司完全不一样，这就成了一个风险点，需要审核人员的注意。

（图来源于“普惠大数据中心”）

如果在一段时间之后，知识图谱的结构发生了很大的变化，就可能存在异常，需要进一步的关注。

此外，复杂网络在生物基因、产业链管理、交通系统、移动通信中都有重要的应用，就不一一列举了。

三、简单入门

1. 网络基本元素

通常用G来表示网络，网络的基本元素是节点V和边E：

G = （V，E）

• 如果网络中的边是有方向的，则称为有向图：

该图表示为：

G = （V，E） 顶点集合：V = {a, b} 边集合：E = {<a,b>, <b,a>}

注意边集合中，<a, b>是用尖括号表示的，因为这是有方向的，也因此<a, b>与<b, a>是两条不同的线。

• 如果网络中的边是无方向的，则称为无向图：

该图表示为：

G = （V，E） 顶点集合：V = {a, b} 边集合：E = {(a, b)}

因为a到b是没有方向的，故用圆括号表示，且(a, b) = (b, a)

2. 网络的统计特征

通常用几个特征来描述网络。

• 度

与某个节点i相连接的、其他节点的数目，叫做这个节点的度，表示为ki。一个节点的度越大，就意味着这个节点越重要。

一个网络的度，就是该网络中所有节点的度的平均值，记作<k>。

• 聚类系数（簇系数）

某节点i的度为ki，也就是该节点有ki个邻集，那么该节点的聚类系数Ci就定义为这ki个节点之间存在的边数Ei，与总的可能的边数ki(ki-1)/2之比：

Ci = 2 * Ei / ki * (ki-1)

它反应了节点i与邻点间关系密切程度。

一个网络的聚类系数C，就是该网络所有节点聚类系数的平均值。网络节点间的密切程度，体现了网络的凝聚力。

下面这个图，a的度为3，a的聚类系数为1/3。

下面这个图a的聚类系数为1。

• 最短路径

两个节点（m,n）之间边数最少的路径称为最短路径，最短路径的长度则为这两个点的距离d(m,n)。

• 平均路径长度

平均路径长度是所有节点对之间的距离的平均值。

N为所有节点个数，仍以这个图为例：

d(a,b) = 1; d(a, d) = 1; d(a, b) = 1; d(b, c) = 2; d(b, d) = 1; d(c, d) = 2

→

L = 8 * 2 / 4 * 3 = 16 / 12 = 1.33

有研究发现，很多庞大复杂的网络，其平均路径长度却出乎意料非常的小，这也被称为小世界效应。

• 介数

网络中通过某点的最短路径的条数称为点介数；网络中通过某边的最短路径的条数称为边介数。

介数反应了节点或者边的作用和影响力，介数越大，说明经过该点（边）的最短路径越多，传播的信息量就越大，但也容易发生阻塞。

网络中所有节点（边）的平均介数，称为网络点介数（边介数）。

3. 复杂网络模型

简单介绍几个网络模型。

• 规则网络

规则网络具有很强的规则性，每一个节点与边的关系是固定的。

• 随机网络

节点确定，边以概率p任意连接；或节点不确定，点边关系也不确定。

• ER网络

给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。

• 小世界网络

1967年，美国社会学家米尔格伦在一系列社会调查后得出，世界上任意2个人的平均距离是6，被称为“六度分离”理论。（真有这个理论！）

Watts和Strogatz提出了一个新模型，通常称为“小世界网络模型”（WS模型）。该模型始于一个具有N个节点的一堆网络，网络节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接，约束条件为节点间无重边，无自环。

（这几个网络模型我都还没有搞明白，先挖个坑，以后再填）

• 无标度网络

在现实世界的网络中，少数的节点往往拥有大量的连接，而大部分节点却很少，网络缺乏一个特征值（或平均度值），即节点值的波动范围相当大。

四、工具推荐

推荐NetworkX，一个Python语言开发的复杂网络建模工具。可以满足常用的复杂网络分析方法，正在撸，求交流。