网络科学课程

写给《图像处理与模式识别研究所》的话:

你总是要先扛过沮丧的今天,才有真实可期的明天.成年人的世界向来没有容易二字.总有一个时刻,在你或长或短的生命里,一定至少有一个夜晚,你站在窗前,看着窗外的世界,觉得无比沮丧,但是你可以选择拥抱光明,允许自己有沮丧和疲惫的权利,但不忘保持战斗力.嘴上喊着丧,却没有停止脚步,唯有化沮丧为力量,坚持向前走,才能将今日的丧,蜕变成明日的喜.这就是平凡如你的不平凡之处.

1.理论

(1).个人介绍

为什么网络科学对我很重要？

博士工作（2000-2004）:

• 收集网页
• 描述国家网络域
• 智利,韩国,希腊,西班牙...

（对我）有影响的书:

这本书于2002年出版,让我看到了世界各地的网络;这本书读起来很容易,面向大众,强烈推荐.

Barabási在某个时候访问了我在智利的大学!

我在top.es领域的工作（~2006）:

博士后工作（2005-2009）:

• 网页垃圾邮件

-为欺骗搜索引擎而创建的页面

-用关键词来吸引流量

-增加其他页面的链接分数

-方法一直在进化,如何把握它们?

致Eureka!等等(2006):

我使用gnuplot可视化带注释的数据集,黑色:垃圾邮件,它们聚集在一起!

查询流(2008):

我们想知道在另一个查询之前或之后最有可能的查询是什么?它们是如何联系在一起的?这就是我们开发查询流图的方法.

我自己作品中的图表:

• 描述国家网络域
• 查找网页垃圾邮件
• 向搜索者建议查询
• ...
• 目前:

-更大工具箱的一部分

-对仅限于结构的结论持怀疑态度

(2).复杂网络示例

参考资料：

Albert László Barabási: Network Science. Cambridge University Press, 2016.

Filippo Menczer, Santo Fortunato, and Clayton A. Davis. A First Course in Network Science. Cambridge University Press, 2020.

• 维基百科定义:

网络科学是一个研究复杂网络的学术领域，如

-电信网络、计算机网络、生物网络、认知和语义网络以及社交网络.

• 考虑到:

-不同的元素和演员代表的节点

-元素或角色之间的联系，如连接。

复杂系统：

• 许多相互连接的部件
• 复杂的连接布局
• 新兴的属性

每一个复杂的系统背后都有一个复杂的网络：

• 大脑神经元之间的联系
• 基因与蛋白质的相互作用
• 人类和非人类动物的家庭/友谊联系
• 电信、电力基础设施
• 商业/贸易网络

人脑:

人脑中的区域：

基因网络:

本图中| V |=500基因的共表达

人类疾病网络：

Moreno的社会图：

• 20世纪30年代初
• 二年级儿童
• 你想和谁坐在一起？
• 颜色和大小:入度

Zachary的空手道俱乐部:

分成两个俱乐部的空手道俱乐部（以1和34为首）.

新西兰峡湾里的海豚：

• 跟踪野生海豚群的研究（2003）
• 寻找海豚一起游泳
• 发现了长期的联系；对其他非人类动物（如绵羊）进行重复性研究

感情链:

• 21世纪初
• 高中阶段的青少年
• 过去18个月的“特殊浪漫关系”或“非浪漫性关系”

1000名索马里Facebook用户：

40万Twitter用户:

练习:

• 查找网络示例，只需指出：

-名字

-节点数（大约）

-边数（大约）

• 要记住的东西

-定义：复杂系统，复杂网络

-复杂网络示例

(3).网络科学应用

参考资料：

Albert László Barabási: Network Science. Cambridge University Press, 2016.

Filippo Menczer, Santo Fortunato, and Clayton A. Davis. A First Course in Network Science. Cambridge University Press, 2020.

复杂网络有什么共同点？为什么这些规则是相关的？你怎么知道它们是什么？

