小世界網路模型

一、概述

小世界網路模型是指某些網路具有局部集聚性和全局短距離特徵的網路結構模型。

最早由Duncan J. Watts和Steven H. Strogatz於1998年提出，他們將小世界模型定義為介於完全隨機和完全規則的網路模型。該模型呈現了群聚和短路徑的特點。

二、特點

小世界網路模型具有以下特點：

1、集聚性：局部節點之間相對密集地連接。

2、短路徑：全局通過少量的中間節點就能夠互相連通。

3、隨機性：節點之間連接的隨機性，使得網路比起完全規則的網路更具有魯棒性。

三、生成演算法

Watts和Strogatz用以下的生成演算法構造小世界模型：

1. 構建一個普通的、具有n個節點、每個節點有k個近鄰的Lattice網路
2. 依次考慮網路中每個節點，並使用以下的方式重新連接網路中該節點的某些近鄰：
   1）對每個節點i和每個k/2的近鄰（按逆時針方向，共k個節點），以概率p重新連接，
   2）如果存在重邊則不進行。
   3）它增加了整個網路的隨機性，而該網路構成保持高度集聚的特性。

四、Python實現代碼示例

以下是使用Python實現小世界網路模型的代碼示例：

import networkx as nx
import random

def watts_strogatz_graph(n, k, p):
    G = nx.generators.random_graphs.random_regular_graph(k, n)
    for i in range(n):
        nodes = [j for j in range(i - k // 2, i + k // 2 + 1)]
        nodes.remove(i)
        for j in nodes:
            if j = n:
                continue
            if random.random() < p:
                G.remove_edge(i, j)
                x = random.randint(0, n - 1)
                while G.has_edge(i, x):
                    x = random.randint(0, n - 1)
                G.add_edge(i, x)
    return G 

五、應用

小世界網路模型具有廣泛的應用領域，在社交網路、生物信息學、通信網路等方面常用於研究節點之間的連接方式和性質。

例如，在社交網路中，人們往往會選擇一些朋友進行交流，這就構成了局部密集連接。但是，社交網路之間幾乎任何人之間都能通過短路程互相連通，這就構成了全局短距離特徵。此時，小世界網路模型就是一種較好的描述方法。

六、總結

小世界網路模型是一種具有局部集聚性和全局短距離特徵的網路結構模型。它的主要特點包括集聚性、短路徑和隨機性。它的生成演算法是通過構建一個普通的節點k近鄰網路，再隨機重連部分邊構成的。小世界網路模型的應用範圍十分廣泛，在社交網路、生物信息學、通信網路中都能發揮重要作用。