Graph properties

From Exterior Memory
Revision as of 10:12, 25 April 2015 by MacFreek (Talk | contribs) (List of properties and graphs.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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 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