Skip to content

Graphs and Networks Terminology

Terminology

Like any discipline, graphs/networks come with their own set of nomenclature. The following descriptions are intentionally simplified—more mathematically rigorous definitions can be found in any graph theory textbook.

  • Graph/Network: A data structure G = (V, E) where V and E are a set of vertices/nodes and edges/links.
  • Vertex/Node: Represents a single entity such as a person or an object.
  • Edge: Represents a relationship between two vertices (e.g., are these two vertices friends on a social network?).
  • Directed Graph vs. Undirected Graph: Denotes whether the relationship represented by edges is symmetric or not.
  • Weighted vs Unweighted Graph:
    • In weighted graphs, edges have a weight that could represent the cost of traversing or a similarity score or a distance score.
    • In unweighted graphs, edges have no weight and simply show connections, example: course prerequisites.
  • Subgraph: A set of vertices and edges that are a subset of the full graph's vertices and edges.
  • Degree: A vertex/node measurement quantifying the number of connected edges.
  • Connected Component: A strongly connected subgraph, meaning that every vertex can reach the other vertices in the subgraph.
  • Shortest Path: The lowest number of edges/links required to traverse between two specific vertices/nodes.