The Lambert W-function is the function w(z) implicitly defined by w exp(w) = z. When I first saw this, I thought that I’d seen something like this come up many times and that it would be really handy to know that this function has a name and has many software implementations . Since then, however, I’ve hardly ever run into the W-function in application. But here’s an application I ran into recently.
A “giant component” in a random network is a component whose size grows in proportion to the size of the network. For a Poisson random network, let c = p(n – 1) be the expected number of vertices connected to any given vertex. If c > 1 then as n goes to infinity, there will be a giant component with probability 1. S, the proportion of nodes inside the a giant component, satisfies the equation
S = 1 – exp(-cS).
S plays a role similar to that of w in the definition of the W-function, which suggests the W-function might come in handy. And in fact, this book gives this solution for S:
S = 1 + w( –c exp(-c) )/c.
There are a couple issues. First, it’s not obvious that solution is correct. Second, we need to be more careful about how we define w(z) when z is negative.
Given some value of c, let S = 1 + w( –c exp(-c) )/c. Then
w( –c exp(-c) ) = –c(1 – S).
Apply the function f(x) = x exp( x ) to both sides of the equation above. By the definition of the W-function, we have
–c exp(-c) = –c(1 – S) exp( –c(1 – S) ).
From there it easily follows that
S = 1 – exp(-cS).
Now let’s look more carefully at the definition of the W-function. For positive real z, w exp(w) = z has a unique real solution defining w. But in the calculations above, we have evaluated w at –c exp(-c), which is negative since c > 1. For negative arguments, we have to pick a branch of w. Which branch guarantees that S = 1 – exp(-cS)? Any branch . No matter which solution to w exp(w) = z we pick, the resulting S satisfies the giant component equation. However, the wrong branch might result in a meaningless solution. Since S is a proportion, S should be between 0 and 1.
Let’s go back and say that for our purposes, we will take w(z) to mean the real number no less than -1 satisfying w exp(w) = z. Then for c > 1, the solution S = 1 + w( –c exp(-c) )/c is between 0 and 1. You can show that S = 1 – exp(-cS) has a unique solution for 0 < S < 1, so any other branch would not give a solution in this interval.
Related post: Measuring graph connectivity with eigenvalues
 For example, in Python the Lambert W-function is
scipy.special.lambertw. The function takes two arguments: z and an integer denoting the branch. By default, the branch argument is set to 0, giving the branch discussed in this post.
 For -1/e < z < 0, there are two real branches of w(z), but there are also infinitely many complex branches.
3 thoughts on “Giant components and the Lambert W-function”
The Lambert w function is actually great for puzzles. Formulate a problem that reduces to $w exp(w) = z$ for a known $z$ and watch your unsuspecting victim suffer while trying to find a closed form solution for $w$, bwhahaha!
I met the Lambert function when solving a problem originally related to a cache model (random strategy, loop references), the abstract setting is http://math.stackexchange.com/questions/52972/a-probabilistic-game-with-balls-and-urns Asymtotically, the “hit probability” can be expressed as a Lambert function.
Another implementation: http://www.gnu.org/software/gsl/manual/html_node/Lambert-W-Functions.html