Variable set size
Constructing graphs from genetic encodings
Sci Rep, Jun 24, 2021; DOI: 10.1038/s41598-021-92577-2

In this section we expand the simplifying assumption of mapping networks with constant set sizes, allowing now for sizes to be distributed according to q(s). The method in the previous section, where we mapped with fixed set sizes, is a special case of this with q(s)=δ(s-s0).

Given an edge between two sets of sizes si and sj drawn from q(s), sisj edges are introduced into the node-level network. The expected number of links at the node level is therefore the number of rules multiplied by a factor of s1s2=s2. The expected density can then be expressed as

when Nsets>>1. Thus, the overall density is not expected to differ from the ER network, even with variable set sizes.

To derive the degree distribution, we consider a set with degree kj at the set-level network. Such a set contains sj nodes, each with the same degree Kj=i=1ksi. Depending on q(s) and the degree distribution pk of the set-level network, the resulting expected degree distribution of the node-level network pK is given by

According to the law of total expectation and the law of total variance,


If the set-level model is an ER network, having Poisson degree distribution with σ2(k)=k, (12) simplifies to σ2(K)=ks2=Ks2s. The GM(ER) model under variable set size therefore has a degree distribution with Fano-factor (as a measure of dispersion) σ2(K)K=s2s.