NetworkX提供了4種常見網(wǎng)絡的建模方法，分別是：規(guī)則圖，ER隨機圖，WS小世界網(wǎng)絡和BA無標度網(wǎng)絡。本文首先介紹在NetworkX生成這些網(wǎng)絡模型的方法，然后以BA無標度網(wǎng)絡的建模為例，分析利用NetworkX進行復雜網(wǎng)絡演化模型設計的基本思路，以便將來開發(fā)出我們自己的模型。同時這篇文章里還涉及到一點復雜網(wǎng)絡可視化的方法（后邊有時間會另文介紹網(wǎng)絡可視化的方法）。

一、規(guī)則圖

規(guī)則圖差不多是最沒有復雜性的一類圖了，在NetworkX中，用random_graphs.random_regular_graph(d, n)方法可以生成一個含有n個節(jié)點，每個節(jié)點有d個鄰居節(jié)點的規(guī)則圖。下面是一段示例代碼，生成了包含20個節(jié)點、每個節(jié)點有3個鄰居的規(guī)則圖：

import networkx as nx
import matplotlib.pyplot as plt
RG = nx.random_graphs.random_regular_graph(3,20)  #生成包含20個節(jié)點、每個節(jié)點有3個鄰居的規(guī)則圖RG
pos = nx.spectral_layout(RG)          #定義一個布局，此處采用了spectral布局方式，后變還會介紹其它布局方式，注意圖形上的區(qū)別
nx.draw(RG,pos,with_labels=False,node_size = 30)  #繪制規(guī)則圖的圖形，with_labels決定節(jié)點是非帶標簽（編號），node_size是節(jié)點的直徑
plt.show()  #顯示圖形

運行結果如下：

圖1   NetworkX生成的規(guī)則圖

二、ER隨機圖

ER隨機圖是早期研究得比較多的一類“復雜”網(wǎng)絡，這個模型的基本思想是以概率p連接N個節(jié)點中的每一對節(jié)點。在NetworkX中，可以用random_graphs.erdos_renyi_graph(n,p)方法生成一個含有n個節(jié)點、以概率p連接的ER隨機圖：

import networkx as nx
import matplotlib.pyplot as plt
ER = nx.random_graphs.erdos_renyi_graph(20,0.2)  #生成包含20個節(jié)點、以概率0.2連接的隨機圖
pos = nx.shell_layout(ER)          #定義一個布局，此處采用了shell布局方式
nx.draw(ER,pos,with_labels=False,node_size = 30)
plt.show()

運行結果如下：

圖2   NetworkX生成的隨機圖

三、WS小世界網(wǎng)絡

在NetworkX中，可以用random_graphs.watts_strogatz_graph(n, k, p)方法生成一個含有n個節(jié)點、每個節(jié)點有k個鄰居、以概率p隨機化重連邊的WS小世界網(wǎng)絡，下面是一個例子：

import networkx as nx
import matplotlib.pyplot as plt
WS = nx.random_graphs.watts_strogatz_graph(20,4,0.3)  #生成包含20個節(jié)點、每個節(jié)點4個近鄰、隨機化重連概率為0.3的小世界網(wǎng)絡
pos = nx.circular_layout(WS)          #定義一個布局，此處采用了circular布局方式
nx.draw(WS,pos,with_labels=False,node_size = 30)  #繪制圖形
plt.show()

運行結果如下：

圖3   NetworkX生成的WS小世界網(wǎng)絡

四、BA無標度網(wǎng)絡

在NetworkX中，可以用random_graphs.barabasi_albert_graph(n, m)方法生成一個含有n個節(jié)點、每次加入m條邊的BA無標度網(wǎng)絡，下面是一個例子：

import networkx as nx
import matplotlib.pyplot as plt
BA= nx.random_graphs.barabasi_albert_graph(20,1)  #生成n=20、m=1的BA無標度網(wǎng)絡
pos = nx.spring_layout(BA)          #定義一個布局，此處采用了spring布局方式
nx.draw(BA,pos,with_labels=False,node_size = 30)  #繪制圖形
plt.show()

