8 Nodes and their Degrees
8.1 Node Degree in Undirected Graphs
In an undirected graph, a given node’s degree can be defined in two ways, both of which lead to the same answer.
One way to think about the degree of a given node \(i\) in a graph (written \(k_i\)) is as the cardinality of the set of neighbors of that node as defined earlier:
\[ k_i = |\mathcal{N}(i)| \tag{8.1}\]
So in the graph shown in Figure 7.1:
\[ k_A = |\mathcal{N}(A)| = |\{B, C, D, F\}|=4 \tag{8.2}\]
Another way to think about node degree is not as the cardinality of the node neighborhood set, but as a count of edges. In this case, we count the number of edges that have a given node \(i\) as one of their endpoints. Recall, that an edge that has a given node as one of their endpoints is said to be incident upon that node. So in the graph shown in Figure 7.1, the set of edges that have node A as one of their endpoints is:
\[ k_A = \{AB, AC, AD, AF\} \]
Which means that:
\[ |k_A| = 4 \] Either way, computing degree as the cardinality of the node’s neighbor set or as the number of edges incident upon the node, gives us the number of other people that a given node is connected to in the network. We will see when we talk about centrality, that this is an important measure of node position called degree centrality (Freeman 1977).
In a graph, nodes that have a degree equal to one, and thus have just a single neighbor in the graph, are called endpoints of the graph. Thus, in Figure 7.1, node \(C\) is an endpoint.
8.2 Node Degree in Directed Graphs
Because in a directed graph, each node has two distinct set of neighbors, we can compute two versions of degree for the same node.
in a directed graph, for any node i, we can count the number of edges that have a given node \(v\) as their destination node. This is also the cardinality of the in-neighborhood set of that node. This is called a node’s indegree and it is written \(k^{in}_i\), where i is the label corresponding to that node.
Additionally, in a directed graph, for any node i, we can count the number of edges that have a given node \(i\) as their source node. This is also the cardinality of the out-neighborhood set of that node. This is called that node’s outdegree and it is written as \(k^{out}_i\), where i is the label corresponding to that node.
For instance, in Figure 5.2, \(k^{out}_B = 3\) and \(k^{in}_B = 2\). Node B has three outgoing ties (from nodes A, C, and D) and three incoming ties (from nodes A and D).
Can you calculate what the indegree and outdegree of node D in Figure 5.2 is?
The graph theoretic ideas of indegree and outdegree have clear sociological interpretations. In a social network, for instance, a node having a large outdegree could indicate a sociable person (a person that likes to connect with others), while having a large indegree can indicate a popular person (e.g., a person lots of other people want to be friends with). In a later lesson we will see how to use a directed graph’s asymmetric adjacency matrix to readily compute the outdegree and indegree in real social networks.