复杂网络的普适性:

"网络科学的一个重要发现是,在科学、自然和技术的各个领域中出现的网络结构彼此相似,这是由相同的组织原则支配的结果."(Barabási 2016)

网络科学的特点:

• 跨学科的；事实上，我们经常处理来自不同学科的问题
• 经验和数据驱动；它基于对网络的观察
• 定量、数学、计算

帮助打击有组织犯罪和串通:

帮助反腐:

帮助预测流行病:

帮助理解一个组织、一个社会或一个大脑:

你能用这个做什么？

• 帮助打击有组织犯罪和腐败
• 帮助预测流行病
• 帮助理解一个组织、一个社会或一个大脑
• 帮助设计新的治疗方法和药物
• ...

强烈推荐：

尼古拉斯·克里斯塔基斯

（一小时讲座）

我们将学到什么:

• 用正式的术语来描述一个网络
• 以此来确定它的性质
• 可视化不同的网络
• 以编程方式操作网络
• 找到重要节点和社区
• 发现或帮助他人发现
• 更多（在很大程度上，这取决于你！）

我们将如何学习:

• 理论课

-帮助您了解如何建模复杂的网络

-帮助您找到重要节点、社区和轨迹影响

-做一些简单的（不是那么简单的）练习来检查你是否正确地理解了每个概念，并帮助你记住

• 实践环节

-帮助您处理复杂的人际网络

-用Python管理和分析图形

• 我的重点是作为一个数据科学家我认为对你有价值的东西

总结:

要记住的东西:

• 复杂网络分析的应用

(4).图论基础

目录:

• 图形符号
• 度分布
• 邻接矩阵

参考资料：

Albert László Barabási: Network Science. Cambridge University Press, 2016.

克尼斯堡的七桥:

快速提问:

一个人能走过7座桥而不穿过同一座桥两次吗？

不能(由欧拉证明,1735年)

一个图有一个欧拉回路,如果图是连通的且所有节点都有偶数度;当图是连通的且所有节点都有偶数度,或只有2个节点奇数度时,图具有欧拉路径.

基本概念:

图的符号:

G = (V,E)

-V:节点或顶点

-E:连接或边缘

• |V|=N图的大小
• |E|=连接数L

典型符号变化：

• 你会发现G用(N,A)表示,这是典型的有向图,意思是“节点，弧”
• 你会发现

-|V|用n或n表示

-|E|用m、m或L表示

有向图与无向图:

• 在无向图中

-E是一个对称关系

• 在有向图中，也称为"有向图"

-E不是对称关系

我们将使用的示例图:

度:

• 节点一有ki度

-这是此节点上发生的连接数

-连接总数L由

• 平均度

在有向网络中:

• 我们区分入度和出度

-分别是传入和传出连接

• 度是两者之和

• 计算连接总数：

度分布：

• 如果有k度的Nk个节点
• 度分布:

• 平均度是

度分布；两个小图:

练习：

画出这些图的度分布:

参考答案：Google Spreadsheet

度分布,实图：

线性的规模,log-log的规模:

邻接矩阵:

什么是邻接矩阵?

• A是G=(V,E)邻接矩阵：

-A有|V|行和|V|列

-Aij=1如果(i,j)∈E

-Aij=0如果(i,j)∉E

例子:

快问:

就A而言,如何表示:

一些"图表学"...

• G是无向的⇔A是对称的
• G有一个自环⇔A在对角线中有一个非零元素
• G是完全的⇔Aij≠0(除非i=j)

总结:

要记住的东西:

多练习：画出索引、出度、度分布图,写出邻接矩阵.

(5).稀疏连接

内容:

• 度
• 稀疏性
• 双边网络
• 连通性

参考资料:

Albert László Barabási: Network Science. Cambridge University Press, 2016.

实际的网络是稀疏的:

• 理论上

• 大多数真实的网络是稀疏的，即:

L是网络中的连接数，N是网络上的节点数.

有些网络有多稀疏？

