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 in ?sec-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.