igraph 参考手册

用于使用 igraph C 库

第 26 章. 分层随机图

1. 简介
2. 表示 HRG
3. 拟合 HRG
4. HRG 抽样
5. 与 igraph 图之间的转换
6. 预测缺失边
7. 弃用的函数

1. 简介

分层随机图是由具有 n 个顶点的无向图的集合。它通过具有 n 个叶子和 n-1 个内部顶点的二叉树定义，其中内部顶点用概率标记。随机图中两个顶点连接的概率由它们最近的共同祖先处的概率标签给出。

请阅读以下两篇文章以了解更多关于分层随机图的信息：A. Clauset、C. Moore 和 M.E.J. Newman。《分层结构和网络中缺失链接的预测》。Nature 453, 98 - 101 (2008)；以及 A. Clauset、C. Moore 和 M.E.J. Newman。《网络中层次结构的结构推断》。E. M. Airoldi 等人（编辑）：ICML 2006 Ws，计算机科学讲义 4503, 1-13。施普林格出版社，柏林海德堡（2007 年）。

igraph 包含将 HRG 模型拟合到给定网络的函数（igraph_hrg_fit），从给定 HRG 集合生成网络的函数（igraph_hrg_game，igraph_hrg_sample），将 igraph 图转换为 HRG 并返回（igraph_hrg_create，igraph_hrg_dendrogram），从一组抽样的 HRG 计算共识树的函数（igraph_hrg_consensus）以及基于其 HRG 模型预测网络中缺失边的函数（igraph_hrg_predict）。

igraph HRG 实现很大程度上基于 Aaron Clauset 在他的网站上发布的代码：https://aaronclauset.github.io/hierarchy/

2. 表示 HRG

2.1. igraph_hrg_t — 用于存储分层随机图的数据结构。
2.2. igraph_hrg_init — 为 HRG 分配内存。
2.3. igraph_hrg_destroy — 释放 HRG 的内存。
2.4. igraph_hrg_size — 返回 HRG 的大小，即叶节点的数量。
2.5. igraph_hrg_resize — 调整 HRG 的大小。

2.1. `igraph_hrg_t` — 用于存储分层随机图的数据结构。

typedef struct igraph_hrg_t {
    igraph_vector_int_t left;
    igraph_vector_int_t right;
    igraph_vector_t prob;
    igraph_vector_int_t vertices;
    igraph_vector_int_t edges;
} igraph_hrg_t;

分层随机图 (HRG) 可以表示为二叉树，其中内部顶点用实数标记。

请注意，您不一定需要知道此内部表示来使用 HRG 函数，只需将一个 igraph 函数创建的 HRG 对象传递给另一个 igraph 函数即可。

它具有以下成员

值：

`左`:	向量，包含内部树顶点的左子节点。第一个顶点始终是根顶点，因此向量的第一个元素是根顶点的左子节点。内部顶点用负数表示，从 -1 开始并向下，即根顶点是 -1。叶顶点用非负数表示，从零开始并向上。
`右`:	向量，包含顶点的右子节点，编码方式与 `左` 向量相同。
`概率`:	附加到内部顶点的连接概率，第一个数字属于根顶点（即内部顶点 -1），第二个属于内部顶点 -2，依此类推。
`边`:	给定内部顶点下方的子树中的边数。
`顶点`:	给定内部顶点下方的子树中的顶点数，包括自身。

2.2. `igraph_hrg_init` — 为 HRG 分配内存。

igraph_error_t igraph_hrg_init(igraph_hrg_t *hrg, igraph_integer_t n);

在将 igraph_hrg_t 传递给 igraph 函数之前，必须调用此函数。

参数：

`hrg`:	指向要初始化的 HRG 数据结构的指针。
`n`:	图中顶点的数量，该图由该 HRG 建模。如果这尚不清楚，则可以为零。

返回值：

错误代码。

时间复杂度：O(n)，图中顶点的数量。

2.3. `igraph_hrg_destroy` — 释放 HRG 的内存。

void igraph_hrg_destroy(igraph_hrg_t *hrg);

可以使用 igraph_hrg_destroy 调用再次重新初始化 HRG 数据结构。

参数：

hrg:

指向要释放的 HRG 数据结构的指针。

时间复杂度：操作系统相关。

2.4. `igraph_hrg_size` — 返回 HRG 的大小，即叶节点的数量。

igraph_integer_t igraph_hrg_size(const igraph_hrg_t *hrg);

参数：

hrg:

指向 HRG 的指针。

返回值：

HRG 中叶节点的数量。

时间复杂度：O(1)。

2.5. `igraph_hrg_resize` — 调整 HRG 的大小。

igraph_error_t igraph_hrg_resize(igraph_hrg_t *hrg, igraph_integer_t newsize);

参数：