例子:

蛋白质相互作用网络(N=2K,L=3K)

例子:

海豚(N=62,L=318)

为什么网络是稀疏的？

• 从节点角度考虑不同机制：

-节点可以连接到多少项

-其中大部分连接起来是否现实？

• 在社交网络中,Dunbar号码(≃150)

例子:

Twitter中的实际朋友与Twitter中关注的人

加权网络:

• 在加权网络中，不再是

• 我们有

• 权重可能代表不同的连接强度

例子:

加权网络,欧盟葡萄酒进口(顶部)和出口(底部)

二部网络:

• 二部图是一个图
• G=(V,E)使

例子:

设计一个双边网络：

左投影：节点所在的图形是1，2，…，7和如果节点共享一个邻居，则它们是连接的.

右投影：节点所在的图形是A，B，…，D和如果节点共享一个邻居，则它们是连接的.

流行文化中的"集团"一词:

在拉丁美洲的一些地方，“clika”或“clica”是指一群亲密的朋友，有时是帮派.

路径和距离:

路径:

• 路径是E的一系列边
• 每条边的终点是下一条边的原点
• 路径的长度就是路径上的边数
• 例子:用橙色标记的路径，长度为5

连通性:

• 如果两个节点i,j之间存在路径:

-这些节点是同一连接组件的一部分

-只有一个连通分量的图称为连通图

连通图:

一个不连通图有一个邻接矩阵，它可以按对角形式块排列.

a、断开

b、连接

距离:

• 如果两个节点i,j位于同一连接组件中:

-i和j之间的距离,用dij表示,是它们之间最短路径的长度

直径:

• 网络的直径是网络上两个节点之间的最大距离dmax
• 有效直径(或有效直径-90%)是一个数d，使得90%的节点对(i,j)的距离小于d
• 平均距离<d>，并且仅对位于同一连接组件中的节点进行测量

总结:

要记住的东西:

• 定义：

-度、出度、入度

-二部图，集团

-稀疏图与稠密图

• 距离、直径、有效直径
• 连接的组件

练习:

• 图的稀疏性度量
• 计算两个节点之间的距离
• 计算图的直径
• 识别连接的组件

(6).聚类系数

内容:

• 局部聚类系数
• 全局聚类系数

参考资料:

Albert László Barabási: Network Science. Cambridge University Press, 2016.

局部聚类系数:

• 局部聚类系数Ci是节点i的一个属性
• 让Li表示节点i的邻居之间的连接数

练习:

每个节点的局部聚类系数是多少?

平均聚类系数:

• 平均聚类系数是整个图的一个性质

有时这叫做图的曲率.

总结:

要记住的东西:

• 局部和全局聚类系数

练习:

• 计算图中每个节点的局部聚类系数

(7)ER随机网络

内容:

• ER模型
• ER模型下的度分布

参考资料:

Albert László Barabási: Network Science. Cambridge University Press, 2016.

Data-Driven Social Analytics course by Vicenç Gómez and Andreas Kaltenbrunner

为什么要研究随机网络？

• 研究复杂网络的一种方法是运行网络创建的随机模型，然后观察它们是否生成看起来像真实网络的网络
• “随机网络”模型是一种特定的随机模型，其中每个连接都是随机独立创建的

在聚会上认识人：

• 你随便挑一个人
• 和那个人聊一会儿，如果有好的氛围，你们就有联系了
• 然后再挑一个人

-再重复一遍

• 结果就是我们所说的随机网络

规范化：Erdös-Rényi或ER

• 对于图中的每对节点

-用概率p进行伯努利试验

• “掷一个有倾向的硬币，它的落点概率是p”

-如果试验成功，就连接这些节点

• 如果硬币正面朝上，连接这些节点
• 对所有对重复试验

例子：

（3个网络,相同参数）

底层的节点最终被孤立了.

网络的一个重要特征：度分布:

• 网络最明显的特征之一就是它的度分布

