mathematics//graph theory//adjacency and degree
What 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.
What 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.
Weight matrix and degree. For an undirected network with non-negative weights and no self-loops,
Wij=Wji≥0,Wii=0,di=∑jWij,D=diag(di).W_{ij}=W_{ji}\ge0,\quad W_{ii}=0,\qquad d_i=\sum_jW_{ij},\qquad D=\operatorname{diag}(d_i).Wij=Wji≥0,Wii=0,di=j∑Wij,D=diag(di).
WWW is the weighted adjacency and DDD holds the weighted degrees. 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.
Powers count walks, not just direct connections: (W2)ij=∑ℓWiℓWℓj(W^2){ij}=\sum\ell W_{i\ell}W_{\ell j}(W2)ij=∑ℓWiℓWℓj. In a binary adjacency, (Wk)ij(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.
Direction needs a convention. In a directed transport graph, WijW_{ij}Wij can be the weight of the transition from iii to jjj. But in x˙i=∑jwij(xj−xi)\dot x_i=\sum_jw_{ij}(x_j-x_i)x˙i=∑jwij(xj−xi) the coefficient wijw_{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 graph Laplacian converts connections into local differences. Coupling interprets dynamic dependencies. A statistical association (covariance) is not automatically a causal edge.