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-)degreek. - 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 |