`hrg`:	指向已初始化的 HRG 的指针（参见 `igraph_hrg_init`）。
`newsize`:	新大小，即叶节点的数量。

返回值：

错误代码。

时间复杂度：O(n)，n 是新大小。

3. 拟合 HRG

3.1. igraph_hrg_fit — 将分层随机图模型拟合到网络。
3.2. igraph_hrg_consensus — 计算 HRG 的共识树。

3.1. `igraph_hrg_fit` — 将分层随机图模型拟合到网络。

igraph_error_t igraph_hrg_fit(const igraph_t *graph,
                   igraph_hrg_t *hrg,
                   igraph_bool_t start,
                   igraph_integer_t steps);

参数：

`图`:	igraph 图，用于拟合模型。在有向图中，边方向将被忽略。
`hrg`:	指向已初始化的 HRG 的指针，拟合结果存储在此处。如果 `start` 参数为 true，它也可以用于将 HRG 传递给函数，该函数可以用作马尔可夫链蒙特卡罗拟合的起点。
`开始`:	是否从给定的 HRG 模型开始拟合。
`步骤`:	整数，拟合过程中要执行的 MCMC 步骤数。如果为零，则在满足收敛条件时停止拟合。

返回值：

错误代码。

时间复杂度：待定。

3.2. `igraph_hrg_consensus` — 计算 HRG 的共识树。

igraph_error_t igraph_hrg_consensus(const igraph_t *graph,
                         igraph_vector_int_t *parents,
                         igraph_vector_t *weights,
                         igraph_hrg_t *hrg,
                         igraph_bool_t start,
                         igraph_integer_t num_samples);

可以从给定的 HRG (hrg) 开始计算，或者（如果 start 为假），则首先将 HRG 拟合到给定的图。

参数：

`图`:	输入图。
`父母`:	一个已初始化的向量，结果存储在此处。对于每个顶点，存储其父顶点的 ID，如果顶点是树中的根顶点，则存储 -1。前 n 个顶点 ID（从 0 开始）引用图的原始顶点，其他 ID 引用顶点组。
`权重`:	数字向量，计算给定树分裂在生成的网络样本中发生的次数，对于每个内部顶点。顺序与 `parents` 中相同。
`hrg`:	一个分层随机图。如果 `start` 参数为 true，则它用作抽样的起点。它在 MCMC 过程中被修改。
`开始`:	是否使用提供的 HRG（在 `hrg` 中）作为 MCMC 的起点。
`num_samples`:	要生成用于创建共识树的样本数。

返回值：

错误代码。

时间复杂度：待定。

4. HRG 抽样

4.1. igraph_hrg_sample — 从分层随机图模型中抽样。
4.2. igraph_hrg_game — 生成分层随机图。

4.1. `igraph_hrg_sample` — 从分层随机图模型中抽样。

igraph_error_t igraph_hrg_sample(const igraph_hrg_t *hrg, igraph_t *sample);

此函数从分层随机图模型中抽取单个样本。

参数：

`hrg`:	要从中抽样的 HRG 模型
`样本`:	指向未初始化的图的指针；样本存储在此处。

返回值：

错误代码。

时间复杂度：待定。

4.2. `igraph_hrg_game` — 生成分层随机图。

igraph_error_t igraph_hrg_game(igraph_t *graph,
                    const igraph_hrg_t *hrg);

此函数是 igraph_hrg_sample 的简单快捷方式。它从给定的 HRG 创建单个图。

参数：

`图`:	指向未初始化的图的指针，新图在此处创建。
`hrg`:	要从中抽样的分层随机图模型。

返回值：

错误代码。

时间复杂度：待定。

5. 与 igraph 图之间的转换

5.1. igraph_from_hrg_dendrogram — 创建分层随机图模型的树状图的图形表示。
5.2. igraph_hrg_create — 从 igraph 图创建 HRG。

5.1. `igraph_from_hrg_dendrogram` — 创建分层随机图模型的树状图的图形表示。

igraph_error_t igraph_from_hrg_dendrogram(
    igraph_t *graph, const igraph_hrg_t *hrg, igraph_vector_t *prob
);

创建在 igraph_hrg_t 数据结构中编码的树状图的 igraph 图等效物。与节点关联的概率在向量中返回，因此此函数可以在没有属性处理程序的情况下工作。

参数：

`图`:	指向未初始化的图的指针，结果存储在此处。
`hrg`:	要转换的分层随机图。
`概率`:	指向已初始化向量的指针；与树状图节点关联的概率将存储在此处。叶节点将具有关联的概率 `IGRAPH_NAN` 。如果您不需要概率，可以将此设置为 `NULL` 。

返回值：

错误代码。

时间复杂度：O(n)，图中顶点的数量。

5.2. `igraph_hrg_create` — 从 igraph 图创建 HRG。

