大型企业网站欣赏,wordpress 实用主题,做视频网站需要什么架构,建站后角度是不是0一、引言
1、网络科学至今受到广泛关注的原因#xff1a;
#xff08;1#xff09;大量的学科#xff08;尤其生物及材料科学#xff09;需要对元素间相互作用在多层级系统中所扮演的角色有更深层次的理解#xff1b;
#xff08;2#xff09;科技的发展促进了综合网…
一、引言
1、网络科学至今受到广泛关注的原因
1大量的学科尤其生物及材料科学需要对元素间相互作用在多层级系统中所扮演的角色有更深层次的理解
2科技的发展促进了综合网络工程系统的能力
2、Boids modelboids模型 boids model由Reynolds结合计算机图形提出这个模型尝试去寻找社会中鸟群、兽群在集群中排列方式。并提出了以下重要的协议
1分隔原则separation群体内所有个体有避免相邻碰撞的趋势
2对准原则alignment群体内个体与其相邻个体速度保持一致的趋势
3内聚原则cohesion群体内所有个体有趋向邻近个体的趋势 根据以上原则可得下图变化 3、网络系统的组成及挑战
1网络系统的组成 动态单元dynamic units彼此之间能够传递和发送信息 信号交换网络signal exchange network能够通过有线或者无线协议实现信息交换
2网络系统所遇到的挑战 系统理论不得不混合信息网络数学 面临跨学科结合如网络几何学
4、通过局部交互的信息交换
1局部通信locality communication 信息交换频道communication channels传送和接受信息需要能量因此只有在有限范围能够接受信息 可靠的带宽available bandwidth如果许多机构同时传播大量的数据交互频道将会饱和并且会导致通信系统急速的恶化。因此为了满足带宽要求信息交换应保持过分节俭的
2局部感知 a、视觉传感器vision-based sensor能够有很长的有效范围但为锲型几何区域 b、 范围传感器range sensor如声呐、激光雷达sonarslaser scanners等不同传感器有着不同的分辨率和有效范围为环形全方向 c、触觉传感器tactile sensor能够提供即刻的周边信息 d、单射线范围传感器single ray range sensor
5、图基交互模型 交互的几何图形事实上将在多智能体网络系统的分析和综合扮演重要角色能够让我们聚集在拓扑结构内部连接所起到的作用topology 一个具有全方向范围传感器机构网络其相应的机构和交互边显示在下图中
edge边能使信息在边连接的顶点之间传递分为有向和无向directed or undirected,其中有向是带箭头的单向而无向是指无箭头的双向 静态、动态和随机网络Static, Dynamic, and Random Networks 根据边可能的消失和再现分为三类 静态网络static network边是静态的即非时变 动态状态相关网络Dynamic, State-dependent Networks边集可能是时变的边可能由于网络机构状态的功能消失或再现 随机网络random network有特别的动态网络组成边是概率发布而非确定性发布
二、图论
1、图与顶点集和边集
1图graphs及其中的定义 图是由含有有限数量元素的有限点集建立将该点集设为顶点集vertex set并标记为V V中的每一个元素都为图中的一个顶点vertex表述为V{} 若 V用两个子集表示则定义为这个集合形式为{},其中i,j1,,2,3,...。 有限图G形式上定义为G(V,E)其中V定义为有限顶点的集合E定义为边的集合顶点和边集为V(G)和E(G)并简化edge{vi,vj}为vivj或ij。 若在顶点vi和vj之间存在一条边(edge)称顶点是邻接的(adjacent)并记关系为vi~vj。这种情况下边vivj称为vi和vj之间的关联(incident)
下图为一个无向图G(V,E)其中V{},E(,,,,) 在V中的邻接顶点集合为N(i)可理解为点集{∈V|vivj∈E}也就是中所有点均与是邻近的。对于无向图如果∈N(i)那么∈N(j)。 对于序列 ,,,..., 在上述序列中和是邻接的。和称为路径的终点(end vertices)vi1...vim-1称为内部顶点inner vertices。如果两个终点首尾连在一起称为一个环cycle。对于一个图形没有形成环叫做一个森林(forest)。 连通图connected对于V(G)中的每一对点都有一条路使他们成为终点end vertices称图G为连通图connected。相反称为非连通图disconnected。连通图相对于无向图而言 连通分量connected component一个连通图含有一个连通分量一个非连通图有超过一个分量。只有一个分量的深林叫做一棵树tree。连通分量是子图子图是连通的子图中含有的最大顶点数 Unlabeld无标签为了更清楚的表述图中的逻辑结构删除各顶点的明确身份信息 Labeld标签将无标签图重新给予身份下面分别为无标签和标签图 同构isomorphic对于两个图G(V,E)和G’(V’,E’)如果拥有相似的点集和边集称为同构记为 完全图complete graph每一个顶点是邻接任何一个其他顶点 路径图path graph与上诉彼此邻接的 ,,,...,同构 环形图cycle graph与路径图不同形成闭环
以下为完全图及路径图 2子图及生成子图 子图G (V,E)和其一个子集S⊆V产生的子图subgraph记为 (S,)其中{{,} ∈E|vi,vj∈S}。也就是子图S中的点和边均为G中存在的如下图中所对应的a、b图。 事实上对于G’(V’,E’)是G的子图当V⊆V’and E⊆E’时也称G为G’的子图。如果对于一个子图VV’可以被定义为一个生成子图spanning subgraph对于图G的生成树同时也是图G的生成子图。 生成树spanning tree包含连通图中所有的顶点其中有一顶点可到达任意一顶点 生成森林forest生成树是对应连通图来说而生成森林是对应非连通图来说的。非连通图可分解为多个连通分量而每个连通分量又各自对应多个生成树至少是 1 棵因此与整个非连通图相对应的是由多棵生成树组成的生成森林。 图a中包含有子图bc为b的边界图boundary即为与子图b存在边的点和其够成的边图d为子图b的闭合图closure即为子图b与其边界图的结合。
2、有向图和赋权图
1赋权图weighted graphs图G中的每一条边都相应地赋有一个数值则称G为赋权图记为G (V,E,w)。
2有向图digraphs当给图中的边赋予方向即变为有向图记为D(V,E)。其中(vi,vj)表示i为箭头的尾部j为箭头的头部即为指向j的箭头方向。 强连接strongly connected有向图中任意两点vi和vj满足vi到vj以及vj到vi都连通非边相反则为弱连接weakly connected 相似地D (V,E),其子图D’ (V’, E’), is such that V’⊆ V and E’⊆ E. 上图中V {,,,}边集为{(,),(,),(,)}
3、图和矩阵 上诉中确立了图形用顶点和边的表述形式下面将会建立图形和矩阵的表述形式。
1邻接矩阵和度 对于一个无向图G其内在顶点的度(degree)表示为d(vi)其值为邻接点集N(i)的基数即为在G中邻接顶点数的个数。下图中 d()1, d()3, d()3, d()2, d()3 一个图形的度序列是其顶点度的集合G的度矩阵(degree matrix)∆(G)是一个对角矩阵在对角线上包含了G中的顶点度 即 邻接矩阵A(G)(adjacency matrix)是对称的n×n矩阵,邻接矩阵的值为 上图中的度矩阵和邻接矩阵为 2关联矩阵incident matrix 关联矩阵incident matrix D(D)假设在具有n个顶点和m条边的有向矩阵中的任意一条边都赋予标签则D()为一个n×m矩阵被定义为 即对于dij当箭头的头部指向vi时dij为1箭头的头部指向j时为-1.
下图关联矩阵为 上诉的关联矩阵可以看到每一列的和均为0这位关联矩阵的共同属性这是由于每一列为一条有向边而有向边又对应着头和尾巴1和-1。
定义弱连接有向图的循环空间(cycle space)为关联矩阵的零空间(null space)即为D(D)z 0中z列向量的集合。
定义假定在关联矩阵D(D)中一个符号路径向量(signed path vector)是向量z在D中所对应的一条路径非边z中第i个指数为1表示第i条边(edge)是积极遍历traversed positively符合路径遍历方向-1为消极遍历0为未在该条路径中使用。
公理有向图中一个符号向量Z所对应的通路path有着不同的起点和终点向量yD(G)z中第i个元素其值为1则为起点值为-1则为终点0为其他。
定理一个弱连接连通有向图D其关联矩阵D(D)的零空间(null space)是由D的循环cycle所对应的符号向量路径所决定的。
4、图的拉普拉斯表述
1图拉普拉斯矩阵
图G的另一个矩阵描述为图拉普拉斯矩阵graph laplacianL(G)。
图拉普拉斯矩阵最直接的定义是对于无向图G的拉普拉斯矩阵度矩阵-邻接矩阵 对于有向图图G的拉普拉斯矩阵为 其中D(GO)为GO所对应的关联矩阵这个定义揭露了图拉普拉斯矩阵实为一个对称且正半定矩阵。
上诉对于有向图和无向图的定义是等效的并且在无向图计算公式的定义中不需要方向。我们将习惯采用D(G)即关联矩阵的方法来计算有向图。抛开方向有时采取上诉两个定义中的一个对于图的拉普拉斯矩阵是有用的。
赋权图拉普拉斯矩阵 W为一个mXm的对角矩阵w(ei),i 1,...,m位于对角线上。
2边拉普拉斯
边拉普拉斯edge laplacian对于一个任意方向的图G边拉普拉斯定义为 两个Le(G)关键线性代数特征如下Le(G)非零特征值与L(G)非零特征值相同转置矩阵特征值与原矩阵特征值相同Le(G)与L(G)非零特征值等于D(G)中非零奇异值的平方。
具有p个连通分量Gi的图G其关联矩阵为 图G的边拉普拉斯矩阵具有块对角线矩阵的形式 有向图拉普拉斯在两个矩阵计算中不包含由于出度导致的度减少
定义有向赋权图的邻接矩阵为即对于wij箭头指向i为正 对于对角度矩阵定义为 din(v)是顶点v的赋权内度in-degree:在i出各箭头边权值相加箭头指向i为正 记度矩阵为即为A(D)与1列向量的对角阵这是由于A(D)每一行相加即为dii的权值和 对应的权值拉普拉斯内度 in-degree定义为 对于所有的有向图均有即全部为1的向量是L(D)矩阵中0特征值所对应的特征向量N是指矩阵的0空间即Av0由于特征值及其特征向量的计算公式固有v为0特征值所对应的特征向量 在多智能体网络中我们选择入度In-degree而非出度out-degree这是由于入度显示机构被其他影响而出度显示影响其他机构。
3代数和谱图论
事实上对于度、邻接、关联、拉普拉斯矩阵特征值的研究属于图论中的子学科名为谱图论spectral graph theory
图拉普拉斯L(G)是对称且半正定的特征值均为非负因此其特征值可写为 其中
理论图G是连通图的充要条件为
