The guessing number of a directed graph (digraph), equivalent to the entropyof that digraph, was introduced as a direct criterion on the solvability of anetwork coding instance. This paper makes two contributions on the guessingnumber. First, we introduce an undirected graph on all possible configurationsof the digraph, referred to as the guessing graph, which encapsulates theessence of dependence amongst configurations. We prove that the guessing numberof a digraph is equal to the logarithm of the independence number of itsguessing graph. Therefore, network coding solvability is no more a problem onthe operations made by each node, but is simplified into a problem on themessages that can transit through the network. By studying the guessing graphof a given digraph, and how to combine digraphs or alphabets, we are thus ableto derive bounds on the guessing number of digraphs. Second, we constructspecific digraphs with high guessing numbers, yielding network coding instanceswhere a large amount of information can transit. We first propose aconstruction of digraphs with finite parameters based on cyclic codes, withguessing number equal to the degree of the generator polynomial. We thenconstruct an infinite class of digraphs with arbitrary girth for which theratio between the linear guessing number and the number of vertices tends toone, despite these digraphs being arbitrarily sparse. These constructions yieldsolvable network coding instances with a relatively small number ofintermediate nodes for which the node operations are known and linear, althoughthese instances are sparse and the sources are arbitrarily far from theircorresponding sinks.
展开▼
