Directed Graph Degrees: In-degree and Out-degree

In-degree and Out-degree in Directed Networks

• A directed network (digraph) has nodes (vertices) and arcs (directed edges).
• For any node v in a directed graph G = (V, E):
  • In-degree: k_{\mathrm{in}}(v) = |{(u, v) \in E}|
  • Out-degree: k_{\mathrm{out}}(v) = |{(v, w) \in E}|
  • Total degree (sometimes called just the degree in a directed graph): k(v) = k{\mathrm{in}}(v) + k{\mathrm{out}}(v)
• Important distinction from undirected graphs: undirected degree counts incident edges; directed graphs separate incoming and outgoing counts.
• Important note about the arc total: not all statements in informal notes are correct—correct identities are:
  • Sum of in-degrees over all nodes equals the number of arcs: \sum{v \in V} k{\mathrm{in}}(v) = |E| = m
  • Sum of out-degrees over all nodes equals the number of arcs: \sum{v \in V} k{\mathrm{out}}(v) = |E| = m
  • Therefore, the sum of total degrees over all nodes equals twice the number of arcs: \sum{v \in V} k(v) = \sum{v \in V} [k{\mathrm{in}}(v) + k{\mathrm{out}}(v)] = 2m
• The transcript’s line "The sum of in degree and out degree for all nodes equals the number of arcs" is a common shorthand but should be interpreted as: the sum of in-degrees across all nodes equals m, and the sum of out-degrees across all nodes also equals m; together, the sum of total degrees across all nodes equals 2m.

Core definitions and notation

• Let G = (V, E) be a directed graph with n = |V| nodes and m = |E| arcs.
• For a node v ∈ V:
  • Incoming count: k_{\mathrm{in}}(v) = |{(u, v) \in E}|
  • Outgoing count: k_{\mathrm{out}}(v) = |{(v, w) \in E}|
  • Total degree: k(v) = k{\mathrm{in}}(v) + k{\mathrm{out}}(v)
• Self-loops contribute 1 to both in-degree and out-degree of the same node: if (v, v) ∈ E, then it adds 1 to k{\mathrm{in}}(v) and 1 to k{\mathrm{out}}(v).

Fundamental identities and relationships

• Arc counts:
  • \sum{v \in V} k{\mathrm{in}}(v) = m
  • \sum{v \in V} k{\mathrm{out}}(v) = m
• Total degree sum:
  • \sum{v \in V} k(v) = \sum{v \in V} [k{\mathrm{in}}(v) + k{\mathrm{out}}(v)] = 2m
• Average degrees (per node):
  • Average in-degree: \frac{1}{n} \sum{v \in V} k{\mathrm{in}}(v) = \frac{m}{n}
  • Average out-degree: \frac{1}{n} \sum{v \in V} k{\mathrm{out}}(v) = \frac{m}{n}
  • Average total degree: \frac{1}{n} \sum_{v \in V} k(v) = \frac{2m}{n}

Worked example

• Let V = {A, B, C} and E = { (A, B), (A, C), (B, C) } (m = 3).
  • Node A: k{\mathrm{in}}(A) = 0\,,\ k{\mathrm{out}}(A) = 2\,, so k(A) = 2
  • Node B: k{\mathrm{in}}(B) = 1\,,\ k{\mathrm{out}}(B) = 1\,, so k(B) = 2
  • Node C: k{\mathrm{in}}(C) = 2\,,\ k{\mathrm{out}}(C) = 0\,, so k(C) = 2
• Checks:
  • Sum of in-degrees: 0 + 1 + 2 = 3 = m
  • Sum of out-degrees: 2 + 1 + 0 = 3 = m
  • Sum of total degrees: 2 + 2 + 2 = 6 = 2m

Computation via adjacency matrix

• Let A be the adjacency matrix with entries A_{ij} = 1 if arc from i to j exists, and 0 otherwise.
• Then for any vertex j:
  • Incoming degree: k{\mathrm{in}}(j) = \sum{i} A_{ij}
  • Outgoing degree: k{\mathrm{out}}(i) = \sum{j} A_{ij}
• In a weighted digraph, replace sums of 1’s with sums of weights; still, degrees summarize counts or total weights of incident arcs in the respective direction.

Practical interpretations and real-world relevance

• In-degree centrality: nodes with high k_{in} may receive information from many sources; representative of popularity or influence in terms of incoming signals.
• Out-degree centrality: nodes with high k_{out} may disseminate information to many others; representative of broadcasting capacity or responsiveness.
• Total degree k(v) provides a quick measure of a node's overall connectivity in the directed sense.
• In many real networks, degree distributions follow heavy tails (power-law), implying a few nodes with very high degrees act as hubs.
• Limitations: degree alone does not capture path structure, weights, directions of flow, or network topology beyond immediate neighbors.

Connections to related concepts

• In undirected graphs, degree is simply the number of incident edges; directed graphs require separating in-degree and out-degree.
• If the network is converted to an undirected one by ignoring edge directions, the degree in the undirected graph relates to the sum of the two directed degrees for each node, but counts become different due to directionality being ignored.
• For path-based measures (e.g., betweenness, PageRank), degrees are a starting point but insufficient to describe node importance fully.

Common pitfalls and quick recap

• Pitfall: assuming the total degree across all nodes equals m. Correction: the sum of in-degrees over all nodes equals m, and the sum of out-degrees over all nodes also equals m; therefore the sum of total degrees equals 2m.
• Pitfall: forgetting that self-loops add to both in-degree and out-degree of the same node.
• Quick recap formulas:
  • k_{\mathrm{in}}(v) = |{(u, v) \in E}|
  • k_{\mathrm{out}}(v) = |{(v, w) \in E}|
  • k(v) = k{\mathrm{in}}(v) + k{\mathrm{out}}(v)
  • \sum{v \in V} k{\mathrm{in}}(v) = m, \quad \sum{v \in V} k{\mathrm{out}}(v) = m, \quad \sum_{v \in V} k(v) = 2m

This set of notes covers the key ideas, formulas, and implications related to in-degree and out-degree in directed networks, with corrections to common informal statements and a clear worked example to anchor understanding.