Graph Entropy ↔ Network Coding ↔ Guessing Games (Riis)

This demo needs JavaScript enabled. If JavaScript is disabled, the diagrams and computed values will not appear.

Example Alphabet size s Strategy Parameter c Split A Split B

In the guessing game on a directed graph, each vertex must guess its own value from its in-neighbours. The same local functions can also be used as coding functions on any acyclic split of the glued graph (Theorem 8 / Corollary 9 in the preprint). Pick an example + split(s) below to see the correspondence numerically.

Runtime: waiting for JavaScript…

Local rule (guessing / coding functions):
x̂_i = (c − Σ_{u∈Pred(i)} x_u) mod s

source (input) target (output) internal node glued vertex

Fixed points in glued graph

—

Guessing number g(G, s)

—

g(G, s) = logₛ(#fixed points)

Split A: inputs decoded correctly

—

Split B: inputs decoded correctly

—

For a split with k input–output pairs, the network is solved (over alphabet A with |A|=s) if and only if the glued graph has sᵏ fixed points under some guessing strategy — i.e. guessing number / entropy k. This page evaluates the selected local rule; it does not search over all possible rules.

Core statements (informal)

“Glue” a multiple-unicast network by identifying each source with its corresponding target; this gives a directed graph Gₙ.
The graph’s entropy equals its guessing number (Theorem 1 in the preprint).
Solvability of the network over an alphabet A is equivalent to the glued graph having entropy / guessing number k over A (Corollary 9 in the preprint).
Different minimal “splits” of the same glued graph yield different acyclic multiple-unicast instances, but the same local functions solve all of them (Theorem 8 and the discussion right after it).

What “split” means here

Pick a vertex set B. Splitting duplicates each v∈B into a source vᵢₙ (keeps outgoing edges) and a target vₒᵤₜ (keeps incoming edges). This breaks all directed cycles that rely on passing “through” vertices in B.

Note: K5 vs C5

A common non-integer example is the 5-cycle C5, whose guessing number is 2.5. The complete graph K5 (viewed as a complete digraph) has guessing number 4; the “sum strategy” achieves s⁴ fixed points.

References

Søren Riis (2007). Preprint introducing the gluing/splitting viewpoint: NetworkCoding/RiisTRGraphEntro.tex
Maximilien Gadouleau, Søren Riis (2012). “Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications”, IEEE Transactions on Information Theory.

Graph entropy ↔ network coding ↔ guessing games (Riis, 2007)

Controls

Strategy used here

Multiple-unicast network (Split A)

Glue sources with targets → guessing graph

Another split of the same glued graph (Split B)

What the numbers show

How this matches the paper