# Graph properties

From Exterior Memory

Graph Properties

## Properties

Symbols:

N |
Total number of nodes in a graph |

E |
Total number of edges in a graph |

k |
Degree of a node |

The average degree `<k>`

is `E/N`

for a directed graph, `2 E/N`

for a undirected graph.

- Degree distribution
- Probabilities
`P(k)`

that a node has (out-)degree`k`

. - Cluster coefficient
- Probability that there is an edge AB, given that there is an edge CA and an edge CB. This may be specific to a given node C, or generic for all nodes in a graph.
- Average minimum path length
- Given two nodes A and B, the expected path length from A to B.

## Graphs

All graph are assumed to be connected.

Graph Type | Example | Degree distribution | Path length | Cluster coefficient | |
---|---|---|---|---|---|

Full mesh or Complete graph, a fully connected graph | deg | len | cc | ||

2D Grid or Lattice graph | deg | len | cc | ||

Star | deg | len | cc | ||

Tree | deg | len | cc | ||

Ring | deg | len | cc | ||

Hierarchical | deg | len | cc | ||

Extended Ring | deg | len | cc | ||

Erdős-Rényi random graph | deg | len | cc | ||

Watts-Strogatz graph | deg | len | cc | ||

Barabási-Albert preferential attachment graph | deg | len | cc | ||

Exponential Random (ERGM) | deg | len | cc | ||

Hyperbolic (HGN) | deg | len | cc |