Graph Terminology Basics

Defining Local Connectivity: Neighbors and Degree

The most basic property of a node is its direct connectivity to other nodes. We formalize this with the concepts of neighbors and degree.

A node v is a neighbor of a node u if there is an edge connecting them. The set of all neighbors of a node u is called its neighborhood, often denoted as $N(u)$.

To get a quick feel for these terms, let's watch a short video clip.

As the video explained, the degree of a node is the number of edges connected to it. In an undirected graph, this is simply the size of its neighborhood.

Let's examine a more complex example to solidify these definitions. The graph below includes parallel edges (multiple edges between the same two nodes) and a self-loop (an edge connecting a node to itself).

Let's break down a few vertices from the image:

• Vertex c: It's connected to b and e. Thus, its neighborhood is $N(c)=\{b,e\}$ and its degree is 2.
• Vertex b: It's connected to a via two parallel edges, to c via one edge, and to f via one edge. It has 3 neighbors, but a total of 4 edges connected to it. So, its neighborhood is $N(b)=\{a,c,f\}$ and its degree is 4.
• Vertex f: It's connected to a and b, and it also has a self-loop. A self-loop adds 2 to the degree count (one for departure, one for arrival). Therefore, its degree is $1(\text{to a})+1(\text{to b})+2(\text{self-loop})=4$. Its neighborhood is $N(f)=\{a,b,f\}$.

Connecting to Graph Representations

These concepts map directly onto the data structures you learned about previously:

• In an adjacency list, the list of nodes associated with a given node u is precisely its list of neighbors. The degree of u is simply the length of this list.
• In an adjacency matrix of an unweighted, simple graph, the degree of a node i is the sum of the entries in row i (or column i, since the matrix is symmetric). You can find its neighbors by looking for all columns j where the entry $A_{ij}$ is 1.

Degree in Directed Graphs

In directed graphs, the concept of degree is refined to account for the direction of the edges. A node's connectivity is split into two types.

As you just read:

• In-degree: The number of incoming edges. For a node v, it's the number of edges that point to v.
• Out-degree: The number of outgoing edges. For a node v, it's the number of edges that start at v.

This distinction is very powerful. In a social network like Twitter, a user's in-degree is their follower count (a measure of popularity), while their out-degree is the number of accounts they follow (a measure of activity).

This also has a clear interpretation in the context of an adjacency matrix for a directed graph. For a node i:

• The out-degree is the sum of its row: ${\sum }_j{A}_{ij}$.
• The in-degree is the sum of its column: ${\sum }_j{A}_{ji}$.

The following resource provides a compact summary of these relationships.

Adding Richness: Weighted Edges

So far, we've treated all connections as equal. An edge either exists or it doesn't. However, in many real-world systems, relationships have varying strengths or costs. This is captured by weighted graphs.

In a weighted graph, each edge is assigned a numerical value, or weight. This weight can represent various metrics, such as:

• Distance or cost: The distance between two cities in a map graph.
• Bandwidth: The data capacity between routers in a computer network.
• Strength of relationship: The number of messages exchanged between two people in a communication network.
• Similarity: The similarity score between two documents or products.

An unweighted graph can be seen as a special case of a weighted graph where all edges have a weight of 1.

In weighted graphs, the concept of degree is extended to strength. The strength of a node is the sum of the weights of all edges connected to it. This provides a more nuanced measure of a node's connectivity than simply counting its neighbors. For instance, a node with two very high-weight connections might be more "important" than a node with five very low-weight connections.

Conclusion

In this lesson, we have defined the fundamental local properties of nodes and edges. These concepts are not just abstract graph theory; they are the building blocks for creating features and defining operations in GNNs.

Here are the key takeaways:

• Neighbors are the set of nodes directly connected to a given node.
• Degree is the number of edges connected to a node. For directed graphs, this is separated into in-degree (incoming edges) and out-degree (outgoing edges).
• Weighted edges add a numerical value to connections, representing concepts like distance, cost, or relationship strength. An unweighted graph is a special case where all weights are 1.
• Node strength is the sum of the weights of a node's connected edges, serving as the weighted equivalent of degree.

In the next lesson, we will move from describing individual nodes and edges to classifying entire graphs based on their overall structure. We will explore special graph types like bipartite, complete, and cyclic graphs, which have distinct properties that are important for certain types of problems.