# Giant components and the Lambert W-function

# Giant components and the Lambert W-function

Join the DZone community and get the full member experience.

Join For FreeThe 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^{1}. 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 link: Lambert W poster

^{1} 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.

Published at DZone with permission of John Cook , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

## {{ parent.title || parent.header.title}}

{{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}