写给《图像处理与模式识别研究所》的话:
你总是要先扛过沮丧的今天,才有真实可期的明天.成年人的世界向来没有容易二字.总有一个时刻,在你或长或短的生命里,一定至少有一个夜晚,你站在窗前,看着窗外的世界,觉得无比沮丧,但是你可以选择拥抱光明,允许自己有沮丧和疲惫的权利,但不忘保持战斗力.嘴上喊着丧,却没有停止脚步,唯有化沮丧为力量,坚持向前走,才能将今日的丧,蜕变成明日的喜.这就是平凡如你的不平凡之处.
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的社会图:
Zachary的空手道俱乐部:
分成两个俱乐部的空手道俱乐部(以1和34为首).
新西兰峡湾里的海豚:
感情链:
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或n表示
-|E|用m、m或L表示
有向图与无向图:
-E是一个对称关系
-E不是对称关系
我们将使用的示例图:
网络 | |V| | |E| |
---|---|---|
Zachary的空手道俱乐部(karate.gml) | 34 | 78 |
Les Misérables(lesmiserables.gml) | 77 | 254 |
电子邮件交换(email-eu-core.csv) | 868 | 25K |
美国公司所有权 | 1351 | 6721 |
漫威漫画(hero-network.csv) | 6K | 167K |
度:
-这是此节点上发生的连接数
-连接总数L由
在有向网络中:
-分别是传入和传出连接
度分布:
度分布;两个小图:
练习:
画出这些图的度分布:
参考答案:Google Spreadsheet
度分布,实图:
线性的规模,log-log的规模:
邻接矩阵:
什么是邻接矩阵?
-A有|V|行和|V|列
-Aij=1如果(i,j)∈E
-Aij=0如果(i,j)∉E
例子:
快问:
就A而言,如何表示:
一些"图表学"...
总结:
要记住的东西:
多练习:画出索引、出度、度分布图,写出邻接矩阵.
(5).稀疏连接
内容:
参考资料:
Albert László Barabási: Network Science. Cambridge University Press, 2016.
实际的网络是稀疏的:
L是网络中的连接数,N是网络上的节点数.
有些网络有多稀疏?
网络 | |V| | |E| | Max|E| |
---|---|---|---|
Zachary的空手道俱乐部 | 34 | 78 | 561 |
Les Misérables | 77 | 254 | 2962 |
电子邮件交换 | 868 | 25K | 376K |
美国公司所有权 | 1351 | 6721 | 911K |
漫威漫画 | 6K | 167K | 17M |
例子:
蛋白质相互作用网络(N=2K,L=3K)
例子:
海豚(N=62,L=318)
为什么网络是稀疏的?
-节点可以连接到多少项
-其中大部分连接起来是否现实?
例子:
Twitter中的实际朋友与Twitter中关注的人
加权网络:
例子:
加权网络,欧盟葡萄酒进口(顶部)和出口(底部)
二部网络:
例子:
设计一个双边网络:
左投影:节点所在的图形是1,2,…,7和如果节点共享一个邻居,则它们是连接的.
右投影:节点所在的图形是A,B,…,D和如果节点共享一个邻居,则它们是连接的.
流行文化中的"集团"一词:
在拉丁美洲的一些地方,“clika”或“clica”是指一群亲密的朋友,有时是帮派.
路径和距离:
路径:
连通性:
-这些节点是同一连接组件的一部分
-只有一个连通分量的图称为连通图
连通图:
一个不连通图有一个邻接矩阵,它可以按对角形式块排列.
a、断开
b、连接
距离:
-i和j之间的距离,用dij表示,是它们之间最短路径的长度
直径:
总结:
要记住的东西:
-度、出度、入度
-二部图,集团
-稀疏图与稠密图
练习:
(6).聚类系数
内容:
参考资料:
Albert László Barabási: Network Science. Cambridge University Press, 2016.
局部聚类系数:
练习:
每个节点的局部聚类系数是多少?
平均聚类系数:
有时这叫做图的曲率.
总结:
要记住的东西:
练习:
(7)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进行伯努利试验
-如果试验成功,就连接这些节点
例子:
(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()
泊松分布近似:
例子:
“写信的背后”计算:
-一个人知道大约1000人的名字
-这现实吗?
调查:你有多少个联系人?
真实的网络:
总结:
要记住的东西:
练习:
视频链接:https://www.youtube.com/watch?v=2DckiyysQy4
(8)随机网络的属性
内容:
参考资料:
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>=1,ER在1959年得到了证实.
增加p的可视化:
次临界状态:<k><1
临界点:<k>=1
超临界状态:<k>>1
关联状态:<k>>logN
大多数真实的网络都是超临界的:
网络 | N | L | <k> | lnN |
---|---|---|---|---|
因特尔 | 192,244 | 609,066 | 6.34 | 12.17 |
电网 | 4,941 | 6,594 | 2.67 | 8.51 |
科学家合作网 | 23,133 | 94,437 | 8.08 | 10.05 |
演员合作网 | 702,388 | 29,397,908 | 83.71 | 13.46 |
蛋白质相互作用 | 2,018 | 2,930 | 2.90 | 7.61 |
小世界现象,又称"六度分离":
Milgram在1967年的实验:
"小世界现象":
-网络中随机选择的两个节点之间的预期距离增长比其节点数增长慢得多
距离≤d的节点有多少?
在ER图中:
距离1处的节点:<k>
距离2处的节点:<k>^2
...
距离d处的节点:<k>^d
最大距离是多少?
假设:
以实验(或经验)为依据的平均值和最大距离:
网络 | N | L | <k> | <d> | dmax | lnN/ln<k> |
---|---|---|---|---|---|---|
因特尔 | 192,244 | 609,066 | 6.34 | 6.98 | 26 | 6.58 |
万维网 | 325,729 | 1,497,134 | 4.60 | 11.27 | 93 | 8.31 |
电网 | 4,941 | 6,594 | 2.67 | 18.99 | 46 | 8.66 |
移动电话 | 36,595 | 91,826 | 2.51 | 11.72 | 39 | 11.42 |
邮件 | 57,194 | 103,731 | 1.81 | 5.88 | 18 | 18.4 |
科学家合作网 | 23,133 | 93,437 | 8.08 | 5.35 | 15 | 4.81 |
演员合作网 | 702,388 | 29,397,908 | 83.71 | 3.91 | 14 | 3.04 |
引用网 | 449,673 | 4,707,958 | 10.43 | 11.21 | 42 | 5.55 |
蛋白质相互作用 | 2,018 | 2,930 | 2.90 | 5.61 | 14 | 7.14 |
近似:
练习:
进入https://oracleofbacon.org/ 找一个有名气的男演员或女演员距离相比大于Kevin 和Bacon的距离,写下演员的名字和距离
聚类系数或"朋友的朋友就是我的朋友":
-Ci=0⇒i的邻居断开连接
-Ci=1⇒i的邻居完全连接
ER图中邻域间的联系:
ER图的聚类系数:
在ER图中:Ci=<k>/N:
当<k>固定时,大型网络的聚类系数应较小;我们应该让<C>/<k>紧跟在1/N之后.
如果在ER图中:Ci=<k>/N
因此,节点的聚类系数应该与度无关.
因特尔:
科学家合作网、蛋白质相互作用:
ER模型是一个度分布糟糕的模型:
ER模型是一个很好的关于路径长度模型:
预测:
观察:
ER模型是一个聚类系数糟糕的模型:
为什么我们要研究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>是多少?
练习:
网络属于哪个集团?
假设<k>介于1和log(N)之间,网络处于超临界状态.
N只是其中的一部分的情况是什么?如何计算<k>≈logN?
平均度<k>?
节点间的平均距离?
总结:
要记住的东西:
练习:
-从滑动中"以实验(或经验)为依据的平均值和最大距离"
-假设它是一个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
-80%的网页链接指向15%的网页;
-80%的引文只给了38%的科学家;
-好莱坞80%的连接都和30%的演员有关.
在定向网络中...
在nd1998,
(离散)形式:
这种形式假设没有阶数为零的节点.
(连续近似)形式:
kmin是在网络中发现的较小的度.
度的自然界限:
最大集线器的连接不能超过N-1个.
随机网络与无标度网络:
地面运输、航空运输
参考文献:
[1]Ricardo Baeza-Yates, Carlos Castillo y Vicente López.Características de la Web de España.
本文分享自 图像处理与模式识别研究所 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!