A system consists of $N$ nodes. The nodes are distributed into $M$ clusters such that each node belongs to a unique cluster. Each cluster $i$ has one unit of weight, $w_i = 1$. Thus the initial weight of the system is $ \sum_{i=1}^M w_i = M$. We sequentially select $Q$ random nodes. Every time a node is selected, the weight of the cluster the node belongs to becomes zero. We want to derive an expression for the average number of $Q$ node selections needed to set the weight of the system to $0$. The size of the clusters follow a power-law distribution of the form $P(\mu) \sim \mu^{- \tau}$, where $P(\mu)$ is the probability of finding a cluster with $\mu$ nodes.
To model this problem, we will introduce the following notation:
- $N(t)$: The total number of remaining nodes at any time $t$ (after $t$ nodes have been picked).
- $M(t)$: The total number of $w=1$ clusters remaining at time $t$.
The rate of change of $M(t)$ depends on the probability of picking a node from an $w=1$ cluster. This probability changes as clusters loose weight once a node of the cluster has been picked. We can express this as:
\begin{equation} \frac{dM}{dt} = -f(N(t), M(t), \tau) \end{equation} where:
- $\frac{dM}{dt}$ is the rate of change of the number of $w=1$ clusters.
- $f(N(t), M(t), \tau)$ is a function representing the probability of picking a node from an $w=1$ cluster, which depends on the current number of nodes, the number of $w=1$ clusters, and the power-law exponent $\tau$.
The solution to this differential equation would give us $M(t)$, from which we could find the time $t$ (or number of nodes picked) at which $M(t)=0$, indicating all weights are destroyed.
Is this the right way to think about this problem?
The form of the function $f$ is complicated because:
- The probability of picking a node from any given cluster depends on its size, which follows the power-law distribution.
- As nodes are picked, the distribution of remaining nodes across clusters changes.
- The number of nodes in $w=1$ clusters decreases over time, altering the probabilities.
How would one go about guessing the form of $f$?