igraph_error_t igraph_hrg_create(igraph_hrg_t *hrg,
                      const igraph_t *graph,
                      const igraph_vector_t *prob);

参数：

`hrg`:	指向已初始化的 `igraph_hrg_t` 的指针。结果存储在此处。
`图`:	要转换的 igraph 图。它必须是一个有向二叉树，具有 n-1 个内部顶点和 n 个叶顶点。根顶点的入度必须为零。
`概率`:	概率向量，用于标记分层随机图的内部节点。

返回值：

错误代码。

时间复杂度：O(n)，树中顶点的数量。

6. 预测缺失边

6.1. igraph_hrg_predict — 基于 HRG 模型预测图中的缺失边。

6.1. `igraph_hrg_predict` — 基于 HRG 模型预测图中的缺失边。

igraph_error_t igraph_hrg_predict(const igraph_t *graph,
                       igraph_vector_int_t *edges,
                       igraph_vector_t *prob,
                       igraph_hrg_t *hrg,
                       igraph_bool_t start,
                       igraph_integer_t num_samples,
                       igraph_integer_t num_bins);

对网络的 HRG 模型进行抽样，并估计在网络中错误观察为不存在的边的概率。

参数：

`图`:	输入图。
`边`:	缺失边的列表存储在此处，前两个元素是第一条边，接下来的两个元素是第二条边，依此类推。
`概率`:	缺失边存在的概率向量，顺序与 `edges` 对应。
`hrg`:	一个 HRG，如果 `start` 为 true，则它用作起点。它也在 MCMC 抽样期间被修改。
`开始`:	是否从给定的 HRG 开始 MCMC。
`num_samples`:	要生成的样本数。
`num_bins`:	控制边概率的分辨率。数字越高，分辨率越高。

返回值：

错误代码。

时间复杂度：待定。

7. 弃用的函数

7.1. igraph_hrg_dendrogram — 从分层随机图创建树状图。

7.1. `igraph_hrg_dendrogram` — 从分层随机图创建树状图。

igraph_error_t igraph_hrg_dendrogram(igraph_t *graph, const igraph_hrg_t *hrg);

创建 igraph_hrg_t 数据结构的 igraph 图等效物。

参数：

`图`:	指向未初始化的图的指针，结果存储在此处。
`hrg`:	要转换的分层随机图。

返回值：

错误代码。

时间复杂度：O(n)，图中顶点的数量。

警告

自 0.10.5 版本起已弃用。请勿在新代码中使用此函数；请改用 igraph_from_hrg_dendrogram()。

igraph 参考手册

第 26 章. 分层随机图

1. 简介

2. 表示 HRG

2.1. igraph_hrg_t — 用于存储分层随机图的数据结构。

2.2. igraph_hrg_init — 为 HRG 分配内存。

2.3. igraph_hrg_destroy — 释放 HRG 的内存。

2.4. igraph_hrg_size — 返回 HRG 的大小，即叶节点的数量。

2.5. igraph_hrg_resize — 调整 HRG 的大小。

3. 拟合 HRG

3.1. igraph_hrg_fit — 将分层随机图模型拟合到网络。

3.2. igraph_hrg_consensus — 计算 HRG 的共识树。

4. HRG 抽样

4.1. igraph_hrg_sample — 从分层随机图模型中抽样。

4.2. igraph_hrg_game — 生成分层随机图。

5. 与 igraph 图之间的转换

5.1. igraph_from_hrg_dendrogram — 创建分层随机图模型的树状图的图形表示。

5.2. igraph_hrg_create — 从 igraph 图创建 HRG。

6. 预测缺失边

6.1. igraph_hrg_predict — 基于 HRG 模型预测图中的缺失边。

7. 弃用的函数

7.1. igraph_hrg_dendrogram — 从分层随机图创建树状图。

警告

2.1. `igraph_hrg_t` — 用于存储分层随机图的数据结构。

2.2. `igraph_hrg_init` — 为 HRG 分配内存。

2.3. `igraph_hrg_destroy` — 释放 HRG 的内存。

2.4. `igraph_hrg_size` — 返回 HRG 的大小，即叶节点的数量。

2.5. `igraph_hrg_resize` — 调整 HRG 的大小。

3.1. `igraph_hrg_fit` — 将分层随机图模型拟合到网络。

3.2. `igraph_hrg_consensus` — 计算 HRG 的共识树。

4.1. `igraph_hrg_sample` — 从分层随机图模型中抽样。

4.2. `igraph_hrg_game` — 生成分层随机图。

5.1. `igraph_from_hrg_dendrogram` — 创建分层随机图模型的树状图的图形表示。

5.2. `igraph_hrg_create` — 从 igraph 图创建 HRG。

6.1. `igraph_hrg_predict` — 基于 HRG 模型预测图中的缺失边。

7.1. `igraph_hrg_dendrogram` — 从分层随机图创建树状图。