330
个编辑
更改
跳到导航
跳到搜索
第38行：
第38行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→算法
#构建一个正则环点阵。该图有<math>N</math>个节点，每个节点和<math>K</math>个相邻的节点相连，其中每一侧有<math>K/2</math>个。即是，若每个节点用<math>n_{0},...,n_{N-1}</math>标示，当且仅当<math>0< \left | i-j \right |\mod(N-1-\frac{K}{2})\leq \frac{K}{2}</math>时，存在边<math>(n_{i},n_{j})</math>。
#构建一个正则环点阵。该图有<math>N</math>个节点，每个节点和<math>K</math>个相邻的节点相连，其中每一侧有<math>K/2</math>个。即是，若每个节点用<math>n_{0},...,n_{N-1}</math>标示，当且仅当<math>0< \left | i-j \right |\mod(N-1-\frac{K}{2})\leq \frac{K}{2}</math>时，存在边<math>(n_{i},n_{j})</math>。
#对于每个节点<math>n_{i}=n_{0},...,n_{N-1}</math>，选出其与最右侧第<math>K/2</math>相邻节点之间的边，即满足<math>n_{i} < n_{j} \leq n_{i} + K/2</math>的所有边 <math>(n_{i},n_{j}\mod N)</math> ，以概率<math>\beta</math>将其重新连接。重新连接的过程是把边 <math>(n_{i},n_{j}\mod N)</math> 替换为边 <math>(n_{i},n_{k})</math> ，其中<math>k</math>以一致的随机性从所有可能的节点选出，并且避免出现自回路<math>(k\neq i)</math>和重复连接（边 <math>(n_{i},n_{{k}'})</math> ，其中<math>{k}'=k</math>，在该算法中不会出现）的情况。
#对于每个节点<math>n_{i}=n_{0},...,n_{N-1}</math>，选出其与最右侧第<math>K/2</math>相邻节点之间的边，即满足<math>n_{i} < n_{j} \leq n_{i} + K/2</math>的所有边 <math>(n_{i},n_{j}\mod N)</math> ，以概率<math>\beta</math>将其重新连接。重新连接的过程是把边 <math>(n_{i},n_{j}\mod N)</math> 替换为边 <math>(n_{i},n_{k})</math> ，其中<math>k</math>以一致的随机性从所有可能的节点选出，并且避免出现自回路<math>(k\neq i)</math>和重复连接（边 <math>(n_{i},n_{{k}'})</math> ，其中<math>{k}'=k</math>，在该算法中不会出现）的情况。
==构建小世界网络==
构建小世界网络的主要机制是[https://en.wikipedia.org/wiki/Watts_and_Strogatz_Model Watts-Strogatz机制]。
小世界网络也可引入延时<ref name="a18">#X. S. Yang, Fractals in small-world networks with time-delay, Chaos, Solitons & Fractals, vol. 13, 215–219 (2002)
</ref>，这不仅会产生分形，而且在特定条件下，还会形成混沌<ref name="a19">#X. S. Yang, Chaos in small-world networks, Phys. Rev. E 63, 046206 (2001)
</ref>，或者在动态网络中转变为混沌<ref name="a20">#W. Yuan, X. S. Luo, P. Jiang, B. Wang, J. Fang, Transition to chaos in small-world dynamical network
</ref>。
构造[https://en.wikipedia.org/wiki/Degree_diameter 度直径图]（Degree–diameter graph）的方法是：网络中每个顶点的邻居数量是有界的，而网络中从任意给定顶点到其他顶点（网络[https://en.wikipedia.org/wiki/Distance_(graph_theory) 直径]）是最小的。构建这样的小世界网络，其实是为寻找临近[https://en.wikipedia.org/wiki/Moore_graph 摩尔边界]的图的秩，而做出的一部分努力。
Barmpoutis等人给出的从零开始构建小世界网络的另外一种方法<ref name="a21">#[https://en.wikipedia.org/wiki/D.Barmpoutis_and_R.M._Murray D.Barmpoutis and R.M. Murray] (2010). "Networks with the Smallest Average Distance and the Largest Average Clustering". arXiv:1007.4031 Freely accessible [q-bio.MN].</ref>，构建了一种平均距离极小且平均集聚度极高的网络。他们提到了一种复杂度恒定的快速算法，以及不同生成图鲁棒性的度量。根据每个网络的应用，可以从一个这样的“超小世界”网络开始，然后重新连接一些边，或者使用几个这样的小网络作为子图，构筑一个更大的图。
通过[https://en.wikipedia.org/wiki/Dual-phase_evolution 双相演化](dual-phase evolution)过程，小世界属性可以在社交网络和其他现实世界系统中自然产生。在顶点之间的连接增长受到时间或空间的制约时，小世界网络尤其常见。该机制通常涉及相位之间的周期性变换，其中，在“全局”阶段——连接建立，而在“本地”阶段——连接被移除。
参考：[https://en.wikipedia.org/wiki/Diffusion-limited_aggregation 扩散限制凝聚]，[https://en.wikipedia.org/wiki/Pattern_formation 模式构成]。
==构建小世界网络代码实现==
=== 使用networkx生成小世界网络 ===
<syntaxhighlight lang="python">
import networkx as nx
import matplotlib.pyplot as plt
# WS network
# 生成20个节点的小世界网络
# 每个节点有四个邻居
# 每条连边以0.3的概率随机重置链接
WS = nx.random_graphs.watts_strogatz_graph(20, 4, 0.3)
pos = nx.circular_layout(WS)
nx.draw(WS, pos, with_labels = False, node_size = 30)
plt.show()
</syntaxhighlight>
此时得到的图片是下图所示:<br />
[[File:Networksx包生成的小世界网络.png | 400px]]
=== 使用原生方法x生成小世界网络 ===
<syntaxhighlight lang="python">
G = nx.Graph()
node_num = 20
neighbour_num = 4
probility = 0.3
# 节点与邻居相连
for i in range(node_num):
from_node = i
for j in range(neighbour_num):
to_node = (i+j) % node_num - neighbour_num / 2
if to_node >= 0:
to_node += 1
G.add_edge(from_node,to_node)
# 连边随机重连
edges = copy.deepcopy(G.edges())
for edge in edges:
if random.random() < probility:
G.remove_edge(edge[0],edge[1])
ran_edge = np.random.randint(node_num,size=2).tolist()
G.add_edge(ran_edge[0],ran_edge[1])
# 绘图
pos = nx.circular_layout(G)
nx.draw(G, pos, with_labels = False, node_size = 30)
plt.show()
</syntaxhighlight>
此时得到的图片如下图所示：
<br />
[[File:原声方法生成的小世界网络.png |400px]]
==局限性==
==局限性==