Quantities in Graph Theory

Distance-Bassed §

• The distance between vertices is defined as the length of the shortest path from to .

• The diameter of a graph, denoted is the length of the longest shortest path in a graph.

  We may calculate it algorithmically using BFS.

• The center of is a vertex with the property that the maximum distance between and any other vertex is as small as possible. That is it satisfies

Centrality §

• The centrality of a vertex in a given graph is a function that captures the vertex’s “importance”.

• The Betweenness Centrality is a measure based on shortest paths.

  Let is the total number of shortest paths from to is the number of those paths that have as an internal vertex.

  Then

  We usually normalize to obtain a proper ranking independent of the number of nodes

• The Link Betweenness Centrality is similar to the betweenness centrality except it is based on internal edges.

  Let is the total number of shortest paths from to is the number of those paths that have as an internal edge in the path.

  We usually perform normalization to obtain a proper ranking

Density and Disjointedness §

• The density of a graph is the ratio of the number of edges with respect to the maximum number of edges. We denote this with ,

  • For undirected simple graphs, we have

    • For directed graphs, we have

  • A graph is dense if its density is as close to ¹. Otherwise it is sparse

• The Clustering coefficient is a quantity which captures the extent in which neighbors form a clique.

  Let be the number of edges between and neighbors of .

  The clustering coefficient is calculated as

  It should be noted that

Links §

• Fundamental Constructs of Graph Theory
• Trails, Walks, Paths and Cycles

Footnotes §

1. The definition of “closeness” is arbitrary. ↩