# 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 FreeHortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

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

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub. Join the discussion.

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 }}