Skip to the quick start

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

This page visualizes a key idea from Søren Riis’ 2007 preprint: a multiple-unicast network coding instance can be “glued” into a directed graph, and solvability becomes a statement about the graph’s guessing number / entropy.

← Research demos

From a shared guessing rule to a communication network

Start with Signal Club →
First visit · three things to try
  1. Start with the triangle. Choose “Butterfly-style”, alphabet 2 and the sum strategy. Four of the eight assignments are fixed points: every guess matches its symbol.
  2. Change to constant guessing. Only one assignment survives. The achieved value falls from 2 to 0, although the graph itself has not changed.
  3. Compare Split A and Split B. A split separates selected vertices into message sources and destinations. Follow the corresponding labels across the three diagrams.
How to read the results

A fixed point is a complete assignment on which all local rules are correct. The displayed value belongs to the selected strategy; the guessing number maximises this value over every legal strategy. The theorem examples and entropy language are optional deeper material.

Controls

Hover nodes/edges to highlight across panels.

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…

Strategy used here

Local rule(s) used as guessing + coding functions.

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

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

Multiple-unicast network (Split A)

Split set B = —

Loading…

Glue sources with targets → guessing graph

Glued directed graph (guessing game).

Loading…

Another split of the same glued graph (Split B)

Split set B = —

Loading…

What the numbers show

We enumerate the fixed points for the chosen strategy and alphabet. The graph’s guessing number is the maximum over all admissible strategies.

Fixed points in glued graph
—
—
Value achieved by this strategy
—
logₛ(#fixed points for the selected strategy)
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.

How this matches the paper

The references below give the precise network-coding statements.

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 bidirected 5-cycle C5, whose guessing number is 2.5 for square alphabet sizes (and asymptotically). 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 (2011). “Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications”, IEEE Transactions on Information Theory. Hosted PDF