outdegree

Outdegree is a basic concept in directed graphs. It measures how many edges originate from a given vertex, reflecting its level of activity or influence in the local network.

Formally, in a directed graph G = (V,E), the outdegree of a vertex v ∈ V, denoted deg+(v) or outdeg(v), is the number of edges that start at v. Equivalently, deg+(v) = |{ (v,u) ∈ E : u ∈ V }|. The indegree deg−(v) counts the edges that end at v. In a simple digraph (without parallel edges or loops), the outdegree is simply the number of distinct immediate successors of v.

Key properties include that the sum of outdegrees over all vertices equals the total number of edges, |E|, in any finite directed graph, since each edge contributes exactly one to the outdegree of its origin. The outdegree can be read from representations: in an adjacency matrix, the row corresponding to v sums to deg+(v); in an adjacency list, it is the length of the list of v’s outgoing neighbors.

Related concepts are the indegree, degree (for undirected graphs), and degree sequences. Variants exist for weighted or multi-directed graphs: the standard outdegree counts edges, while the out-strength or weighted outdegree sums the weights of outgoing edges.

Applications of outdegree include characterizing network structure, identifying highly active nodes, and informing algorithms that propagate information or probabilities along outgoing links. It is a fundamental measure in social, web, citation, and transportation networks.