现在的位置: 首页 > 综合 > 正文

《网络科学-原理与应用》要点总结1——图论

2018年04月03日 ⁄ 综合 ⁄ 共 1206字 ⁄ 字号 评论关闭

由于毕设的需要,寒假一直在看《网络科学-原理与应用》这本书,到现在为止粗粗的看了一遍,现在把一些要点都记录一下,当然里面好多数学推算都没懂,o(╯□╰)o

图是一个3元组:G=(N,L,f),N为节点集合,L为链路集合,f为将链路映射到节点对的映射函数。图有很多属性,例如平均路径长度,密度,熵,聚类系数,介数和紧度,谱半径,谱系,度序列分布等。节点度等于将节点连接到图上的链路数量。路径长度是两个节点间的最短路径,平均路径长度是所有最短路径的平均值,又称为特征路径长度。循环的回路长度是1,意味着节点连接到自身。在图G中任何两个节点之间最长的路径称为图G的直径。从一个节点u到连通图的所有其他节点的最长路径定义成节点u的半径,具有最小半径的节点为图的中心。具有最大的半径的节点称为边沿节点。密度是实际链路数与最大可能链路数之比。聚类系数是对“有多少节点与他们的邻接节点形成三角子图”的一种测量。介数和紧度是对一个节点的中介或中间者的有用性的测量。。谱半径是图的邻接矩阵的最大非平凡特征值:det[A(G)-λI]=0,谱半径完全由图的拓扑(度序列)来决定。谱系是图的拉普拉斯矩阵的最大非平凡特征值:det[L-λI]=0。如果度序列为[0,0,3,0,1],则度序列分布g'=[0,0,0.75,0,0.25].熵是对“信息量”或信息传递的“不确定”的度量,熵的测量单位是比特:I(G)=-∑hi(㏒2(hi)),其中g'=[h1,h2......h(max_d)].

图的四种基本形式的矩阵表示:连接矩阵,邻接矩阵,路径矩阵和拉普拉斯矩阵。连接矩阵就是节点u和节点v之间有多少条直接连着的线,注意要不经过其他的节点:如果Vi~Vj,Cij=k,否则Cij=0,k就是Vi~Vj的链路数。邻接矩阵只需要把连接矩阵稍作修改即可,如果k>1,那么在邻接矩阵中仍用1来表示:如果Vi~Vj, Aij=1,否则,Aij=0. 拉普拉斯矩阵L=A-D.这里A是邻接矩阵,D为对角矩阵。对角矩阵式一个具有非零对角元素并且对角元素d(i,i)等于节点Vi的度的一致性矩阵。路径矩阵存储了沿着途中所有节点对之间有向路径的跳数。

图按照结构分类,可以分为随机图,小世界类,无标度类和k-规则图。随机图具有随机结构(具有最小的聚类系数),k-规则图具有纯的确定性的结构。小世界类是大部分结构化的,部分随机的图。小世界图是具有相对较小的平均路径长度,相对较高的聚类系数CC的图。聚类系数的算法:假设邻居共享c条链路,那么节点u的聚类系数CC(u)=2c/(degree(u)*(degree(u)-1)).聚类系数是三角子图c的实际数与最大可能数之比。无标度类是大部分是随机的,部分结构化的图。

随机图服从泊松分布,无标度图服从幂律分布(厚尾分布,随着k的增加不会像指数或正太分布那样快的减少),小世界图具有高平均聚类系数,k-规则图具有0熵。

抱歉!评论已关闭.