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)
whereV
andE
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.