mathematics//graph theory//adjacency and degree
Adjacency and degree describe the structure a network keeps before any law of evolution is chosen. A **graph** is nodes and edges. Nodes can be tanks, sensors, states of a Markov chain or data samples. Edges are a relation defined for the problem: a pipe, a dependence, an allowed transition or a similarity. The **topology** says which connections exist; the **weights** add intensity. Neither decides on its own what quantity evolves or under which law.
Adjacency and degree describe the structure a network keeps before any law of evolution is chosen. A graph is nodes and edges. Nodes can be tanks, sensors, states of a Markov chain or data samples. Edges are a relation defined for the problem: a pipe, a dependence, an allowed transition or a similarity. The topology says which connections exist; the weights add intensity. Neither decides on its own what quantity evolves or under which law.
The weight matrix and the degrees hold that structure in numbers. For an undirected network with non-negative weights and no self-loops, they are
Wij=Wji≥0,Wii=0,di=∑jWij,D=diag(di).\ca{W_{ij}}=\ca{W_{ji}}\ge0,\quad \ca{W_{ii}}=0,\qquad \cb{d_i}=\sum_j\ca{W_{ij}},\qquad \cb{D}=\operatorname{diag}(\cb{d_i}).Wij=Wji≥0,Wii=0,di=j∑Wij,D=diag(di).
The weights in green, the degrees in blue. W\ca{W}W is the weighted adjacency and D\cb{D}D holds the weighted degrees; much of the control and GNN literature calls the same matrix AAA, with Aij=wijA_{ij}=\ca{w_{ij}}Aij=wij. With unit weights the degree counts neighbors; with conductances it sums conductances; with affinities it sums similarities, which does not make it a physical capacity. In a drone fleet's communication graph the degree is the number of drones a drone hears, and the largest degree sets the safe step of a consensus protocol.
Powers count walks, not just direct connections: (W2)ij=∑ℓWiℓWℓj(\ca{W}^2)_{ij}=\sum_\ell \ca{W_{i\ell}}\ca{W_{\ell j}}(W2)ij=∑ℓWiℓWℓj. In a binary adjacency, (Wk)ij(\ca{W}^k)_{ij}(Wk)ij counts walks of length kkk, allowing repeated nodes and edges; it does not count only simple paths. With weights it sums products of weights along those walks. For a transition matrix the same multiplication sums probabilities of compatible alternatives: same algebra, different meaning of the entries.
12345 104152 240512 315264 451624 522442 W^3 for the house graph of 5 nodes, degrees 2, 2, 3, 3, 2: entry (i, j) counts the walks of 3 steps from i to j, nodes and edges may repeat.
Tap a start and an end, raise kkk and run the listed walks on the graph: each one is counted in the highlighted entry, back-and-forth steps included.
Direction needs a convention. In a directed transport graph, Wij\ca{W_{ij}}Wij can be the weight of the transition from iii to jjj. But in x˙i=∑jwij(xj−xi)\dot x_i=\sum_j\ca{w_{ij}}(x_j-x_i)x˙i=∑jwij(xj−xi) the coefficient wij\ca{w_{ij}}wij means that iii uses the value of jjj: the dynamic dependence goes from jjj to iii. Arrows cannot be carried between transport and dependence without revisiting the indices. A symmetric network hides this ambiguity; a directed one exposes it.
Affinity is not distance. To group data, a large weight usually means similarity, not separation. A large distance must not become a strong edge as is; it can be transformed through a decreasing function, as spectral clustering does.
The two matrices are also the skeleton of a graph network. A graph convolutional layer multiplies the node features by the normalized adjacency D~−1/2(W+I)D~−1/2\tilde D^{-1/2}(\ca{W}+I)\tilde D^{-1/2}D~−1/2(W+I)D~−1/2, where D~\tilde DD~ is the degree matrix of W+I\ca{W}+IW+I: a step of averaging with the neighbours, followed by learned weights (GNN).
The graph Laplacian converts connections into local differences. Coupling interprets dynamic dependencies. A statistical association (covariance) is not automatically a causal edge.