Generating maximally disassortative graphs with given degree distribution
Generating maximally disassortative graphs with given degree distribution
复制标题
DOI：
10.1287/stsy.2017.0006
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
P. Hoorn;L. Prokhorenkova;E. Samosvat
中科院分区：
文献类型：
--
作者：
P. Hoorn;L. Prokhorenkova;E. Samosvat
在本文中，我们考虑生成具有指定度分布的图的优化问题，使得通过 Spearman's rho 测量的连接节点的度之间的相关性最小。我们提供了一种算法来解决这个问题，并根据大小偏向的度分布获得这些最大不相配图中的联合度分布的完整表征。结果，我们得到了具有任意给定度分布的图上斯皮尔曼 rho 的下界。我们使用这个下界来表明，对于任何固定的尾部指数，都存在具有该指数的无标度度序列，使得具有此类度序列的所有图的 Spearman's rho 的最小值任意接近于零。这意味着仅指定度分布的尾部行为（如复杂网络分析中经常进行的那样）并不能保证 Spearman rho 的最小值。
In this paper we consider the optimization problem of generating graphs with a prescribed degree distribution, such that the correlation between the degrees of connected nodes, as measured by Spearman's rho, is minimal. We provide an algorithm for solving this problem and obtain a complete characterization of the joint degree distribution in these maximally disassortative graphs, in terms of the size-biased degree distribution. As a result we get a lower bound for Spearman's rho on graphs with an arbitrary given degree distribution. We use this lower bound to show that for any fixed tail exponent, there exist scale-free degree sequences with this exponent such that the minimum value of Spearman's rho for all graphs with such degree sequences is arbitrary close to zero. This implies that specifying only the tail behavior of the degree distribution, as is often done in the analysis of complex networks, gives no guarantees for the minimum value of Spearman's rho.