運行結果如下：

圖4   NetworkX生成的BA無標度網(wǎng)絡

五、對BA模型實現(xiàn)代碼的分析

前面我們介紹了NetworkX提供的4種網(wǎng)絡演化模型的應用方法，但僅停留在使用已有的模型是不夠的，實際工作中我們可能會自己開發(fā)一些網(wǎng)絡演化模型。利用NetworkX提供的數(shù)據(jù)結構，我們可以比較方便的完成這一工作。下面以NetworkX中BA模型的實現(xiàn)代碼為例，分析用NetworkX開發(fā)網(wǎng)絡演化模型的一般思路。NetworkX中關于網(wǎng)絡建模的代碼在random_graphs.py這個文件中，可以用記事本打開它。為了敘述簡便起見，我刪掉了原始代碼中的一些錯誤處理與初始條件定義的語句，紅色部分是翻譯后的注釋。

#定義一個方法，它有兩個參數(shù)：n - 網(wǎng)絡節(jié)點數(shù)量；m - 每步演化加入的邊數(shù)量
def barabasi_albert_graph(n, m):
    # 生成一個包含m個節(jié)點的空圖 (即BA模型中t=0時的m0個節(jié)點)
    G=empty_graph(m) 
    # 定義新加入邊要連接的m個目標節(jié)點
    targets=range(m) 
    # 將現(xiàn)有節(jié)點按正比于其度的次數(shù)加入到一個數(shù)組中，初始化時的m個節(jié)點度均為0，所以數(shù)組為空
    repeated_nodes=[]    
    # 添加其余的 n-m 個節(jié)點，第一個節(jié)點編號為m（Python的數(shù)組編號從0開始）
    source=m
    # 循環(huán)添加節(jié)點
    while source<n:
        # 從源節(jié)點連接m條邊到選定的m個節(jié)點targets上（注意targets是上一步生成的）
        G.add_edges_from(zip([source]*m,targets))
        # 對于每個被選擇的節(jié)點，將它們加入到repeated_nodes數(shù)組中（它們的度增加了1）
        repeated_nodes.extend(targets)
        # 將源點m次加入到repeated_nodes數(shù)組中（它的度增加了m）
        repeated_nodes.extend([source]*m)
        # 從現(xiàn)有節(jié)點中選取m個節(jié)點 ，按正比于度的概率（即度優(yōu)先連接）
        targets=set()
        while len(targets)<m:
            #按正比于度的概率隨機選擇一個節(jié)點，見注釋1
            x=random.choice(repeated_nodes)
            #將其添加到目標節(jié)點數(shù)組targets中
            targets.add(x)       
        #挑選下一個源點，轉到循環(huán)開始，直到達到給定的節(jié)點數(shù)n
        source += 1
    #返回所得的圖G
    return G

注釋1：此步是關鍵，random.choice方法是從一個數(shù)組中隨機地挑選一個元素。由于repeated_nodes數(shù)組中的節(jié)點出現(xiàn)次數(shù)是正比于節(jié)點度的，所以這樣處理可以保證按度大小的概率選出節(jié)點，即實現(xiàn)了度優(yōu)先連接。如果是按正比于節(jié)點適應性等非整數(shù)值優(yōu)先連接，可以參考我的另一篇博文《根據(jù)值的大小隨機取數(shù)組元素的方法》。

六、小結

NetworkX的優(yōu)勢之一就是開源，這也是所有Python庫的優(yōu)勢（Python是腳本語言，它沒有辦法隱藏源代碼）。NetworkX的源代碼結構清晰，風格簡練，注釋詳盡，是學習、研究復雜網(wǎng)絡不錯的參考資料。當然在這方面我也是初學者，更多的功能還需要在實際應用中不斷去發(fā)掘和領會…………