Безмасштабная сеть с использованием алгоритма льготного вложения

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. Это немного отличается от стандартного графа Барабаси-Альберта, который начинается с подключенной версии, а не с версии без каких-либо ребер.

    # 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

Теперь он будет добавлять каждый узел 1 за раз. Когда он это сделает, он добавит новый узел с ребрами к 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