实验环境

我用的是Anaconda 自带的Spyder编辑器，python3.8


此算法在上一篇算法复杂网络——随机网络ER的构造C++实现及测试的基础上用python重写了，在编写过程中发现python对数组的初始化非常方便，仅用np.zeros（）函数就可以生成，而C++要用双层for循环才可以。在这里我默认系统资源非常充足，就未对内存申请失败进行判断，实际上在测试时节点数1000就报错内存不足。但是算法的整体框架都是对的，用了一个晚上写好的，早上来实验室修改了几处小错误。



 友情提醒：如果import包的内容报错，请自行百度下载相应的包头，除此之外正常运行不会出错的。



代码使用方法：打开Python编辑器，复制导入，测试成功的话可以看到输出的ER网络以及代码所在位置写入成功的两个文件。 


实验代码

代码流程部分在上一篇中已经介绍的比较细致了，这里不再赘述。 不同的是将C++中write2File_degreedistribut()函数直接写入clalulateDegreeDistribution()函数中（本来是分开写的，但在传形参的时候出现了数组下标越界的问题，没有解决就直接用实参写了），另增加了showGraph()函数——将ER网络邻接矩阵转化成图的形式输出。

实验完整代码如下，经多次测试能正确输出结果。

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 17 14:35:03 2019

