复杂网络相关研究

复杂网络的一些概念记录

邻接矩阵

邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

矩阵中每一行代表一个点,行a即为点a,每一列代表某一行的点所指向的点,矩阵的每一个(小格)表示一条边。图中的所有边(指向性的箭头)带有权值,通常约定权值为0的边为不存在的边。

关联矩阵

关联矩阵(incidence matrix)是显示两类对象之间关系的矩阵。

矩阵中每一行代表一个点,行a即为点a,每一列代表某一条边,矩阵的每一个小格表示该点和边之间有连接关系。1则代表相连,0则代表不相连。

拉普拉斯矩阵

拉普拉斯矩阵(Laplacian matrix)也称调和矩阵,是表示拉普拉斯算子的离散化,用矩阵来表示图。

矩阵中的每一行代表一个点,行a即为点a,每一列代表另一个点b,以下面三种情况进行判断赋值:

如果a = b,则该小格的值为deg(a),即该点的度.

如果a != b,但a和b相连,则该小格的值为-1.

其他情况,改小格值为0.

完全图

完全图是一个简单的无向图,其中每对不同的顶点之间都恰连有一条边相连。

  • 平均路径长度为 1
  • 聚类系数为 1

补图

补图(complementary graph),一个图G的补图(complement)或者反面(inverse)是一个图有着跟G相同的点,而且这些点之间有边相连当且仅当在G里面他们没有边相连。
通俗的来讲就是完全图Kn去除G的边集后得到的图Kn-G.

对于左边的图,先画出他的完全图,再删去原来图中的边,即可得到补图

接近中心性

在连通图中,节点的接近度中心度是网络中心度的度量,计算方式为该节点与图中所有其他节点之间的最短路径的长度之和的倒数。因此,一个节点越中心,它就越靠近所有其他节点。

稠密图

在数学中,稠密图是边数接近最大边数的图。相反,只有几条边的图是稀疏图。稀疏图和稠密图之间的区别相当模糊,并且取决于上下文。

图的密度

图的密度被定义为 边的数量/最大可能边数

图的割集

设S是G的边集E的一个子集,如果在连通图G中删除S的所有边.则G-S不连通,并且不存在S的真子集使G-S不连通,就称边集S是图G的一个割集。

通俗的说,如果移除某条边或点,原图G不再连通,则称该点或边为图的一个割集,但是一个割集的真子集不能是割集。

因为v3是点割集,因此{v1.v3}不能作为图的一个点割集

度相关系数

度相关系数(degree correlations)
度相关系数被定义为在图中随机取一个度为k时能够取到的概率p(k).


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!