-这个分布是不是很偏斜？或者每个节点都接近某个平均值？有“典型”的度吗？

-它看起来像网络形成模型预测的度分布吗？

• 我们将花大量时间研究不同模式下的度分布

二项分布

• 在n个独立试验中获得x成功的概率分布，其中每个试验都有p成功的概率

ER模型中的度分布:

• 简单的二项分布
• 请注意，一个节点的“成功”（连接）的最大数量为N-1，因此：

预期连接数:

• 预期连接数

• 平均度

练习:

• 考虑一个N=3000,p=10^-3的ER图

1)期望的连接数是多少？

2）平均度<k>是多少？

度分布示例:

import numpy as np
from scipy.stats import binom
from matplotlib import pyplot as plt
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus']=False
x=np.arange(0,40)
plt.figure(figsize=(8,5))
plt.bar(x,(binom(40,0.1)).pmf(x),label='Binom(40,0.1)')
plt.bar(x,(binom(40,0.3)).pmf(x),label='Binom(40,0.3)')
plt.bar(x,(binom(40,0.5)).pmf(x),label='Binom(40,0.5)')
plt.gca().legend()
plt.xlabel("40次试验成功")
plt.ylabel("概率")
plt.show()

泊松分布近似：

例子：

“写信的背后”计算:

• 假设N=7 x 10^9
• 假设<k>=1000

-一个人知道大约1000人的名字

• 则期望kmax=1185
• <k> ±σ是968到1032的范围

-这现实吗？

调查：你有多少个联系人？

真实的网络：

总结:

要记住的东西:

• ER模型
• ER模型中的度分布

练习:

• 编写代码创建ER网络
• 用N=256,p=0.25表示网络的期望边数;然后将您的解决方案与此视频中的解决方案进行比较

视频链接:https://www.youtube.com/watch?v=2DckiyysQy4

(8)随机网络的属性

内容:

• ER模型下的连通性
• ER模型下的距离
• ER模型下的聚类系数

参考资料:

Albert László Barabási: Network Science. Cambridge University Press, 2016.

Data-Driven Social Analytics course by Vicenç Gómez and Andreas Kaltenbrunner.

ER网络中的连通性:

ER网络随着<k>的增加而增加:

• 当<k>=0时：孤立
• 当<k><1时：断开
• 当<k>>1时：强连通分量
• 当<k>=N–1完全图

显然，必须有一个强连接，<k>=1，ER在1959年得到了证实.

增加p的可视化:

次临界状态:<k><1

临界点:<k>=1

超临界状态:<k>>1

关联状态:<k>>logN

大多数真实的网络都是超临界的：

小世界现象，又称"六度分离":

Milgram在1967年的实验:

• 目标：（1）马萨诸塞州波士顿的一名股票经纪人和（2）马萨诸塞州沙龙的一名学生
• 资料来源：威奇托和奥马哈的居民
• 材料：研究目的的简短摘要、一张照片、姓名、地址和目标人的信息
• 要求：将信件转发给最有可能认识目标对象的朋友、亲戚或熟人
• 296封信中有64封到达目的地

"小世界现象":

• 如果你选择地球上的任何两个人，他们之间的联系是通过一条关系密切的熟人
• 规范化

-网络中随机选择的两个节点之间的预期距离增长比其节点数增长慢得多

距离≤d的节点有多少？

在ER图中:

距离1处的节点:<k>

距离2处的节点:<k>^2

...

距离d处的节点:<k>^d

最大距离是多少？

假设:

以实验(或经验)为依据的平均值和最大距离：

近似:

• 考虑到dmax由一些较长的路径控制，而<d>是所有路径的平均值，我们通常在ER图中观察到：

练习:

进入https://oracleofbacon.org/ 找一个有名气的男演员或女演员距离相比大于Kevin 和Bacon的距离，写下演员的名字和距离

聚类系数或"朋友的朋友就是我的朋友":

• 节点i的聚类系数Ci:

