Weighted networks as randomly reinforced urn processes

We analyze weighted networks as randomly reinforced urn processes, in which the edge-total weights are determined by a reinforcement mechanism. We develop a statistical test and a procedure based on it to study the evolution of networks over time, detecting the “dominance” of some edges with respect to the others and then assessing if a given instance of the network is taken at its steady state or not. Distance from the steady state can be considered as a measure of the relevance of the observed properties of the network. Our results are quite general, in the sense that they are not based on a particular probability distribution or functional form of the random weights. Moreover, the proposed tool can be applied also to dense networks, which have received little attention by the network community so far, since they are often problematic. We apply our procedure in the context of the International Trade Network, determining a core of “dominant edges.”

Figure 1

We performed some simulations of the model (with $L=2500$ and ${10}^6$ extractions) in both cases of no dominant set (one class) and of a dominant set (two classes). On the left we plot the frequency distributions of the weights in the case of uniform/truncated Gaussian (G) distributions of the random variables $W$. On the right we plot the normalized number of extractions of each edge/color in the case of no dominant set (up) and in the case of two classes with the set $[1,1250]$ as the dominant set (below).

Figure 2

In the lower panel we plot the number of no-rejections $N_c$ for the COMTRADE data (solid blue line) and for the simulated data of an urn with colored balls in the case of uniform distributions ($t={10}^6$ dotted and dashed red line, $t=250000$ dashed black line, and $t=125000$ dotted black line). For both cases we ordered the edges/colors in descending order according to the total edge-weight/number of added balls and we considered as ${\mathcal{D}}^{*}$ the set of the top 2000 edges/colors. We then executed the test taking ${\ell }^{*}$ in ${\mathcal{D}}^{*}$ running from the highest to the lowest value and accumulating the number of no-rejections in the $y$ axis. After a constant no-rejection rate, the curves associated to simulations start bending, exactly in correspondence of the true dominant set (the top 1250 edges), known a priori. The turning point is always the same, but the higher $t$ is, the sharper the turning point is. The curve associated to COMTRADE has a similar trend with a turning point around 500, which reveals the presence of a core subset of dominant edges (the top 500 edges). In the inset we performed the same procedure for a randomly chosen set ${\mathcal{D}}^{*}$ with size 2000 for the two collections of data. In the upper panel, we calculated for various sizes of ${\mathcal{D}}^{*}$ the difference ${\Delta }_f$ between the rejection percentage obtained for the randomly chosen set (averaged over 10 realizations) and the one obtained for the set of the top edges (red square for simulations and blue circle for COMTRADE), and we found a maximum where the two curves of the lower panel start bending.