Python:为无标度网络实现逐步修改的 Barabasi-Albert 模型

Question

在 Python 中，我需要创建一个指数网络，它不同于指数随机图。

Exponential Networks were introduced in 2005 by Liu & Tang ，并且源自用于创建无标度网络的 Barabasi-Albert 模型的轻微变化。这种新算法仍然使用增长和优先依附，但采用的方式是:

• 网络从初始节点数 n 增长到最终节点数 N；
• 新节点不连接到连接度最高的节点，而是连接到具有最高平均度的邻域的节点。

所以现在驱动依恋的不是现有节点的度数，而是它们邻域的平均度数。这意味着需要修改生成 Barabasi-Albert 模型的算法，这就是我的目标。

我想编写一段代码，以简单的逐步方式执行此操作，使用嵌套 for 循环来模拟增长和优先依恋。另外，我希望为节点分配特定位置，如下所示:

n=100 #Final number of nodes
ncols = 10 #Number of columns of a 10x10 grid
pos = {i : (i // ncols, (n-i-1) % ncols) for i in G.nodes()} #G=graph

我的问题:我可以通过访问 nx.barabasi_albert_graph() 的源代码来解决这个问题函数，但我不明白哪个是增长阶段，哪个是优先依附阶段，以及计算每个节点的度数的地方。 如果有人能在这里为我指明正确的方向，我会很高兴。

---

nx.barabasi_albert_graph() 函数的源代码:

def barabasi_albert_graph(n, m, seed=None):

    if m < 1 or  m >=n:
        raise nx.NetworkXError(\
              "Barabási-Albert network must have m>=1 and m<n, m=%d,n=%d"%(m,n))
    if seed is not None:
        random.seed(seed)

    # Add m initial nodes (m0 in barabasi-speak)
    G=empty_graph(m)
    G.name="barabasi_albert_graph(%s,%s)"%(n,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

我已经实现了一个 animation for Barabasi-Albert graph growth并且我认为该实现很容易根据优先附件标准和节点位置进行调整。

节点位置

You will need to look into animate_BA function for nodes position (as I have it randomly chosen) at lines 39 (for starting nodes) and 69 (for newly added node)

成长期

As for Growth phase, this is implemented in a separate function choose_neighbors that is called for the insertion of a new node into the graph. My implementation chooses a node to connect to with probability: (deg(i)+1)/Sum(deg(i)+1) where i is a node in the graph and deg(i) is the degree of that node and Sum(deg(i)+1) is the summation of degrees of all nodes in the graph + 1. This is achieved by creating a list of floats from 0 to 1 specifying the probability for each node to be chosen based on its degree.You can adjust that to the average degree of neighbors instead. So you will have to create this list but differently, since this function calls select_neighbors function to choose neighbors randomly based on the defined probabilities.

其他函数主要是和动画相关的，可以不用细看。该代码已记录在案，您可以在那里找到进一步的解释。