Graph properties

From Exterior Memory
Jump to: navigation, search

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 Graph-Complete-N7.svg deg len cc
2D Grid or Lattice graph Graph-square-grid.svg deg len cc
Star Graph-star-E7.svg deg len cc
Tree Graph-tree-h3.svg deg len cc
Ring Graph-cycle-n11.svg deg len cc
Extended Ring Graph-extended-cycle-n11.svg deg len cc
Hierarchical Hierarchical network model example.svg 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