1
$\begingroup$

So basically I'm choosing a set of numbers from a probability mass function, (say binomial or scale-free). By which I mean I'm performing a weighted choose operation using the PMF as weights. However I would ideally like to choose them so they add up to a specified total. How could I go about doing this without skewing the PMF? For example, if I simply chose the last number so that the total is met without going over, then the choices would no longer adhere to the distribution.

So to give you my use case, I found this generative model here which is the configuration model for generating scale free networks. This involves computing a finite version of the scale-free distribution and then randomly choosing (weighted by distribution) a degree for each node. However there is no way of specifying what the total edge count should be.

$\endgroup$
0
$\begingroup$

As you've stated the issue currently, I don't think it is possible, since you are drawing single samples independently and identically distributed, presumably. If you add a constraint that the sum must add to $T$, then that distribution must change (certain combinations of draw becoming impossible, for example, which used to be fine).

If you are on a small enough scale, one thing you could do is compute the constrained joint distribution, i.e. you draw $n$ samples at once $x_1,\ldots,x_n\sim J$, where $J$ is the set of all possible combinations of size $n$ such that $\sum_i x_i=T$.

Basically, you currently have $p(X=v_i) = p_i$, you need to figure out a new distribution $q$ where $q(X_1=v_{\alpha_1},\ldots, X_n= v_{\alpha_n}) = q_\alpha$ is a PMF on combinations of variables that sum to $T$. (You have to do this for each $n$ too, if that is not fixed).

In other words, let the set of possible values be $v_1,\ldots, v_n$. Figure out the set $S=\{ (v_1,\ldots,v_m) \mid m\geq 1, \sum_i v_i = T \}$, i.e. all possible combinations of variables that sum to $T$. Any sample from $S$ is now a valid sample. The only issue is how to weight them. Ideally, you can do this by figuring out the probability $p(S)$, i.e. the chance that choosing any random combination of values you choose is in $S$ (presumably there is a maximum number of choices you can make, i.e. maximum length of the sequence, say $L$... hopefully all $v_i$ are positive). Then you can just take $p(v) = p(v_1,\ldots,v_m) = \prod_j p_j / p(S)$, since $p(v|v\in S) = p(v,S)/p(S)$ to write it a bit... informally.

This construction basically takes the subspace of all possible subsets of choices that are valid (add up to $T$) and then reweights them according to the probability you would have seen using the original probabilities in the initial space (correcting the probabilities to account for the new subspace we are now operating in).

Of course, this is non-trivial :). The pdf you linked doesn't load for me (probably an issue on my end mind you). However, it sounds like you are sampling an integer for each node in a graph. If the number of nodes is fixed, then the construction I noted above is a little simpler, since $n=L=|V|$ is fixed, and may be tractable if $L$ is small. It is the most principled approach I can think of, which exactly preserves the original relative weighting while guaranteeing it adds to $T$.

The idea of sampling normally until the last node, then setting it equal to the difference seems problematic because you could hit $T$ before reaching the last node, no? And you cannot give the node a negative degree.

Note there is a trivial algorithm but slow algorithm which prevents skewing: just sample all of them as you were, then at the end if you are not equal to $T$, keep choosing new nodes (uniformly at random) and sample a new value for them, until the sum total is $T$. No skewing but might take a very very long time. You could speed this up by slightly skewing the distribution: when sampling nodes to retry, if you are below $T$, favour choosing nodes with small degrees, or favour larger degrees slightly more.


Now, if you can relax a bit the requirement that it sums to $T$, and just be near $T$, and you want to be fast, then perhaps you could do something a little cuter. :) Basically, we keep track of the total remaining number of nodes, and slightly skew our choices so that we will end up close to $T$, by putting a prior over the current sample that changes for each sample (depending on the previous samples). You can then manually balance you much each choice is allowed to be skewed versus how much you want to guarantee being close to $T$.

Let the original distribution over $v$ (a single node's degree) have an expected value of $\mathbb{E}[v]=:\mu_v$. Suppose we have already chosen degrees for $K$ nodes, and there are $U=|V|-K$ nodes left. Let $C_V$ be the set of degree values of the already chosen vertices, with sum $S_C=\sum_{v\in C_V} v$. We thus have "space left" given by $T - S_C$. But, the expected value of the total we will get is $ E_T = S_C + U\mu_v $. Let $\Delta = E_T - T$ be the expected difference between $T$ and $E_T$. If $\Delta$ is positive, we want to choose smaller values, and if it is negative, we want to choose larger values. (But we want to skew $p(v)$ as little as possible.) How to do this is up to you, but one way is to change $p(v)$ to $q(v)$ such that $\mathbb{E}_{v\sim q(v)}[v]U + S_C = S_C + U\sum_i v_iq_i = T$, where $v_i\in\{1,\ldots,n\}$ presumably. So, for the current node, we need $q$ such that: $$ \sum_i v_iq_i \approx (T - S_C) / U \;\;\;\;\&\;\;\;\; q_i \approx p_i $$ where the first constraint says that we are choosing a distribution such that if we follow it for $U$ more steps then we expect to end up with the sum at $T$, and the second constraint says that we cannot be too far from the "true" distribution over node degrees. This can be rewritten as a soft constraint optimization objective: $$ \mathcal{L}(q) = \left[ \frac{T - S_C}{U} - \sum_i v_iq_i \right]^2 + \gamma\sum_i (p_i - q_i)^2 + \xi \left(1 - \sum_j q_j\right)^2 $$ where we want $q^* = \arg\min_q \mathcal{L}(q)$ and $\gamma$ controls how much we care about the first versus second constraint. (The third term is to make it close to a probability distribution). Let's check the derivative $$ \partial_{q_k} \mathcal{L} = -2v_k\left[ \frac{T - S_C}{U} - \sum_i v_iq_i \right] - 2\gamma(p_k - q_k) - 2\xi \left(1 - \sum_j q_j\right) = [\nabla_q \mathcal{L}(q)]_k $$ (Please do this yourself as I may [almost certainly] have made mistakes). This doesn't seem analytically solvable, but we can do a very quick gradient descent : $q^{(t)} \leftarrow q^{(t-1)} - \eta\nabla_q \mathcal{L}(q^{(t-1)})$ Obviously more sophisticated algos could also be used and/or automatic differentiation. So we can basically do the following algorithm:

  1. Draw a value for a node from $p$

  2. Until all the nodes have chosen values:

    • Choose a random node $a$

    • Compute $q$ via a few fast optimization steps (not many maybe needed, it's random anyway)

    • Normalize $q$ (or use it to parameterize a Dirichlet distribution and draw $q$ from that)

    • Sample a random node value (degree) from $q$ and assign it to $a$

This algorithm states that every time we choose a node, we minimally adjust the PMF $p$ over degrees such that the expected total sum over nodes will be close to $T$. Of course, it won't be exactly, but it should be close (if you run this many times, the average sum should be $T$), depending on $\gamma$, $\xi$, optimization quality, the prior distribution $p$, the problem itself, etc... For instance, if $\mu_v$ is larger than $T$, this is already very hard :)

Once you have something near $T$, then maybe you can do some smaller, more reasonable changes to get it to $T$.

Well, I better stop rambling now, let me know if you want clarifications. Or if I totally misunderstood the question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.