### 6 releases

0.6.0 | Jul 26, 2024 |
---|---|

0.5.5 | Mar 25, 2024 |

0.5.2 | Oct 16, 2023 |

#**447** in Data structures

**44** downloads per month

**MIT/Apache**

31KB

303 lines

# Neighborhood Diversity

A

Library for computing the neighborhood diversity of simple, undirected graphs.`Rust`

## Quick Start

`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``(``)``;`

## Definitions

A graph's neighborhood diversity quantifies the variety of neighborhoods of its vertices. In loose terms, it says that two vertices have the same type if they have the same neighbors, irrespective of whether they are adjacent or not. Two vertices having the same type is an equivalence relation which means that reflexivity, symmetry and transitivity apply. For the order-zero graph $K_0$, the neighborhood diversity is zero. Graphs $G = (V, E)$ of higher order produce values between one and $|V|$. One, if the graph's vertices form a singular clique or independent set and $|V|$ if no two vertices have the same type. The definitions this work is based on closely adhere to the ones presented by Lampis (2012):

Definition 1.1Given a graph $G = (V, E)$, two vertices $v, v' \in V$ have the sametypeif $N(v) \setminus {v'} = N(v') \setminus {v}$.

Definition 1.2Given a graph $G = (V, E)$, a subset $M \subseteq V$ is called aneighborhood classof $G$ if $\forall v, v' \in M: N(v) \setminus {v'} = N(v') \setminus {v}$.

Definition 1.3Aneighborhood partitiondivides the vertices of a graph into subsets in such a way that each subset forms a neighborhood class. Such a partition isoptimalif it is made up exclusively of maximal neighborhood classes.

Definition 1.4Theneighborhood diversityof a graph is defined by the number of parts in the optimal neighborhood partition of its vertices.

## License

Licensed under the Apache License, Version 2.0 <LICENSE-APACHE.txt or https://www.apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT.txt or https://opensource.org/licenses/MIT>, at your option. Files in the project may not be copied, modified, or distributed except according to those terms.

#### Dependencies

~310KB