邻域多样性

一个用于计算简单无向图的邻域多样性的 Rust 库。

快速入门

use neighborhood_diversity::prelude::*;

let graph = Graph::random_graph(10, 0.1);
let neighborhood_partition = calc_neighborhood_partition(&graph);
let neighborhood_diversity = neighborhood_partition.len();

定义

一个图的邻域多样性衡量其顶点的邻域多样性。简单地说，如果两个顶点具有相同的邻居，则它们具有相同的类型，无论它们是否相邻。具有相同类型的两个顶点是一个等价关系，这意味着自反性、对称性和传递性适用。对于零阶图 $K_0$，邻域多样性为零。更高阶的图 $G = (V, E)$ 产生介于 1 和 $|V|$ 之间的值。如果图的顶点形成一个单一的团或独立集，则为 1；如果没有两个顶点具有相同的类型，则为 $|V|$。本工作中基于的定义与 Lampis (2012) 提出的定义非常接近。

定义 1.1 对于一个图 $G = (V, E)$，如果两个顶点 $v, v' \in V$ 满足 $N(v) \setminus {v'} = N(v') \setminus {v}$，则称它们具有相同的 类型。

定义 1.2 对于一个图 $G = (V, E)$，如果子集 $M \subseteq V$ 满足 $\forall v, v' \in M: N(v) \setminus {v'} = N(v') \setminus {v}$，则称 $M$ 是 $G$ 的一个 邻域类。

定义 1.3 一个 邻域划分 将图的顶点划分为子集，使得每个子集形成一个邻域类。如果这种划分仅由最大邻域类组成，则称其为 最优。

定义 1.4 图的邻域多样性定义为最优邻域划分中部分的数量。

许可证

根据 Apache 许可证版本 2.0 <LICENSE-APACHE.txt 或 https://apache.ac.cn/licenses/LICENSE-2.0> 或 MIT 许可证 <LICENSE-MIT.txt 或 https://opensource.org/licenses/MIT>，由您选择。项目中的文件不得根据这些条款进行复制、修改或分发。