复杂网络笔记

空间上网络 很容易形成高聚集性

存在距离上三角不等式 两边之和大于 第三边

你两个邻居跟你靠近 他们彼此之间也会靠近 （因为上述）

但是并不短

现实是无标度世界。攻击那些度大的点，会有特别大的攻击性。

弱连接就有强关系
√ 找工作要找那些有过一面之缘 weak tie 因为这种人恰恰可能是桥节点；
√ 如果去找爸妈 亲密朋友 很难从小集团走出去

网络上的动力学

传染疾病模型
（1）SIR模型
Infected 感染
Suspectible 疑似
Resistant 恢复并且免疫

（2）SEIR模型
S（Susceptible）易感染状态
E（Exposed ） 潜伏期状态
I（Infected） 感染状态
R（Removed） 免疫状态
所有个体都处于易感染状态，当与感染个体接触后会变为潜伏状态，随后又将处于感染状态，个体最终将会产生免疫力，从而不再传染或被传染。

图结构：尺寸很大，把图转化成向量，给每个节点赋予一个vector ，这样一下子网络数据变的很规整，然后用神经网络等等。
Graph network
脸书上的推荐其实就是关系预测一种很重要的应用
社区检测很重要

Graph learning lifecycle
图数据
节点特征
学习算法
最终模型

特征学习 ：将图结构和节点属性映射到一个低维空间

拆开来 拼回去 怎么损失最小 ？

网络的拓扑性质： 不依赖节点的具体位置、边的具体形态 就可以表现出来的性质

网络拓扑结构发展结构：
最初100年： 认为是规则网络
19世纪50年代末： 认为是随机网络
2005年左右： 真实网络具有与前两者都不同的统计特征的网络，叫复杂网络

用矩阵描述网络

描述一个网络：最简便就是用矩阵

（1）无权无向网络

1号 跟2、4有连接，记作1；其余记作0
2号 跟1/3/4/5均有连接，记作1；其余记作0
3号只跟2有链接，第二个位置记作1
···
···

（2）无权有向网络

1号对别的没有，故全为0
2号指向1/3/4，记作1
3号没有指向别人，全0
4号指向1/2/5，记作1
5号指向2，记作1

（3）加权网络

3号指向自己，权重为1,
2号指向4号，权重为5
4号指向2号，权重为4
两个不同指的方向，权重不同。。

复杂网络研究的基本问题： 复杂网络拓扑结构的不确定性

复杂网络的特性：

（1） 度

在一个无向型的网络中一个节点i的度Ki就是和节点i相连的边的数目

（2） 平均路径长度

描述了节点间的分离程度，即网络有多小。
两节点间的距离：连接两者最短路径的边的数目【从a到b最短中间经过个c，则节点间距离为2，因为有两条边】
网络直径：任意两点间的最大距离
平均路径长度：所有节点间距离的平均值

N（N-1）=Cn2 选任意两点，是可能的距离，在这里求一个归一化。所以除以它
人们研究复杂网络发现：绝大多数大规模真实网络的平均路径长度比想象的小得多, 称之为 “小世界效应”

（3） 聚类系数

侧重描述节点的近邻之间的关系
我有10个朋友，但是谁都不认识谁，那么我的集聚系数为0
我有10个朋友，他们几乎都认识，那么我的集聚系数就接近于1

计算方法：
假如节点a 有k条边与其他节点连接，那么这k个节点之间互相连接最多可能有k（k-1）/2条边。
节点a的聚类系数Ca=这k个节点实际形成的边/ 最多可能的边数k（k-1）/2
整个网络的聚类系数C=所有节点的聚类系数的平均值

小世界网络

小世界网络：近年来研究发现,很多实际的复杂网络既不完全规则也不完全随机,而是介于完全规则和完全随机这两个极端之间,
既具有类似规则网络的较大集聚系数,又具有类似于随机网络的较小平均路径长度

小世界网络经典例子：人际关系网络中的“六度分离”
【社会心理学家斯坦利·米尔格拉姆做了一个实验：他要求300 多人发信把他的一封信寄到某市一个“ 目标” 人。于是形成了发信人的链条, 链上的每个成员都力图把这封信寄给他们的朋友、家庭成员、商业同事或偶然认识的人, 以便尽快到达目标人。实验结果是, 一共60 个链条最终到达目标人, 链条中平均步骤大约为6 。人们把这个结果说成“ 六度分离” 】

小世界：大多网络尽管规模很大，但是任意俩节点间都有一条很短的路径
集聚度：网络有内聚倾向
幂律分布：对一件事情起决定作用的，往往是少数几个因素，而其它大部分的因素都无关紧要。

小世界网络模型【small world network / SWN】 【watts和strogatz 于1998提出】
Watts定义了小世界网络的三个特性：
#1# 连接各个节点之间最短的路径长度, 这是整个网络中所有节点对路径长度的平均值。
#2# 集聚程度, 它代表了两个节点之间通过各自的相邻节点连接在一起的可能性, 当然它们之间可能直接连接, 即网络的集聚度。
高度结构化的网络有长路径和大的聚合度,
随机网络则有短路径长度和很小的集聚度。
小世界网络有与随机网络相近的路径长度, 但却拥有高聚合度。

#3# 对数路径, 所以对任何规模的网络都会随着网络图形变得越来越巨大而网络却保持相对短的路径长度

完全图 就是 两两之间都有相关。 没有实际意义。