Ivanko Evgeny, Chernoskutov Mikhail
Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, 620990 Ekaterinburg, Russia.
Institute of Natural Sciences and Mathematics of the Ural Federal University, 620075 Ekaterinburg, Russia.
Entropy (Basel). 2022 Feb 20;24(2):297. doi: 10.3390/e24020297.
We consider the problem of modeling complex systems where little or nothing is known about the structure of the connections between the elements. In particular, when such systems are to be modeled by graphs, it is unclear what vertex degree distributions these graphs should have. We propose that, instead of attempting to guess the appropriate degree distribution for a poorly understood system, one should model the system via a set of sample graphs whose degree distributions cover a representative range of possibilities and account for a variety of possible connection structures. To construct such a representative set of graphs, we propose a new random graph generator, Random Plots, in which we (1) generate a diversified set of vertex degree distributions and (2) target a graph generator at each of the constructed distributions, one-by-one, to obtain the ensemble of graphs. To assess the diversity of the resulting ensembles, we (1) substantialize the vague notion of diversity in a graph ensemble as the diversity of the numeral characteristics of the graphs within this ensemble and (2) compare such formalized diversity for the proposed model with that of three other common models (Erdos-Rényi-Gilbert (ERG), scale-free, and small-world). Computational experiments show that, in most cases, our approach produces more diverse sets of graphs compared with the three other models, including the entropy-maximizing ERG. The corresponding Python code is available at GitHub.
我们考虑对复杂系统进行建模的问题，在这类系统中，对于各元素之间连接结构的了解甚少或几乎一无所知。特别是，当要用图来对这类系统进行建模时，尚不清楚这些图应具有何种顶点度分布。我们建议，对于一个了解甚少的系统，不应试图去猜测合适的度分布，而应通过一组样本图来对该系统进行建模，这些样本图的度分布涵盖了具有代表性的一系列可能性，并考虑了各种可能的连接结构。为了构建这样一组具有代表性的图，我们提出了一种新的随机图生成器——随机图绘制（Random Plots），在其中我们（1）生成一组多样化的顶点度分布，并且（2）针对每个构建好的分布逐一使用一个图生成器，以获得图的集合。为了评估所得集合的多样性，我们（1）将图集合中模糊的多样性概念具体化为该集合中图的数字特征的多样性，并且（2）将所提出模型的这种形式化多样性与其他三种常见模型（厄多斯－雷尼－吉尔伯特（ERG）模型、无标度模型和小世界模型）的多样性进行比较。计算实验表明，在大多数情况下，与包括熵最大化的ERG模型在内的其他三种模型相比，我们的方法生成的图集更加多样。相应的Python代码可在GitHub上获取。