"""
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import random
import time

print('请输入ER网络的顶点个数：')
NETWORK_SIZE=int(input())
print('请输入连边概率：')
PROBABILITY_OF_EAGE=float(input())
adjacentMatrix=np.zeros((NETWORK_SIZE,NETWORK_SIZE),dtype=int)#初始化邻接矩阵
random.seed(time.time())#'random.random()#生成[0,1)之间的随机数

#生成ER网络
def generateRandomNetwork():
    count=0
    probability=0.0
    for i in range(NETWORK_SIZE):
        for j in range(i+1,NETWORK_SIZE):
            probability=random.random()
            if probability<PROBABILITY_OF_EAGE:
                count =count+1
                adjacentMatrix[i][j]=adjacentMatrix[j][i]=1
    print('您所构造的ER网络边数为：'+str(count))

#用于绘制ER图
def showGraph():
    G=nx.Graph()
    for i in range(len(adjacentMatrix)):
        for j in range(len(adjacentMatrix)):
            if adjacentMatrix[i][j]==1:#如果不加这句将生成完全图，ER网络的邻接矩阵将不其作用
                G.add_edge(i,j)
    nx.draw(G)
    plt.show()
 
#将ER网络写入文件中
def writeRandomNetworkToFile():
    ARRS=[]
    f=open('randomNetwork01.txt','w+')
    for i in range(NETWORK_SIZE):
        t=adjacentMatrix[i]
        ARRS.append(t)
        for j in range(NETWORK_SIZE):
            s=str(t[j])
            f.write(s)
            f.write(' ')
        f.write('\n')
    f.close()
 
#计算度分布并将其存入文件中
def calculateDegreeDistribution():
    averageDegree=0.0
    identify=0.0
    statistic=np.zeros((NETWORK_SIZE),dtype=float)#statistic将用于存放度分布的数组，数组下标为度的大小，对应数组内容为该度的概率
    degree=np.zeros((NETWORK_SIZE),dtype=int)#degree用于存放每个节点的度
    for i in range(NETWORK_SIZE):
        for j in range(NETWORK_SIZE):
            degree[i]=degree[i]+adjacentMatrix[i][j]
    for i in range(NETWORK_SIZE):
        averageDegree+=degree[i]
    print('平均度为'+str(averageDegree/NETWORK_SIZE))#计算平均度
    for i in range(NETWORK_SIZE):
        statistic[degree[i]]=statistic[degree[i]]+1
    for i in range(NETWORK_SIZE):
        statistic[i]=statistic[i]/NETWORK_SIZE
        identify=identify+statistic[i]
    identify=int(identify)    
    print('如果output为1则该算法正确\toutput='+str(identify))#用于测试算法是否正确
    f=open('degree01.txt','w+')#将度分布写入文件名为degree01文件中，若磁盘中无此文件将自动新建
    for i in range(NETWORK_SIZE):

        f.write(str(i))
        f.write(' ')
        s=str(statistic[i])#注意写入操作要求是字符串格式，因此用str进行格式转换
        f.write(str(s))    #写入的每一行由两部分组成，一个元素为度的下标，第二个元素为度的概率  
        f.write('\n')#每个节点的度及概率写入完成将进行换行，输入下一个节点的度及度分布
    f.close()
    
 #主程序开始
start=time.perf_counter()     #用以程序计时开始位置      
generateRandomNetwork()      #生成ER随机网络
writeRandomNetworkToFile()   #将随机网络写入randomNetwork01.txt文件中
calculateDegreeDistribution() #计算此ER随机网络的度分布并将结果写入文件degreee01.txt文件中
finish=time.perf_counter()#程序计时结束
duration=finish-start
print('生成这个ER网络需要的时间为：'+str(duration)+'s')
print('您所构造的ER网络如下：')
showGraph()



实验结果

1. 测试数据：输入顶点数10，连边概率0.08



  2.测试数据：输入顶点数100，连边概率0.08



 3.测试数据：输入顶点数1000，连边概率0.08 



查看邻接矩阵以及度分布文件

以节点个数20，连边概率0.4为例：



可以查看对应的randomNetwork01文件——存放ER 无向图的邻接矩阵

 

 可以查看度分布文件degree01.txt——第一列表示度，第二列表示度的概率分布。




同志们，你们可以正常运行吗，有问题的及时在评论处回复我哦。 


回复评论：1.要直接输出节点及度分布，添加以下几行，注意statistic的作用域是在calculateDegreeDistribution()函数体内，在函数体外是输不出结果的，要么把statistic的定义写在函数外，要么在函数体内部输出。这里测试输出前二十个，可将20改为NETWORK_SIZE输出全部的。

#计算度分布并将其存入文件中
def calculateDegreeDistribution():
    averageDegree=0.0
    identify=0.0
    statistic=np.zeros((NETWORK_SIZE),dtype=float)#statistic将用于存放度分布的数组，数组下标为度的大小，对应数组内容为该度的概率
    degree=np.zeros((NETWORK_SIZE),dtype=int)#degree用于存放每个节点的度
    for i in range(NETWORK_SIZE):
        for j in range(NETWORK_SIZE):
            degree[i]=degree[i]+adjacentMatrix[i][j]
    for i in range(NETWORK_SIZE):
        averageDegree+=degree[i]
    print('平均度为'+str(averageDegree/NETWORK_SIZE))#计算平均度
    for i in range(NETWORK_SIZE):
        statistic[degree[i]]=statistic[degree[i]]+1
    for i in range(NETWORK_SIZE):
        statistic[i]=statistic[i]/NETWORK_SIZE
        identify=identify+statistic[i]
    identify=int(identify)    
    print('如果output为1则该算法正确\toutput='+str(identify))#用于测试算法是否正确
    #添加以下部分
    print('打印前二十个节点的度分布')
    for i in range(20):
        print('节点'+str(i)+'度为'+str(statistic[i]))
    #添加结束    
    f=open('degree01.txt','w+')#将度分布写入文件名为degree01文件中，若磁盘中无此文件将自动新建
    for i in range(NETWORK_SIZE):
 
        f.write(str(i))
        f.write(' ')
        s=str(statistic[i])#注意写入操作要求是字符串格式，因此用str进行格式转换
        f.write(str(s))    #写入的每一行由两部分组成，一个元素为度的下标，第二个元素为度的概率  
        f.write('\n')#每个节点的度及概率写入完成将进行换行，输入下一个节点的度及度分布
    f.close()


 输出结果：



2.在测试10000时

正常运行

复杂网络定义

：

复杂网络概念最开始的时候是相对于规则网络和随机网络提出来的，即介于规则网络和随机网络之间的网络都可以称之为复杂网络。—狭义的复杂网络

从广义上说，任何网络都可以称之为复杂网络，即使是规则网络和随机网络，也是复杂网络的特例。


复杂网络研究意义

：

复杂网络理论可以应用于保护许多现实系统的正常运行。也就是开展复杂网络稳定性研究，对于一些技术网络的设计和基础设施网络的保护同样具有重要的意义，也可以有效地防止黑客侵入互联网，并组织病毒在万维网上传播蔓延。

在医疗方面直接针对集散节点（即那些与很多人具有连接关系的人）采取措施接种疫苗，可以达到和好效果。

在经济管理领域，利用复杂网络了解公司，产业和经济之间的连接方式，有助于监控和预防大规模的经济衰退。


复杂网络基本参数

：


平均最短路径长度：任意两节点之间的距离的平均值。


聚集系数： 一般与平均最短路径一起提出，因为它们俩是“小世界”效应的两个重要性质。用来刻画两个朋友之间互为朋友的概率。


度分布： 网络中一个随机选择的节点度为k的概率

有向图分为出度和入度

无向网络度分布


介数：在研究之初，没有介数的概念，在网络节点和边的重要性上的研究和对于网络中社区的划分的研究，提出介数概念。**节点的介数被定义为网络中所有的最短路径中经过该点的数目的比例。**介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。


复杂网络的经典模型

：


规则网络模型：
全局耦合网络：任意两个节点都有边直接相连

最近邻耦合网络 ：每个节点只和它周围的邻居相连

星型耦合网络：只有一个中心节点，其余的N-1个节点与这个中心节点相连接。

随机模型： 典型例子ER随机模型 研究的课题为：当概率p为多大时，随机模型就会产生一些特殊的性质。
“小世界”模型： “小世界”模型起源于，首先建立一个低维的网络结构，然后增加或移动一些边，以生成较低密度的“捷径”，他们将网络中较远的部分连接起来。WS模型构造出来的网络具有：较高的平均聚类系数和较低的最短路径长度
“无尺度”网络：又可以称之为网络生长模型，反映了复杂网络的另一特性，网络的节点度分布函数具有幂律形式。在“无尺度”模型中，节点和边按照一定的方式被加入到网络中，网络以某种方式进行生长。

**

小结

较小的平均最短路径长度以及较大的聚集系数是复杂网络“小世界”特性的体现，它集中反映了现实网络环境下高集聚性和短连接距离的特点；度分布服从幂律分布体现了复杂网络的“无尺度”特性，即网络的平均度不能反应网络中度的大致分布情况，现实中的“长尾”分布和“二八定律”反映的就是这一特性；介数在一定程度上反映了网络中单个节点和边的重要性。


作者：DN-Software Network

来源：CSDN

原文：https://blog.csdn.net/daining424/article/details/83721054

版权声明：本文为博主原创文章，转载请附上博文链接！

1. 复杂网络定义
：

复杂网络概念最开始的时候是相对于规则网络和随机网络提出来的，即介于规则网络和随机网络之间的网络都可以称之为复杂网络。—狭义的复杂网络

从广义上说，任何网络都可以称之为复杂网络，即使是规则网络和随机网络，也是复杂网络的特例。
2. 复杂网络研究意义
：

复杂网络理论可以应用于保护许多现实系统的正常运行。也就是开展复杂网络稳定性研究，对于一些技术网络的设计和基础设施网络的保护同样具有重要的意义，也可以有效地防止黑客侵入互联网，并组织病毒在万维网上传播蔓延。

在医疗方面直接针对集散节点（即那些与很多人具有连接关系的人）采取措施接种疫苗，可以达到和好效果。

在经济管理领域，利用复杂网络了解公司，产业和经济之间的连接方式，有助于监控和预防大规模的经济衰退。
3. 复杂网络基本参数
：

1. 平均最短路径长度：任意两节点之间的距离的平均值。

2. 聚集系数： 一般与平均最短路径一起提出，因为它们俩是“小世界”效应的两个重要性质。用来刻画两个朋友之间互为朋友的概率。

3. 度分布： 网络中一个随机选择的节点度为k的概率

有向图分为出度和入度

无向网络度分布

4. 介数：在研究之初，没有介数的概念，在网络节点和边的重要性上的研究和对于网络中社区的划分的研究，提出介数概念。**节点的介数被定义为网络中所有的最短路径中经过该点的数目的比例。**介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。
4. 复杂网络的经典模型
：


规则网络模型：

全局耦合网络：任意两个节点都有边直接相连
最近邻耦合网络 ：每个节点只和它周围的邻居相连
星型耦合网络：只有一个中心节点，其余的N-1个节点与这个中心节点相连接。



随机模型： 典型例子ER随机模型 研究的课题为：当概率p为多大时，随机模型就会产生一些特殊的性质。


“小世界”模型： “小世界”模型起源于，首先建立一个低维的网络结构，然后增加或移动一些边，以生成较低密度的“捷径”，他们将网络中较远的部分连接起来。WS模型构造出来的网络具有：较高的平均聚类系数和较低的最短路径长度


“无尺度”网络：又可以称之为网络生长模型，反映了复杂网络的另一特性，网络的节点度分布函数具有幂律形式。在“无尺度”模型中，节点和边按照一定的方式被加入到网络中，网络以某种方式进行生长。

**


5. 小结

较小的平均最短路径长度以及较大的聚集系数是复杂网络“小世界”特性的体现，它集中反映了现实网络环境下高集聚性和短连接距离的特点；度分布服从幂律分布体现了复杂网络的“无尺度”特性，即网络的平均度不能反应网络中度的大致分布情况，现实中的“长尾”分布和“二八定律”反映的就是这一特性；介数在一定程度上反映了网络中单个节点和边的重要性。

你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。
新的改变
我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：

全新的界面设计 ，将会带来全新的写作体验；
在创作中心设置你喜爱的代码高亮样式，Markdown 将代码片显示选择的高亮样式 进行展示；
增加了 图片拖拽 功能，你可以将本地的图片直接拖拽到编辑区域直接展示；
全新的 KaTeX数学公式 语法；
增加了支持甘特图的mermaid语法 功能；
增加了 多屏幕编辑 Markdown文章功能；
增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能，功能按钮位于编辑区域与预览区域中间；
增加了 检查列表 功能。

功能快捷键
撤销：Ctrl/Command + Z

重做：Ctrl/Command + Y

加粗：Ctrl/Command + B

斜体：Ctrl/Command + I

标题：Ctrl/Command + Shift + H

无序列表：Ctrl/Command + Shift + U

有序列表：Ctrl/Command + Shift + O

检查列表：Ctrl/Command + Shift + C

插入代码：Ctrl/Command + Shift + K

插入链接：Ctrl/Command + Shift + L

插入图片：Ctrl/Command + Shift + G
合理的创建标题，有助于目录的生成
直接输入1次#，并按下space后，将生成1级标题。

输入2次#，并按下space后，将生成2级标题。

以此类推，我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。
如何改变文本的样式
强调文本 强调文本
加粗文本 加粗文本
标记文本
删除文本

引用文本

H2O is是液体。
210 运算结果是 1024.
插入链接与图片
链接: link.
图片: 
带尺寸的图片: 
当然，我们为了让用户更加便捷，我们增加了图片拖拽功能。
如何插入一段漂亮的代码片
去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.
// An highlighted block
var foo = 'bar';

生成一个适合你的列表

项目

项目

项目






项目1
项目2
项目3


 计划任务
 完成任务

创建一个表格
一个简单的表格是这么创建的：




项目
Value




电脑
$1600


手机
$12


导管
$1


设定内容居中、居左、居右
使用:---------:居中

使用:----------居左

使用----------:居右




第一列
第二列
第三列




第一列文本居中
第二列文本居右
第三列文本居左


SmartyPants
SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如：




TYPE
ASCII
HTML




Single backticks
'Isn't this fun?'
‘Isn’t this fun?’


Quotes
"Isn't this fun?"
“Isn’t this fun?”


Dashes
-- is en-dash, --- is em-dash
– is en-dash, — is em-dash


创建一个自定义列表

Markdown
Text-to-HTML conversion tool
Authors
John
Luke

如何创建一个注脚
一个具有注脚的文本。
注释也是必不可少的
Markdown将文本转换为 HTML。
KaTeX数学公式
您可以使用渲染LaTeX数学表达式 KaTeX:
Gamma公式展示 $\Gamma(n) = (n-1)!\quad\forall
n\in\mathbb N$ 是通过欧拉积分
$\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,.$

你可以找到更多关于的信息 LaTeX 数学表达式here.

新的甘特图功能，丰富你的文章


关于 甘特图 语法，参考 这儿,

UML 图表
可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图：:

这将产生一个流程图。:


关于 Mermaid 语法，参考 这儿,

FLowchart流程图
我们依旧会支持flowchart的流程图：


关于 Flowchart流程图 语法，参考 这儿.

导出与导入
导出
如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ，生成一个.md文件或者.html文件进行本地保存。
导入
如果你想加载一篇你写过的.md文件或者.html文件，在上方工具栏可以选择导入功能进行对应扩展名的文件导入，

继续你的创作。



mermaid语法说明 ↩︎

注脚的解释 ↩︎

原文链接

 在机器学习以及优化组合问题中，最常用的方法就是梯度下降法。比如BP神经网络，多层感知器的神经元(units)越多，对应的权矩阵也就越大，每个权可视为一个自由度或者变量。我们知道自由度越高，变量越多，模型越复杂，模型的能力越强。但是模型能力越强，模型就越容易过拟合，对噪声太敏感。另一方面，使用梯度下降进行最优解搜寻时，多变量的误差曲面很像是连绵起伏的山峰一样，变量越多，山峰和山谷也越多，这就导致梯度下降法极容易陷入到局部的一个小山谷，而停止搜索（局部最优）。这就是常规的梯度下降法在解决多维度的优化问题中最常见的局部最优问题。究其原因是梯度下降法的搜索准则所致，按照梯度的负方向搜索，一味追求网络误差或能量函数的降低，使得搜索只具有“下山”的能力，而不具备“爬山”的能力。所谓“爬山”的能力，就是当搜索陷入局部最优时，还能具备一定的“翻山越岭”的能力，能够从局部最优中逃出来，继续搜索全局最优。如果为具有多个局部极小点的系统打一个形象的比喻。设想托盘上有一个凸凹不平的多维能量曲面，若在该曲面上放置一个小球，它在重力作用下，将滚入最邻近的一个低谷（局部最小点）而不能自拔。但该低谷不一定就是曲面上最低的那个低谷（全局最小点）。因此，
 局部极小问题只能通过改进算法来解决 。一种可行的办法就是刚才所提到的让算法具有“爬山”的能力，同时还要保证当搜索进入全局最优时不会因为“爬山”而跑出全局最优的“山谷”。本文要讲解的随机神经网络：模拟退火(Simulated Annealing)与玻尔兹曼机(Boltzmann Machine)就是通过一定的概率保证搜索陷入局部最优时能够具有一定的“爬山”能力。这个形象的对比可参看下图：


 随机神经网络与其他神经网络相比有两个主要区别
 ：① 在学习阶段 ， 随机网络不像其他网络那样基于某种确定性算法调整权值，而是按某种概率分布进行修改；② 在运行阶段，随机网络不是按某种确定性的网络方程进行状态演变，而是按某种概率分布决定其状态的转移。神经元的净输入不能决定其状态取１还是取０，但能决定其状态取１还是取０的概率。这就是随机神经网络算法的基本概念。 


 模拟退火算法是随机网络中解决能量局部极小问题的一个有效方法，其基本思想是模拟金属退火过程。金属退火过程大致是，先将物体加热至高温，使其原子处于高速运动状态，
 此时物体具有较高的内能；然后，缓慢降温，随着温度的下降，原子运动速度减慢，内能下降；最后，整个物体达到内能最低的状态。模拟退火过程相当于沿水平方向晃动托盘，温度高则意味着晃动的幅度大，小球肯定会从任何低谷中跳出，而落入另一个低谷。这个低谷的高度（网络能量）可能比小球原来所在低谷的高度低（网络能量下降） ，但也可能反而比原来高（能量上升）。后一种情况的出现，从局部和当前来看，这个运动方向似乎是错误的；但从全局和发展的角度看，正是由于给小球赋予了“爬山”的本事，才使它有可能跳出局部低谷而最终落入全局低谷。当然，晃动托盘的力度要合适，并且还要由强至弱（温度逐渐下降），小球才不致于因为有了“爬山”的本领而越爬越高
 。

 在随机网络学习过程中，先令网络权值作随机变化，然后计算变化后的网络能量函数。网络权值的修改应遵循以下准则：若权值变化后能量变小，则接受这种变化；否则也不应完全拒绝这种变化，而是按预先选定的概率分布接受权值的这种变化。其目的在于赋予网络一定的“爬山”能力。
 实现这一思想的一个有效方法就是Metropolis 等人提出的模拟退火算法。

 设 X 代表某一物质体系的微观状态（一组状态变量，如粒子的速度和位置等），E（X）表示该物质在某微观状态下的内能，对于给定温度 T，如果体系处于热平衡状态，则在降温退火过程中，其处于某能量状态的概率与温度的关系遵循 Boltzmann
 分布规律。分布函数为：

P(E)∝
 exp(-E(X)/KT)

 K为波耳兹曼常数，为了讨论方便，将K直接融入到T中进行讨论。当温度一定时，物质体系的能量越高，其处于该状态的概率就越低，因此物质体系的内能趋向于向能量降低的方向演变。如给定不同的温度，上式表示的曲线变化如下图所示：




 当物体温度T较高时，P(E)对能量E的大小不敏感，因此物体处于高能或低能状态的概率相差不大；随着温度T的下降，物质处于高能状态的概率随之减小而处于低能状态的概率增加；当温度接近０时，物体处于低能状态的概率接近１。由此可见，温度参数T越高，状态越容易变化。为了使物质体系最终收敛到低温下的平衡态，应在退火开始时设置较高的温度，然后逐渐降温，最后物质体系将以相当高的概率收敛到最低能量状态。


 用随机神经网络解决优化问题时，通过数学算法模拟了以上退火过程。模拟方法是，定义一个网络温度以模仿物质的退火温度，取网络能量为欲优化的目标函数。网络运行开始时温度较高，调整权值时允许目标函数偶尔向增大的方向变化，以使网络能跳出那些能量的局部极小点。随着网络温度不断下降至０，最终以概率１稳定在其能量函数的全局最小点，从而获得最优解。