1、简介

尽管网络科学和传统的图论关于基本概念的定义是一致的,但两者在研究角度和研究方法上有着重要的区别。传统的图论往往着眼于具有某种规则结构或者节点数较小的图,因而往往在理论分析时可以采用图示的方法直观的看出图的一些性质,然后网络科学研究中设计的实际网络往往包含数十万甚至数百万以上的节点,具有复杂的不规则拓扑结构,必须借助于强大的计算能力和统计方法。这篇笔记主要介绍网络科学中一些基本的概念和定义。

2、相关介绍

复杂网络的连通性

以全球社交网络为例,尽管没有这个网络的完整结构数据。但是全世界只要有一个人没有朋友或者一小群人没有除了这群人之外的朋友,这整个网络就是不连通的,对于大规模网络而言,连通性是相当脆弱的性质,因为单个节点或者相当少部分节点的行为都可能破坏连通性。但是,我们可以考虑连通片:许多实际的大规模负责网络都是不连通的,但是往往会存在一个特别大的连通片,它包含了整个网络中相当比例的节点,这一连通片成为巨片(Giant component)。

有向复杂网络中的蝴蝶结结构

实际的大规模有向网络往往不是强连通也不是弱连通的,往往有一个包含了网络中相当部分节点的很大的弱连通片-弱连通巨片(Giant weakly connected component,GWCC)。这一弱连通巨片往往具有一种包含四个部分的蝴蝶结结构(Bow-tie structure)。

1、强连通核(Strongly connected core,SCC):亦称为强连通巨片,它位于网络的中心。SCC中任意两个节点之间都是强连通的。

2、入部(IN):包含那些可以通过有向路径到达SCC但不能从SCC到达的节点。

3、出部(OUT):包含那些可以从SCC通过有向路径到达但不能到达SCC的节点。

4、卷须(Tendrils):包含那些既无法到达SCC,也无法从SCC到达的节点。

此外,还有可能存在从挂在IN上的卷须节点到挂在OUT上的卷须节点的不经过SCC的有向路径,这些串在一起的卷须节点成为管子(Tube)。

3、相关概念

节点的度与网络稀疏性

度是刻画单个节点属性的概念,在网络科学中我们用网络中所有节点的度的平均值称为网络的平均度,记为<k>。

以无向图为例,N代表节点数,M代表边数:
$$
k = \frac{2M}{N}
$$

网络稀疏性与稠密化

一个包含N个节点的网络的密度ρ定义:网络中实际存在的边数M与最大可能的边数之比。

因此,对于无向网络,定义:
$$
ρ = \frac{M}{\frac{1}{2}N(N-1)}
$$
可以得到平均度和网络密度之间有如下的关系:
$$
k = \frac{2M}{N}=(N-1)ρ≈Nρ
$$