Transportation Geography and Network Science/Characterizing Graphs

From Wikibooks, open books for an open world
Jump to: navigation, search

beta index[edit]

The beta index (\beta) measures the connectivity relating the number of edges to the number of nodes. It is given as:

\beta=\frac{e}{v}

where e = number of edges (links), v = number of vertices (nodes)

The greater the value of \beta, the greater the connectivity. As transport networks develop and become more efficient, the value of \beta should rise.

cyclomatic number[edit]

The cyclomatic number (u) is the maximum number of independent cycles in a graph.

u=e-v+p

where p = number of graphs or subgraphs.

alpha index[edit]

The alpha index (\alpha) is the ratio of the actual number of circuits in a network to the maximum possible number of circuits in that network. It is given as:

\alpha=\frac{u}{2v-5}

Values range from 0%—no circuits—to 100%—a completely interconnected network.


gamma index[edit]

The gamma index (\gamma) measures the connectivity in a network. It is a measure of the ratio of the number of edges in a network to the maximum number possible in a planar network (3(v-2))

\gamma=\frac{e}{3(v-2)}

The index ranges from 0 (no connections between nodes) to 1.0 (the maximum number of connections, with direct links between all the nodes).

Completeness[edit]

The number of links in a real world network is typically less than the maximum number of links and the completeness index used here captures this difference. This measure is estimated at the metropolitan level.


\rho_{complete} = \frac{e}{e_{max}} = \frac{e}{{v^2}-{v}}

e refers to the number of links or street segments in the network and v refers to the number of intersections or nodes in the network. Compare with the \gamma index above.

König number[edit]

The König number (or associated number) is the number of edges from any node in a network to the furthest node from it. This is a topological measure of distance, in edges rather than in kilometres. A low associated number indicates a high degree of connectivity; the lower the König number, the greater the Centrality of that node.

eta index[edit]

The eta index (\eta) measure the length of the graph over the number of edges.

\eta=\frac{L(G)}{e}

theta index[edit]

The theta index (\theta) measure the traffic (Q(G)) per vertex.

\theta=\frac{Q(G)}{v}

iota index[edit]

The iota index (\iota) measures the ratio between the length of its network and its weighted vertices.

 \iota=\frac{L(G)}{W(G)}

 W(G)=1,\forall o=1

 W(G)=\sum_{e}2*o,\forall o>1

Source: [1]