使用优先连接算法的无标度网络

Question

我很难理解这段代码是做什么的。请有人一步一步地看一下代码，并解释一下它是如何工作的，它是做什么的？

def scale_free(n,m):
    if m < 1 or  m >=n: 
        raise nx.NetworkXError("Preferential attactment algorithm must have m >= 1"
                               " and m < n, m = %d, n = %d" % (m, n)) 
    # Add m initial nodes (m0 in barabasi-speak)
    G=nx.empty_graph(m)

    # Target nodes for new edges
    targets=list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes=[]
    # Start adding the other n-m nodes. The first node is m.
    source=m
    while source<n:
        # Add edges to m nodes from the source.
        G.add_edges_from(zip([source]*m,targets))
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend([source]*m)
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachement)
        targets = _random_subset(repeated_nodes,m)
        source += 1
    return G

Answer 1

因此，第一部分确保m至少为1且为n>m。

def scale_free(n,m):
    if m < 1 or  m >=n: 
        raise nx.NetworkXError("Preferential attactment algorithm must have m >= 1"
                               " and m < n, m = %d, n = %d" % (m, n)) 

然后，它创建一个没有边和第一个m节点0，1，...，m-1的图。这看起来与标准的barabasi-albert图略有不同，后者从连接的版本开始，而不是从没有任何边的版本开始。

    # Add m initial nodes (m0 in barabasi-speak)
    G=nx.empty_graph(m)

现在，它将开始一次添加1个新节点，并基于各种规则将它们连接到现有节点。它首先创建一组“目标”，其中包含无边图中的所有节点。

    # Target nodes for new edges
    targets=list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes=[]
    # Start adding the other n-m nodes. The first node is m.
    source=m

现在，它将一次添加一个节点。当它这样做时，它会将带有边的新节点添加到以前现有节点的m中。这些m以前的节点已经存储在一个名为targets的列表中。

    while source<n:

在这里它创建了这些边

        # Add edges to m nodes from the source.
        G.add_edges_from(zip([source]*m,targets))

现在，它将决定在添加下一个节点时谁将获得这些边。它应该以与它们的程度成正比的概率来选择它们，方法是通过一个列表repeated_nodes，它让每个节点在每条边出现一次。然后，它从其中随机选择一组m节点作为新目标。根据_random_subset是如何定义的，它可能会也可能不会在同一步骤中多次选择同一节点作为目标。

        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend([source]*m)
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachement)
        targets = _random_subset(repeated_nodes,m)
        source += 1
    return G