常見網絡模型——ER随機圖、規則圖、BA、WS小世界

ER随機圖：（沒有重邊和自環的簡單圖）

定義一：具有固定邊數的ER随機圖 G(N,M)

構造算法：

（1）初始化：給定 N 個節點和待添加的邊數 M

（2）随機連邊：

1. 随機選取一對沒有邊相連的不同節點，并在這對節點之間添加一條邊
2. 重複步驟1，直到在 M 對不同節點對之間各添加了一條邊

定義二：具有固定連邊機率的ER随機圖 G(N,p)

構造算法：

（1）初始化：給定 N 個節點以及連邊機率 p∈[0,1]

（2）随機連邊：

1. 選擇一對沒有邊相連的不同節點
2. 生成一個随機數 r ∈(0,1)
3. 如果 r < p，那麼在這對節點之間添加一條邊；否則就不添加邊
4. 重複步驟1、2、3，直到所有節點對都被選擇過一次

不使用已有庫函數，自己編寫模型如下：

import networkx as nx
import numpy as np

'''ER model :generate a ER graph'''

def ERmodel(NodeNum, ER_P):
    Node_num = NodeNum
    N = list(range(Node_num))
    G_ER = nx.Graph()
    G_ER.add_nodes_from(N)
    p = ER_P
    AdjMatrix = np.random.randint(0, 10, (Node_num, Node_num))

    # ER 無權無向
    AdjMatrix[0][0] = 0
    for i in range(1, Node_num):
        AdjMatrix[i][i] = 0
        for j in range(i):
            if i > j and AdjMatrix[i][j] < p:
                G_ER.add_edge(i, j)
                AdjMatrix[i][j] = 1
                AdjMatrix[j][i] = 1
            else:
                AdjMatrix[i][j] = 0
                AdjMatrix[j][i] = 0
           

規則圖之最近鄰耦合網絡：具有周期邊界條件，每個節點與最近鄰 2k 個點連線

import networkx as nx

if __name__ == '__main__':
    NUM1 = 500
    K = 15          #  最近鄰 2K 個點連線
    K1 = K + 1
    g = nx.Graph()
    N = list(range(NUM1))
    g.add_nodes_from(N)   #  增加 NUM1 個點

    for i in range(NUM1):
        for j in range(1, K1):
            K_add = NUM1 - K
            i_add_j = i + j + 1
            if i >= K_add and i_add_j > NUM1:  # 大數标簽節點 加數鄰邊 加邊判斷
                i_add = i + j - NUM1
                g.add_edge(i, i_add)
            else:
                i_add = i + j
                g.add_edge(i, i_add)
           

BA無标度網絡：

考慮網絡的增長特性和優先連接配接（好像更多的人使用輪盤賭算法，以後再加好了）

增長特性：網絡的規模是不斷擴大的

優先連接配接：新的節點更傾向于與那些具有較高連接配接度的 hub 節點連接配接

構造算法：

（1）增長：從一個具有 m0 個節點的連通網絡開始，每次引入一個新的節點并且連到 m 個已存在的節點上，這裡 m≤m0

（2）優先連接配接：一個新節點與一個已經存在的節點 i 相連接配接的機率 P_i 與節點 i 的度 k_i 之間滿足關系：

P_i = k_i / ∑k_j

import networkx as nx
import numpy as np
import random
import math

if __name__ == '__main__':
    m_0 = 4
    m = 2
    t = 496
    NUM = m_0 + t
    g = nx.Graph()
    N = list(range(m_0))
    g.add_nodes_from(N)
    k = []                   #   儲存各節點的度
    k_0 = m-1
    p_k = []                 #   儲存各節點的優先機率
    p_0 = 1/m_0
    k_all = 0
    for i in range(m_0):          #   初始的完全圖    
        p_k.append(p_0)
        k.append(k_0)
        k_all += k_0
        for j in range(i,m_0):
            g.add_edge(i,j)

    for i in range(t):
        m_0_t = m_0 + i               #   t 時刻的節點數
        m_0_1 = m_0 + i - 1         #   t-1 時刻的節點數
        g.add_node(m_0_t)
        # k_all = 0
        # for j in range(m_0_t_1):
        #     k_all += k[j]
        add_edge = 1
        while(add_edge<=m):
            for j in range(m_0_1):       #   按照節點順序比較，人為使得标簽小的節點度偏大
                p_random = random.random()       #   是否應該從機率最大的開始比較
                if p_random <= p_k[j] and add_edge <= m:
                    k_j = k[j]
                    p_k_j = p_k[j]
                    g.add_edge(m_0_t,j)
                    add_edge += 1
                    k[j] = k_j + 1
                    k_all += 2                 #   增加一條邊，度增加 2
                    p_k[j] = (k_j + 1)/k_all

        k.append(2)
        p = 2/k_all
        p_k.append(p)
           

WS小世界模型：

作為從完全規則網絡向完全随機網絡的過渡，在規則網絡中引入少許的随機性

構造算法：

（1）從規則圖開始：給定一個含有 N 個點的環狀最近鄰耦合網絡，其中每個節點都與它左右相鄰的各 K/2 個節點相連，K是偶數；

（2）随機化重連：以機率 p 随機地重新連接配接網絡中原有的每條邊，即把每條邊的一個端點保持不變，另一個端點改取為網絡中随機選擇的一個節點，其中規定不得有重邊和自環

（在上述模型中，p=0 對應于完全規則網絡，p=1 對應于完全随機網絡）

  在具體算法實作時，可以把網絡中所有節點編号為 1, 2, ..., N ;對于每個節點 i，順時針選取與節點 i 相連的 K/2 條邊中的每一條邊，邊的一個端點仍然固定為節點 i， 以機率 p 随機選取網絡中的任一個節點作為該條邊的另一個端點。是以，嚴格來說，即使在 p=1 的情況下，通過這種算法得到的WS小世界模型與相同節點，相同變數的ER随機圖模型還是有差別的：畢竟，在WS小世界中每個節點的度至少是 K/2, 而在ER随機圖中則無此限制

import networkx as nx
import numpy as np
import random

if __name__ == '__main__':
    NUM1 = 500
    NUM2 = NUM1 - 1
    K = 15          #  最近鄰 2K 個點連線
    K1 = K + 1
    p = 0.3
    g = nx.Graph()
    N = list(range(NUM1))
    g.add_nodes_from(N)   #  增加 N 個點

    for i in range(NUM1):
        for j in range(1, K1):
            K_add = NUM1 - K
            i_add_j = i + j + 1
            if i >= K_add and i_add_j > NUM1:  #   大數标簽節點 加數鄰邊 加邊判斷
                i_add = i + j - NUM1
                g.add_edge(i, i_add)
            else:
                i_add = i + j
                g.add_edge(i, i_add)

    #  按照機率 p = 0.3 重連
    for i in range(NUM1):
        for e_del in range(i + 1, i + K1):
            if e_del >= NUM1:     #   找到的節點标簽大于實際中的标簽，标簽更正
                e_del = e_del - NUM1
            P_random = random.randint(0, 9)
            if P_random <= 2:
                g.remove_edge(i, e_del)
                e_add = random.randint(0, NUM2)    #   0 - NUM2 都可能
                while e_add == i or g.has_edge(i, e_add) == True:
                    e_add = random.randint(0, NUM2)
                g.add_edge(i, e_add)