What happens for a complete graph?

Graph entropy equals the Shannon entropy of the vertex distribution.

What happens for an edgeless graph?

It is zero under this definition, because all vertices may belong to one stable set.

Does adding edges increase entropy?

With the same vertex distribution, it cannot decrease it; additional edges restrict the allowed stable sets.

AI Glossary / Mathematics and optimization / Advanced

Graph entropy

Definition

In the information-theoretic sense associated with Körner, graph entropy measures a graph together with a probability distribution over its vertices. It captures an information requirement determined by which vertex pairs must remain distinguishable, rather than merely applying Shannon entropy to vertex degrees.

What it means

A graph describes relationships, while a vertex distribution describes how frequently its possible symbols occur. Both affect graph entropy. Two applications using the same graph can therefore obtain different values if their symbol probabilities differ.

The term also appears in other network-analysis measures, including degree-based and spectral constructions. Those are not automatically equivalent. This entry uses the stable-set definition of Körner graph entropy, with edges representing pairs that must be distinguished. Reversing that edge interpretation changes the problem.

How it works

An independent, or stable, set contains no adjacent vertices. Form the convex hull of the zero-one membership vectors of all stable sets; this is the vertex packing polytope. A vector a in that polytope can be viewed as the vertex inclusion probabilities obtained by randomly choosing a stable set.

For vertex probabilities p_i, graph entropy is the minimum of the sum of p_i log_2(1/a_i) over that polytope. A zero inclusion probability for a positive-probability vertex gives an infinite contribution. Zero-probability vertices contribute zero under the usual convention.

The distribution p and the inclusion vector a play different roles. The p values sum to one; the a values need not. Stable sets can contain several vertices, so their inclusion probabilities are not a probability distribution over individual vertices.

Three practical examples

1. Information coding: model which source symbols must receive distinguishable descriptions, taking their frequencies into account. Graph entropy supplies an asymptotic information-theoretic quantity under the relevant coding formulation.

2. Comparing requirements: keep the source distribution fixed but add distinctions between symbol pairs. The feasible stable sets become more restricted, so this graph entropy cannot decrease.

3. Research interpretation: when a network study reports graph entropy, inspect its exact definition. A degree-distribution entropy and Körner graph entropy can answer different questions even if both are measured using logarithms.

Think of it this way

Imagine a labeling system in which some pairs of items must have different labels, while other pairs may share one. The relationship graph records the required distinctions, and frequencies record how often items arise. Graph entropy combines those ingredients; it does not measure complexity from the number of connections alone.

Worked example

Consider a three-vertex path A - B - C, with edges AB and BC but no edge AC. Suppose each vertex has probability one-third. The largest stable sets are {A, C} and {B}.

Choose {A, C} with probability q and {B} with probability 1 − q. The inclusion vector is then a = (q, 1 − q, q). For this path, smaller stable sets cannot improve the objective: their inclusion vectors can be increased by assigning their probability to one of these maximal sets.

The objective becomes −(2/3)log_2 q − (1/3)log_2(1 − q). Differentiating, or recognizing the matching binary proportions, gives the minimizing choice q = 2/3. Thus a = (2/3, 1/3, 2/3).

Substitution gives graph entropy (2/3)log_2(3/2) + (1/3)log_2 3, approximately 0.918296 bits. Notice that the inclusion coordinates sum to 5/3, which is valid: choosing {A, C} includes two vertices simultaneously.

If edge AC is added, the graph becomes complete. Only singleton stable sets can be nonempty, and the optimum for the uniform distribution is a = (1/3, 1/3, 1/3). Entropy becomes log_2 3, approximately 1.584963 bits. If all edges are removed, choosing the entire vertex set gives a = (1, 1, 1) and entropy zero.

Finally, retain the original path but change the vertex probabilities to (0.25, 0.5, 0.25). The minimizing q is now 0.5 and graph entropy is one bit. With probabilities (0.45, 0.1, 0.45), q becomes 0.9 and entropy is approximately 0.468996 bits.

These changes show that neither the vertex count nor the edge count alone determines the answer. The required distinctions and their frequencies interact.

Illustrative case study

In a fictional information-management project, an analyst proposes using graph entropy to assess a symbol-labeling scheme. A first dashboard instead computes Shannon entropy from normalized vertex degrees and presents that number as the coding requirement.

Review identifies the mismatch. The team specifies which symbol pairs require distinction, estimates a vertex distribution and uses the appropriate mathematical definition. It also records that the information-theoretic rate is an asymptotic benchmark, not a ready-made code length for each individual item.

A numerical entropy value is useful only when the graph convention, probability model and operational meaning are explicit.

Common misconceptions and mistakes

Graph entropy is not one universally defined scalar across every discipline. State which entropy construction is being used.

Do not normalize the inclusion vector a to sum to one. That would alter the stable-set optimization and can exclude valid solutions, as the worked path demonstrates.

Do not confuse a stable set with a clique. Stable sets contain no adjacent pair; cliques have every possible pair connected.

A convex objective does not make the whole calculation automatically easy. Describing or optimizing over the stable-set polytope can be computationally demanding for general graphs.

A fractional number of bits is not a claim that an individual stored label occupies a fraction of a physical bit.

Business use

The concept is relevant to specialized coding, combinatorial optimization and analytical research where a graph represents meaningful distinctions. It is less useful as an unexplained general-purpose score of network quality or organizational complexity.

Before comparing results, confirm identical edge conventions, vertex probabilities, logarithm bases and definitions. A change in the source distribution can change the score without any change in the underlying relationships, so interpretation requires both pieces of evidence.

Check your understanding

Which two vertices can share a stable set in the path example?

Answer: A and C.

Why may inclusion coordinates sum to more than one?

Answer: A randomly chosen stable set may include several vertices.

What is the uniform path's entropy?

Answer: Approximately 0.918296 bits, compared with approximately 1.584963 bits for the complete three-vertex graph.

Related terms

Graph coloring
Mutual information
Perfect Graph
Shannon entropy
independent set
vertex packing polytope
chromatic entropy

Learn next

Derive the path's optimum q for an arbitrary positive probability on B. Then compare graph entropy with the entropy of a particular proper coloring, keeping the definitions and probability distributions explicit.

Sources

Gábor Simonyi, Perfect Graphs and Graph Entropy: An Updated Survey, definitions and information-theoretic interpretation: https://www.renyi.hu/~simonyi/perfhgp.pdf

The three-vertex calculations and information-management case are original illustrations.

Previous: Graph-cut segmentation Next: Graph Hashing