学习小记

double_edge_swap(G)

这是一个连边置乱的函数,输入的G必须为无向图,且图节点不小于4

    # Instead of choosing uniformly at random from a generated edge list,
    # this algorithm chooses nonuniformly from the set of nodes with
    # probability weighted by degree.

【问题1】该算法选择从节点集中以度的加权概率进行非均匀选择,而非从边列表中均匀随机选取。这么做有什么好处?

函数解读:

  • keys,degrees=zip(*G.degree().items()) #迭代节点度

u--v     得到的结果为:[('y', 'x', 'u', 'v'), (1, 2, 2, 1)]
|
x--y 

  • cdf=nx.utils.cumulative_distribution(degrees) # 计算度的累积分布

结果为 cdf = [0.0, 0.16666666666666666, 0.5, 0.8333333333333333, 0.9999999999999999]

简单解释一下原因,累积分布 所以第一个是0,第二个是(0+1)/(1+2+2+1),第三个是(0+1+2)/(1+2+2+1)...

  • (ui,xi)=nx.utils.discrete_sequence(2,cdistribution=cdf)  #返回长度为2的采样序列
  • u=keys[ui]
    x=keys[xi]

若ui=0,xi=1,则u='y',x='x'即从网络G中选两点

connected_double_edge_swap(G, nswap=1, _window_threshold=3)

这是保持连通性的双边置乱

_window_threshold?这是干嘛用的?

【问题1】分别用上述两种方式执行置乱操作,发现本算法所采用的方式确实效率高出好多

原文地址:https://www.cnblogs.com/sxbjdl/p/4722176.html