Download presentation
Presentation is loading. Please wait.
1
复杂网络简介 LiuChang
2
目录 背景 基本概念 网络模型 基本搜索算法
3
目录 背景
4
技术网络 电力网 WWW 因特网 1) internet is not the only case, of course, complex networks can be found almost in all areas of nature. 2) Compare the structure of the WWW network with a cristal lattice for example.
5
社会网络 朋友关系网 科学引文网 科学家合著网
6
交通运输网络 航空网 城市公共交通网 道路交通网
7
生物网络 生态网络 蛋白质相互作用网络 神经网络
1) It is evident that network structure brings a whole new dimension... so how to study properties of network structure?!
8
复杂网络（Complex Network）
9
复杂网络（Complex Network）
定义 具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为 复杂网络。
10
复杂网络研究进程 1736，欧拉：哥尼斯堡七桥→图论 1950，Erdos, Renyi: 随机图论
20世纪60年代末，弱连接的强度(Mark Granovetter) 1998，Strogatz, Barabasi: 小世界实验 世纪之交，新纪元
11
为什么现在才开始研究复杂网络？ 计算机技术的发展： 使我们拥有各种网络的数据库，并有可能对大规模 的网络进行实证研究 普适性的发现：
许多实际网络具有相同的定性性质 且已有的理论不能描述和解释 理论研究的发展 小世界网络 (Small World Network), 无标度网络 (Scale-free Network) 统计物理学的研究手段
12
目录 基本概念
13
对网络结构的描述 度（Degree）：朋友的个数 介数（Betweenness）：经过我的最短路径的条数
集聚系数（群系数）（Clustering coefficient）：朋友的朋友 还是不是朋友的情况 最短路径（Shortest path）：两个顶点之间边数最少的路 径
18
聚类系数（clustering coefficient）
假设一个节点 有 条边与它相连，这 个节点 就是节点 的邻居，则节点的聚类系数就是 的 邻居节点互相连接的边数和邻居节点全部连接的 所有边数的比值。
19
clustering coefficient
用 表示节点的聚类系数，其中邻居节点相互连接的边数用 表示，这些邻居节点全部连接的所有边数为 。网络的全局聚类系数 是所有节点 的聚类系数的平均值。
20
目录 网络模型
21
复杂网络的结构 四种结构模型： 规则网络 小世界网络 随机网络 无标度网络
22
规则网络
26
小世界网络模型 WS小世界模型构造算法（随机化重连） 1、从最近邻耦合网络开始
2、随机化重连：以概率p随机地重新连接网络中的 每个边，即将边的一个端点保持不变，而另一个端 点取为网络中随机选择的一个节点。其中规定，任 意两个不同的节点之间至多只能有一条边，并且每 一个节点都不能有边与自身相连。
27
小世界网络模型 NW小世界模型构造算法（随机化加边） 1、一个环状的规则网络开始
2、随机化加边：以概率p在随机选取的一对节点 之间加上一条边。其中，任意两个不同节点之间 至多只能有一条边，并且每一个节点都不能有边 与自身相连。 改变p值可以实现从最近邻耦合网络(p=0)向全局 耦合网络(p=1)转变。当p足够小和N足够大时，NW 小世界模型本质上等同于WS小世界模型。
28
小世界网络模型
29
无标度网络 BA无标度模型构造算法 1、增长：从一个具有 个节点 的网络开始，每次引入一个新的节 点，并连到 个已存在的节点上，这里
1、增长：从一个具有 个节点 的网络开始，每次引入一个新的节 点，并连到 个已存在的节点上，这里 2、优先连接：一个新节点与一个已经存在的节点 相连接的概率 与节点 的度 ,节点 的度 满 足：
30
目录 基本搜索算法
31
基本搜索算法 广度优先搜索算法 深度优先搜索算法 最大度搜索算法 随机游走搜索算法 K遍历器随机游走与最大度相结合的混合算法
32
广度优先搜索算法（BFS） 首先查询源节点的所有邻居节点中是否存在目标节点，若 存在，则将其返回给源节点；若不存在，邻居节点将信息 专递给它们各自的邻居节点，重复上述过程，直到找到目 标节点为止。
33
深度优先搜索算法（DFS） DFS在源节点的邻居节点中沿着树的深度遍历树的节点,尽 可能深的搜索树的分支。
当节点i的所有邻居节点都已经被查询过，搜索将回到把 查询信息传递给节点i那个起始节点。 重复这一过程直到已发现目标节点为止。
34
最大度搜索算法（DS） DS是搜索其邻居中最大节点度的节点。 若该节点是目标节点,则返回信息。
否则,继续搜索最大节点度的节点的邻居节点,直到搜索到 目标节点为止。
35
随机游走搜索算法（RWS） 随机游走算法判断源节点是不是目标节点,如果是,则停止 搜索。否则,随机选择一个邻居将信息传送过去,直到找到 目标节点为止。 随机游走的搜索步数大,但是在搜索的过程中信息产生量 少,这样在网络中就不会产生很大的流量。
36
3种随机游走算法 1 无限制随机游走 2 不返回上一步节点的随机游走 3 不重复访问节点的随机游走
37
K遍历器随机游走与最大度相结合的混合算法 (KRDS)
网络中每个节点都知道它们邻居节点的信息 源节点随机选择k个邻居节点传送信息,若发现目标节点, 则将返回信息。 否则,它们分别选择它们邻居中度最大的节点传递信息。
38
K遍历器随机游走与最大度相结合的混合算法 (KRDS)
如果依然没有搜索到目标节点,则用随机游走进行查询。 重复这个过程直到搜索到目标节点为止。 在该算法中,k有一个约束条件,即它要小于等于当前节点 的度数。
39
对比 广度优先搜索 搜索在和源节点距离相等的节 点之间同时进行，提高了效率 会产生很大的流量；不适合用 来对规模比较大的网络进行搜 索
深度优先搜索 在规模比较小时平均搜索步数 不是很大 对规模比较大的网络来说不合 适 最大度搜索 对度分布比较均匀的网络不适合 无限制随机游走 搜索步数都比较大,而且随着网络规模的增大而急剧的增加。 不返回上一步随机游 走 不重复访问节点的搜 索算法 存在找不到节点的可能性 对WS小世界网络模型不太适用,平均搜索步数大 K遍历器随机游走 和最大度相结合 对基本的网络模型和新提出的小世界网络模型都适用。 平均搜索步数小 灵活度大 只需要利用局部信息
40
“我认为下个世纪将是复杂性的世纪。” ————史蒂芬霍金
41
Thank you
Similar presentations
