无标度孤立团层次结构的新模型

### 无标度孤立团层次结构的新模型 #### 1. 引言 现实世界中的许多网络，如万维网、互联网、引用网络和生物网络等，都具有无标度特性，即其度分布遵循幂律。这些网络还具有高聚类系数和小直径等典型属性，为此人们提出了许多网络模型来解释这些特性。 最近，有研究对现实世界网络进行了新的观察： - **观察 1**：网络中团的大小分布呈现幂律。 - **观察 2**：收缩这些团后网络的度分布也呈现幂律。 - **观察 3**：将收缩后的网络视为原始网络，重复观察 1 和 2 依然成立。 这种结构被称为层次团结构，最终没有孤立团的收缩图称为素网络。此前大多数无标度网络模型无法生成具有大团（更不用说孤立团）的图，也没有针对层次团结构的模型。本文旨在提出一种新的网络模型，为任何给定的无标度网络添加层次团结构。 #### 2. 预备知识 - **图的基本定义**：本文只考虑无多重边和自环的简单无向图，记为 $G = (V, E)$，其中 $V$ 是顶点集，$E$ 是边集。对于图 $G$，$V[G]$ 表示顶点集，$E[G]$ 表示边集。顶点 $v$ 的邻域 $N_G(v)$ 是与 $v$ 相邻的顶点集，$v$ 的度 $d_G(v)$ 是邻域的大小，图的最大度记为 $\Delta$。 - **子图与团**：图 $G' = (V', E')$ 是 $G$ 的子图，当且仅当 $V' \subseteq V$ 且 $E' \subseteq (V' \times V') \cap E$。子图是团，当且仅当其中任意两个顶点之间都有边相连。 - **孤立团**：团 $C$ 是 $c$-孤立的，如果从 $V(C)$ 到 $V \setminus V(C)$ 的出边数小于 $c|V(C)|$。1 - 孤立团可以在线性时间内枚举，且它们之间很少重叠，易于分离。 - **图的收缩**：用 $C(G)$ 表示将图 $G$ 中所有孤立团收缩为一个顶点后得到的简化图。 - **无标度特性**：图 $G$ 是“无标度”的，如果其度分布遵循幂律，即与 $k^{-\gamma}$ 成比例，其中 $\gamma$ 是常数。度分布是序列 $\{ \frac{n_k}{n} \}_{k \geq 1}$，其中 $n_k$ 是度为 $k$ 的顶点数，$\frac{n_k}{n}$ 是其在 $n$ 个顶点中的比例。若存在常数 $c_1$ 和 $c_2$，使得对于所有 $1 \leq k \leq \Delta$，有 $c_1k^{-\gamma} \leq \frac{n_k}{n} \leq c_2k^{-\gamma}$，则称 $G$ 的度分布遵循幂律。本文将此概念扩展到孤立团大小分布，若孤立团大小分布序列 $\{ \frac{m_s}{m} \}_{s \geq 1}$ 满足 $\frac{m_s}{m} = \Theta(s^{-\gamma})$，则称 $G$ 的孤立团大小遵循幂律。 #### 3. 模型 模型的主要思想如下： - 以一个由某种无标度模型（如 BA 模型）生成的素无标度图 $G_0$ 为基础。 - 将 $G_0$ 中的顶点随机分为“节点”（代表 1 - 孤立团）和“简单顶点”。 - 对于每个节点，用一个大小等于其原始度的孤立团替换它，新孤立团中的顶点再递归地进行同样的处理。 具体步骤如下： - **输入**：图 $G_0 = (V_0, E_0)$ 和参数 $p_0$，假设 $G_0$ 是素无标度图，即其所有团都是非孤立的，且度分布遵循幂律。 - **递归扩展**