-Ci=0⇒i的邻居断开连接

-Ci=1⇒i的邻居完全连接

ER图中邻域间的联系：

• 作为节点i的邻居的节点数是ki
• 作为i的邻居的不同节点对的数目为ki(ki-1)/2
• 其中任何一对节点连接的概率是p
• 那么，i的邻居之间的期望的连接是：

ER图的聚类系数:

• i的邻居之间的期望的连接是：

• 聚类系数:

在ER图中：Ci=<k>/N:

当<k>固定时,大型网络的聚类系数应较小;我们应该让<C>/<k>紧跟在1/N之后.

如果在ER图中:Ci=<k>/N

因此,节点的聚类系数应该与度无关.

因特尔:

科学家合作网、蛋白质相互作用:

ER模型是一个度分布糟糕的模型:

• 预测:

• 观察到的节点数量比预测的大

ER模型是一个很好的关于路径长度模型：

预测：

观察:

ER模型是一个聚类系数糟糕的模型:

• 预测:Ci=<k>/N

• 聚类系数随度增大而减小

为什么我们要研究ER模型？

• 起点
• 简单
• 指导性的
• 历史上很重要，只有在大数据集开始可用时才变得突出⇒与数据科学相关！

练习:

考虑ER图中N=3000,p=10^(-3),<k>≈3

1)哪一个网络是一个集团?

2)假设我们要增加N，直到只有一个连通分量

2.1)根据p和N的函数值求<k>

2.2）N应该是什么?通过试错法求解

3）如果网络有N个节点，那么<k>值是多少？

4）N个节点的预期距离<d>是多少？

练习:

• 考虑一个N=3000,p=10^(-3)的ER图

网络属于哪个集团？

假设<k>介于1和log(N)之间,网络处于超临界状态.

N只是其中的一部分的情况是什么?如何计算<k>≈logN？

平均度<k>?

节点间的平均距离?

总结:

要记住的东西:

• ER模型
• ER模型中的度分布
• ER模型中的距离分布
• ER模型中的连通集团

练习:

• 利用现有网络

-从滑动中"以实验(或经验)为依据的平均值和最大距离"

-假设它是一个ER网络

-指出网络处于哪个状态

-估计预测距离

-如果可以,与实际距离进行比较

• 编写代码创建ER网络

(9)无标度网络

内容:

• 无标度网络的特性
• 无标度网络的度分布
• 无标度网络的距离分布

参考资料:

Albert László Barabási: Network Science. Cambridge University Press, 2016.

1998年nd.edu(N=300K,L=1.5M)

网络图有随机网络没有的是什么?

• 大型"枢纽"

-具有很高的度的节点

-在随机（ER）图中不太可能出现

• 我们已经看到泊松分布在观测度分布时的一个糟糕的近似值

nd1998度分布:

在实际网络中度有一个很好的逼近:

• 对数曲线图中的直线下降的线

• 参数Ɣ是幂律的指数
• 无标度网络是一个度分布服从幂律的网络
• 泊松定律与幂律的比较

nd1998度分布:

什么样的伽马值减少了幂律的“长尾”？

插入语:Pareto

• 19世纪意大利经济学家维尔Vilfredo Pareto指出，80%的钱是由20%的人挣来的
• 最近...

-80%的网页链接指向15%的网页；

-80%的引文只给了38%的科学家；

-好莱坞80%的连接都和30%的演员有关.

• 一场仍然悬而未决的争论：1%和0.1%的人的财富

在定向网络中...

• 每个节点有两个度:kin和kout
• 一般来说,它们可能有所不同,因此

在nd1998,

(离散)形式:

这种形式假设没有阶数为零的节点.

(连续近似)形式:

kmin是在网络中发现的较小的度.

度的自然界限:

最大集线器的连接不能超过N-1个.

随机网络与无标度网络:

地面运输、航空运输

参考文献：

[1]Ricardo Baeza-Yates, Carlos Castillo y Vicente López.Características de la Web de España.