蛋白质相互作用网络
从分子水平上看，生命现象产生于生物分子之间的相互作用。生物分子之间的这种相互作用关系可以通过网络来表示，其中节点表示基因、蛋白质或代谢物，而边表示蛋白质之间的物理相互作用，转录调控或代谢反应。常见的网络有基因调控网络、蛋白质相互作用网络及新陈代谢网络。正确地构建这些网络是在分子水平上理解生命的关键步骤之一。因此，关于生物网络的构建成为了系统生物学的研究热点之一。
细胞各种重要生理过程的实现，包括信号的传导、对外界环境及内部环境变化的响应等都是以蛋白质之间相互作用为基础。近年来，蛋白质相互作用网络已经得到了广泛的研究。随着酵母双杂交，基于质谱的串联亲和纯化等高通量实验技术的发展和生物信息学在蛋白质相互作用预测领域的广泛应用，人们得到越来越多可利用的蛋白质相互作用数据来构建蛋白质相互作用网络[1-5]。对这些蛋白质相互作用网络结构特征的研究发现蛋白质相互作用网络具有如下有趣的拓扑性质：(1) 蛋白质相互作用网络是稀疏的，节点的平均度都比较小；(2) 蛋白质相互作用网络是小世界网络，具有较短的平均路径长度及与纯粹的随机图相比较 大的平均聚类系数[4-7]；(3) 蛋白质相互作用网络是无标度网络[6,8]，也就是， 这些网络的度分布服从幂律分布1()P k k θ- 。这意味着蛋白质相互作用网络是高度异质(heterogeneous)的，即存在大量的拥有少量边的节点和小数目的拥有大量边的枢纽(hubs)节点；(4) 蛋白质相互作用网络具有功能模块结构[9,10]，即度为k 的节点的平均聚类系数()C k 以幂率2()C k k θ- 衰减。这表明拥有少量边的节点具有大的聚类系数属于稠密连接的小子网络，而枢纽节点具有小的聚类系数连接着不同的子网络[12]，显示出了功能模块结构；(5) 蛋白质相互作用网络表现出度负关联的性质[12,13]，其中所有度为k 的节点的邻居的平均度()nn K k 遵循3()nn K k k θ- 。因此，度大与度小节点之间的连接被累积，而那些度大与度大以及度小与度小节点之间的连接被抑制[12,13]。
为了再现蛋白质相互作用网络的上述拓扑特征，科研工作者已经提出了各种各样基于复制和变异的网络增长模型。文献[7,14]中作者提出了两个简单的蛋白质演化模型来再现蛋白质相互作用网络的无标度和小世界性质。Chung 等[15]分析了节点的完全复制和部分复制的图演化模型，并指出节点的部分复制可以产生幂
指数小于2的幂律特征图。基于基因的复制和新生成基因的重连，Pastor-Satorras等[16]研究了蛋白质相互作用的演化并指出该机制可以再现人们熟知的生物的蛋白质组的统计特征。Ispolatov等[17]提出了一个单参数的复制变异网络模型来描述蛋白质相互作用网络的演化，并考虑了当参数变化时网络的自平均(self-average)性质。另外，Ispolatov等[18]还研究了网络中团(clique)的分布。文献[19,20]中Liu等讨论了复制和变异对生物网络的度负关联性的影响。然而，据我们所知，所有上述的理论模型都没有说明网络的功能模块结构。最近，Takemoto等[21]完全从理论上提出了一种通过合并全连通子图来演化网络模型，并表明该演化模型可以生成幂律度分布和功能模块结构。进一步地，他们对该模型进行了改进，用适应性驱使的择优连接(preferential attachment)来选择n个节点，结果表明改进的模型生成的网络除了具有幂律度分布和功能模块结构外，还具有度负关联性质[22]。
[ 1 ] Uetz P, Giot L, Cagney G, Mansfield T A, Judson R S, etal. 2000 Nature403 623
[ 2 ] Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, et al. 2001 Pro. Natl. Acad. Sci. USA98 4569
[ 3 ] Guldener U, Munsterkotter M, Hattori M, et al. 2006 Nucleic Acids. Res. 34 436
[ 4 ] Li S, Armstrong C M, Bertin N, Ge H, Milstein S, et al. 2004 Science 303 540
[ 5 ] Giot L, Bader J S, Brouwer C, Chaudhuri A, Kuang B, et al. 2003 Science 302 1727
[ 6 ] Wanger A 2001 Mol. Biol. Evol. 18 1283
[ 7 ] Sole R V, Pastor-Satorras R, Smith E D, Kepler T 2002 Adv. Comp. Syst.5 43
[ 8 ] Jeong H, Mason S P, Barabasi A L, Oltvai Z N 2001 Nature411 41
[ 9 ] Ravasz E, Barabasi A L 2003 Phys. Rev. E67 026112
[ 10 ] Williams R J, Martinez N D, Berlow E L, Dunne J A, Barabasi A L 2002 Science297 1551.
[ 11 ] Yook S H, Oltvai Z N, Barabasi A L 2004 Proteomics 4 929
[ 12 ] Hase T , Niimura Y, Kaminuma T, Tanaka H 2008 Plos ONE3 e1667
[ 13 ] Maslov S, Sneppen K 2002 Science 296 910
[ 14 ] Vazquez A, Flammini A, Maritan A 2003 ComPlexUs1 38
[ 15 ] Chung F , Lu L , Dewey T G, Galas D J 2003 J. Comput. Biol.10 677
[ 16 ] Pastor-Satorras R., Smith E., Sole R.V 2003 J. Theor. Biol.222 199
[ 17 ] Ispolatov I, Krapivsky P L, Yuryev A 2005 Phys. Rev. E71 061911
[ 18 ] Ispolatov I, Krapivsky P L, Yuryev A 2005 New J. Phys.7 145
[ 19 ] Dan Z, Liu Z R, Wang J Z 2007 Chin. Phys. Lett.24 2766
[ 20 ] Xu C S,Liu Z R, Wang R Q 2010 Physica A389 643
[ 21 ] Takemoto K, Oosawa C 2005 Phys. Rev. E71 046116
[ 22 ] Takemoto K, Oosawa C 2007 Math. Bios.208 454
第五章 图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总
基于人工神经网络的通信信号分类识别 冯 涛 (中国电子科技集团公司第54研究所,河北石家庄050081) 摘 要 通信信号的分类识别是一种典型的统计模式识别问题。系统地论述了通信信号特征选择、特征提取和分类识别的原理和方法。设计了人工神经网络分类器,包括神经网络模型的选择、分类器的输入输出表示、神经网络拓扑结构和训练算法,并提出了分层结构的神经网络分类器。 关键词 模式识别;特征提取;分类器;神经网中图分类号 TP391 文献标识码 A Classification and Identification of Communication Signal Using Artificial Neural Networks FE NG Tao (T he 54th Research Institute of CETC,Shijia zhuan g Hebei 050081,China) Abstract The classification and identificati on of communication signal is a typical statistical pattern identification.The paper discusses the theory and method of feature selection,feature extraction and classi fication &identificaiton of communication signal.A classifier based on artificial neural networks is designed,includin g the selection of neural network model,the input and output expression of the classifier,neural network topology and trainin g algorithm.Finally a hierarchical archi tecture classifier based on artificial neural networks is presented. Key words pattern recognition;features extraction;classifier;neural networks 收稿日期:2005-12-16 0 引言 在通信对抗侦察中,侦察接收设备在截获敌方通信信号后,必须经过对信号的特征提取和对信号特征的分析识别,才能变为有价值的通信对抗情报。通过对信号特征的分析识别,可以得到信号种类、通信体制、网路组成等方面的情报,从而为研究通信对抗策略、研制和发展通信对抗装备提供重要参考依据。 1 通信信号分类识别的原理 通信信号的分类识别是一种典型的模式识别应用,其作用和目的就是将某一接收到的信号正确地归入某一种类型中。一般过程如图1 所示。 图1 通信信号分类识别的一般过程 下面简单介绍这几部分的作用。 信号获取:接收来自天线的信号x (t),并对信号进行变频、放大和滤波,输出一个中频信号; A/D 变换:将中频模拟信号变换为计算机可以运算的数字信号x (n); 以上2步是信号空间x (t)到观察空间x (n )的变换映射。 特征提取:为了有效地实现分类识别,必须对原始数据进行变换,得到最能反映分类差别的特征。这些特征的选择和提取是非常重要的,因为它强烈地影响着分类器的设计和性能。理想情况下,经过特征提取得到的特征向量对不同信号类型应该有明显的差别; 分类器设计和分类决策:分类问题是根据识别对象特征的观察值将其分到某个类别中去。首先,在样本训练集基础上确定合适的规则和分类器结构,然后,学习训练得到分类器参数。最后进行分类决策,把待识别信号从特征空间映射到决策空间。 2 通信信号特征参数的选择与特征提取 2 1 通信信号特征参数的选择 选择好的特征参数可以提高低信噪比下的正确 识别率,降低分类器设计的难度,是基于统计模式识别方法最为关键的一个环节。试图根据有限的信号 信号与信息处理 24 2006Radio Engineering Vo1 36No 6
function [DeD,aver_DeD]=Degree_Distribution(A) %% 求网络图中各节点的度及度的分布曲线 %% 求解算法：求解每个节点的度，再按发生频率即为概率，求P(k) %A————————网络图的邻接矩阵 %DeD————————网络图各节点的度分布 %aver_DeD———————网络图的平均度 N=size(A,2); DeD=zeros(1,N); for i=1:N % DeD(i)=length(find((A(i,:)==1))); DeD(i)=sum(A(i,:)); end aver_DeD=mean(DeD); if sum(DeD)==0 disp('该网络图只是由一些孤立点组成'); return; else figure; bar([1:N],DeD); xlabel('节点编号n'); ylabel('各节点的度数K'); title('网络图中各节点的度的大小分布图'); end figure; M=max(DeD); for i=1:M+1; %网络图中节点的度数最大为M,但要同时考虑到度为0的节点的存在性 N_DeD(i)=length(find(DeD==i-1)); % DeD=[2 2 2 2 2 2] end P_DeD=zeros(1,M+1); P_DeD(:)=N_DeD(:)./sum(N_DeD); bar([0:M],P_DeD,'r'); xlabel('节点的度 K'); ylabel('节点度为K的概率 P(K)'); title('网络图中节点度的概率分布图'); 平均路径长度 function [D,aver_D]=Aver_Path_Length(A) %% 求复杂网络中两节点的距离以及平均路径长度 %% 求解算法：首先利用Floyd算法求解出任意两节点的距离，再求距离的平均值得平均路
第五章 图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
本文首先分析了图像识别技术以及bp神经网络算法，然后详细地阐述了人工神经网络图像识别技术。 【关键词】人工神经网络 bp神经网络图像识别识别技术 通常而言，所谓图像处理与识别，便是对实际图像进行转换与变换，进而达到识别的目的。图像往往具有相当庞大的信息量，在进行处理图像的时候要进行降维、数字化、滤波等程序，以往人们进行图像识别时采用投影法、不变矩法等方法，随着计算机技术的飞速发展，人工神经网络的图像识别技术将逐渐取代传统的图像识别方法，获得愈来愈广泛的应用。 1 人工神经网络图像识别技术概述 近年来，人工智能理论方面相关的理论越来越丰富，基于人工神经网络的图像识别技术也获得了非常广泛的应用，将图像识别技术与人工神经网络技术结合起来的优点是非常显著的，比如说： （1）由于神经网络具有自学习功能，可以使得系统能够适应识别图像信息的不确定性以及识别环境的不断变化。 （2）在一般情况下，神经网络的信息都是存储在网络的连接结构以及连接权值之上，从而使图像信息表示是统一的形式，如此便使得知识库的建立与管理变得简便起来。 （3）由于神经网络所具有的并行处理机制，在处理图像时可以达到比较快的速度，如此便可以使图像识别的实时处理要求得以满足。 （4）由于神经网络可增加图像信息处理的容错性，识别系统在图像遭到干扰的时候仍然能正常工作，输出较准确的信息。 2 图像识别技术探析 2.1 简介 广义来讲，图像技术是各种与图像有关的技术的总称。根据研究方法以及抽象程度的不同可以将图像技术分为三个层次，分为：图像处理、图像分析以及图像理解，该技术与计算机视觉、模式识别以及计算机图形学等学科互相交叉，与生物学、数学、物理学、电子学计算机科学等学科互相借鉴。此外，随着计算机技术的发展，对图像技术的进一步研究离不开神经网络、人工智能等理论。 2.2 图像处理、图像识别与图像理解的关系 图像处理包括图像压缩、图像编码以及图像分割等等，对图像进行处理的目的是判断图像里是否具有所需的信息并滤出噪声，并对这些信息进行确定。常用方法有灰度，二值化，锐化，去噪等；图像识别则是将经过处理的图像予以匹配，并且对类别名称进行确定，图像识别可以在分割的基础之上对所需提取的特征进行筛选，然后再对这些特征进行提取，最终根据测量结果进行识别；所谓图像理解，指的是在图像处理与图像识别的基础上，根据分类作结构句法分析，对图像进行描述与解释。所以，图像理解包括图像处理、图像识别和结构分析。就图像理解部分而言，输入是图像，输出是对图像的描述解释。 3 人工神经网络结构和算法 在上个世纪八十年代，mcclelland与rumelhant提出了一种人工神经网络，截止现在，bp神经网络已经发展成为应用最为广泛的神经网络之一，它是一种多层前馈神经网络，包括输入层、输出层和输入层输出层之间隐藏层，如图1所示，便是一种典型的bp神经网络结构。 bp神经网络是通过不断迭代更新权值使实际输入与输出关系达到期望，由输出向输入层反向计算误差，从而通过梯度下降方法不断修正各层权值的网络。 bp神经网络结构算法如下所述： （1）对权值矩阵，学习速率，最大学习次数，阈值等变量和参数进行初始化设置； （2）在黑色节点处对样本进行输入；
SWISS-MODEL 蛋白质结构预测 SWISS-MODEL是一项预测蛋白质三级结构的服务，它利用同源建模的方法实现对一段未知序列的三级结构的预测。该服务创建于1993年,开创了自动建模的先河,并且它是讫今为止应用最广泛的免费服务之一。 同源建模法预测蛋白质三级结构一般由四步完成： 1.从待测蛋白质序列出发，搜索蛋白质结构数据库（如PDB,SWISS-PROT等），得到许多相似序 列（同源序列），选定其中一个（或几个）作为待测蛋白质序列的模板； 2.待测蛋白质序列与选定的模板进行再次比对，插入各种可能的空位使两者的保守位置尽量对齐； 3.建模：调整待测蛋白序列中主链各个原子的位置，产生与模板相同或相似的空间结构——待测 蛋白质空间结构模型； 4.利用能量最小化原理，使待测蛋白质侧链基团处于能量最小的位置。 最后提供给用户的是经过如上四步（或重复其中某几步）后得到的蛋白质三级结构。 SWISS-MODEL工作模式 SWISS-MODEL服务器是以用户输入信息的最小化为目的设计的，即在最简单的情况下，用户仅提供一条目标蛋白的氨基酸序列。由于比较建模程序可以具有不同的复杂性，用户输入一些额外信息对建模程序的运行有时是有必要的，比如，选择不同的模板或者调整目标模板序列比对。该服务主要有以下三种方式: ?First Approach mode(简捷模式）：这种模式提供一个简捷的用户介面：用户只需要输入一条氨基酸序列，服务器就会自动选择合适的模板。或者，用户也可以自己指定模板（最多5条），这些模板可以来自ExPDB模板数据库（也可以是用户选择的含坐标参数的模板文件）。如果一条模板与提交的目标序列相似度大于25%，建模程序就会自动开始运行。但是，模板的可靠性会随着模板与目标序列之间的相似度的降低而降低，如果相似度不到50%往往就需要用手工来调整序列比对。这种模式只能进行大于25个残基的单链蛋白三维结构预测。 ?Alignment Interface（比对界面）：这种模式要求用户提供两条已经比对好的序列，并指定哪一条是目标序列，哪一条是模板序列（模板序列应该对应于ExPDB模板数据库中一条已经知道其空间结构的蛋白序列）。服务器会依据用户提供的信息进行建模预测。
BP神经网络模型 第1节基本原理简介 近年来全球性的神经网络研究热潮的再度兴起，不仅仅是因为神经科学本身取得了巨大的进展．更主要的原因在于发展新型计算机和人工智能新途径的迫切需要．迄今为止在需要人工智能解决的许多问题中，人脑远比计算机聪明的多，要开创具有智能的新一代计算机，就必须了解人脑，研究人脑神经网络系统信息处理的机制．另一方面，基于神经科学研究成果基础上发展出来的人工神经网络模型，反映了人脑功能的若干基本特性，开拓了神经网络用于计算机的新途径．它对传统的计算机结构和人工智能是一个有力的挑战，引起了各方面专家的极大关注． 目前，已发展了几十种神经网络，例如Hopficld模型，Feldmann等的连接型网络模型，Hinton等的玻尔茨曼机模型，以及Rumelhart等的多层感知机模型和Kohonen的自组织网络模型等等。在这众多神经网络模型中，应用最广泛的是多层感知机神经网络。多层感知机神经网络的研究始于50年代，但一直进展不大。直到1985年，Rumelhart等人提出了误差反向传递学习算法（即BP算），实现了Minsky的多层网络
设想，如图34-1所示。 BP 算法不仅有输入层节点、输出层节点，还可有1个或多个隐含层节点。对于输入信号，要先向前传播到隐含层节点，经作用函数后，再把隐节点的输出信号传播到输出节点，最后给出输出结果。节点的作用的激励函数通常选取S 型函数，如 Q x e x f /11)(-+= 式中Q 为调整激励函数形式的Sigmoid 参数。该算法的学习过程由正向传播和反向传播组成。在正向传播过程中，输入信息从输入层经隐含层逐层处理，并 传向输出层。每一层神经元的状态只影响下一层神经
§5 最短投递路线的设计 一、最优环游 邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。 在一个网络),,(W E V N =中，经过它的每条边的链称为欧拉链，经过N 中每一边至少一次的闭链称为N 的环游，经过N 中每一边恰好一次的环游称为欧拉环游。一个图能一笔画就是该图有欧拉环游。显然上述问题就是在具有非负权的网络中找出一条权最小的环游，这种环游称为最优环游。 若N 有欧拉环游，则它的每一条欧拉环游具有相同的权，它也必然是最优环游。对有欧拉环游的网络，我们可以采用弗莱里（Fleury ）算法求得N 的最优环游。 弗莱里算法 计算步骤如下： 1、任意选取N 的一个顶点0v ，置0v Z =； 2、假设链i i v e v e v Z 110=已选定，从},,,{\21i e e e E 中按下述方法选取1+i e ： （1）1+i e 和i v 相关联； （2）1+i e 尽量不选i G （是G 中去掉边i e e e ,,,21 而得到的图）的割边（即去掉此边后，图i G 变为不连通），除非没有非割边可选择。 3、设1+i e 另一关联点为1+i v 。若φ≠+},,,{\121i e e e E ，重复步骤2；否则11211++i i v e v e v 即为N 的一条欧拉环游。 若网络N 没有欧拉环游，此时最优环游通过的某些边将超过一次。下面是一种有关引进重复边的算法。将边e 的两个端点再用一条权为)(e W 的新边连接时，称为边e 的重复边。 因此，问题可以重新叙述如下：给定一个具有非负权的网络N ， （1）用添重复边的方法求得N 的一个欧拉赋权母图* N ，使得下式尽可能小； ∑∈) (}\{*)(N E N e e W （2）求* N 的欧拉环游。 当点数较少时，可用奇偶点图上作业法求解，为此我们不加证明介绍下述两个结论。 结论1 网络N 有欧拉环游当且仅当N 中每一点的次为偶数。 结论2 最优环游具有这样的性质：（1）每条边至多重复一次；（2）每一圈上重复边的长度不超过该圈总长的一半。
第4卷第3期 复杂系统与复杂性科学 Vol.4No.3 2007年9月 C OMP LEX SYSTE M S AND COM P LEX I TY SC I E NCE Sep.2007 文章编号:1672-3813(2007)03-0001-09 开源软件的复杂网络分析及建模 郑晓龙,曾大军,李慧倩,毛文吉,王飞跃,戴汝为 (中国科学院自动化研究所复杂系统与智能科学重点实验室,北京100080) 摘要:开源软件现在变得越来越复杂。把开源软件看作复杂网络并进行研究,有助 于更好地理解软件系统。同时,开源软件是一种较为复杂的人工系统,通过对它们 的研究也可以推动复杂网络理论的应用。以一种基于源代码包的L inux操作系 统———Gent oo L inux操作系统为研究对象,我们把该系统中的软件包抽象成节点, 软件包之间的依赖关系抽象成边,以此建立复杂网络,并对其进行了分析。发现已 有模型不能很好地描述与预测Gent oo网的演化过程,因此,提出了一种新的演化模型。在该模型中,网络现有节点连接新节点的概率不但与现有节点的度有关系,而且也受到现有节点“年龄”的影响。还通过计算机仿真实验把仿真数据与Gent oo真实数据进行了比较,结果显示,新模型更为适合Gent oo网。 关键词:复杂网络;Gent oo;聚集系数;度分布;模型 中图分类号:N94;TP393;TP31文献标识码:A Ana lyz i n g and M odeli n g O pen Source Software a s Co m plex Networks ZHENG Xiao2l ong,ZENG Da2jun,L I Hui2qian,MAO W en2ji,WANG Fei2yue,DA I Ru2wei (The Key Laborat ory of Comp lex Syste m s and I ntelligence Science,I nstitute of Aut omati on, Chinese Academy of Sciences,Beijing100080,China) Abstract:Soft w are syste m s including those based on open2s ource code are becom ing increasingly com2 p lex.Studying the m as comp lex net w orks can p r ovide quantifiable measures and useful insights fr om the point of vie w of s oft w are engineering.I n the mean while,as one of the most comp lex man2made artifacts, they p r ovide a fruitful app licati on domain of comp lex syste m s theory.I n this paper,we analyze one of the most popular L inux meta packages/distributi ons called the Gent oo syste m.I n our analysis,we model s oft2 ware packages as nodes and dependencies a mong the m as arcs.Our e mp irical study shows that the resul2 ting Gent oo net w ork can not be exp lained by existing random graph models.This motivates our work in devel op ing a ne w model in which ne w nodes are connected t o old nodes with p r obabilities that depend not only on the degrees of the old nodes but als o the“ages”of these nodes.Thr ough si m ulati on,we de mon2 strate that our model has better exp lanat ory power than the existing models. Key words:comp lex net w orks;Gent oo;cluster coefficient;degree distributi on;model 收稿日期:2007-08-23 基金项目:国家自然科学基金委基金(60621001,60573078);科技部973项目(2006CB705500,2004CB318103);中国科学院、国家外国专家局,创新团队国际合作伙伴计划(2F05N01) 作者简介:郑晓龙(1982-),男,安徽人,博士研究生,研究方向为复杂网络与数据挖掘。
人工神经网络的模型:人工神经元的模型、常用的激活转移函数、MP模型神经元 人工神经元的主要结构单元是信号的输入、综合处理和输出 人工神经元之间通过互相联接形成网络，称为人工神经网络 神经元之间相互联接的方式称为联接模式。相互之间的联接强度由联接权值体现。 在人工神经网络中，改变信息处理及能力的过程，就是修改网络权值的过程。 人工神经网络的构造大体上都采用如下的一些原则： 由一定数量的基本神经元分层联接； 每个神经元的输入、输出信号以及综合处理内容都比较简单； 网络的学习和知识存储体现在各神经元之间的联接强度上。 神经网络解决问题的能力与功效除了与网络结构有关外，在很大程度上取决于网络激活函数。人工神经网络是对人类神经系统的一种模拟。尽管人类神经系统规模宏大、结构复杂、功能神奇，但其最基本的处理单元却只有神经元。人工神经系统的功能实际上是通过大量神经元的广泛互连，以规模宏伟的并行运算来实现的。 人工神经网络模型至少有几十种，其分类方法也有多种。例如，若按网络拓扑结构，可分为无反馈网络与有反馈网络；若按网络的学习方法，可分为有教师的学习网络和无教师的学习网络；若按网络的性能，可分为连续型网络与离散型网络，或分为确定性网络与随机型网络；若按突触连接的性质，可分为一阶线性关联网络与高阶非线性关联网络。 人工神经网络的局限性： (1) 受到脑科学研究的限制：由于生理实验的困难性，因此目前人类对思维和记忆机制的认识还很肤浅，还有很多问题需要解决； (2) 还没有完整成熟的理论体系； (3) 还带有浓厚的策略和经验色彩； (4) 与传统技术的接口不成熟。 如果将大量功能简单的形式神经元通过一定的拓扑结构组织起来，构成群体并行分布式处理的计算结构，那么这种结构就是人工神经网络，在不引起混淆的情况下，统称为神经网络。根据神经元之间连接的拓扑结构上的不同，可将神经网络结构分为两大类：分层网络相互连接型网络 分层网络可以细分为三种互连形式： 简单的前向网络； 具有反馈的前向网络； 层内有相互连接的前向网络。 神经网络的学习分为三种类型：有导师学习、强化学习无导师学习 有导师学习：必须预先知道学习的期望结果——教师信息，并依此按照某一学习规则来修正权值。 强化学习：利用某一表示“奖／惩”的全局信号，衡量与强化输入相关的局部决策如何。 无导师学习：不需要教师信息或强化信号，只要给定输入信息，网络通过自组织调整，自学习并给出一定意义下的输出响应。 神经网络结构变化的角度，学习技术还可分为三种: 权值修正、拓扑变化、权值与拓扑修正学习技术又还可分为：确定性学习、随机性学习 人工神经网络 人工神经网络是生物神经网络的某种模型(数学模型)；是对生物神经网络的模仿 基本处理单元为人工神经元 生物神经元(neuron)是基本的信息处理单元
图与网络模型及方法学习心得 摘要：图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的《哥尼斯堡的七座桥》。1847年，克西霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计算烷烃的同分异构体时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈。近几十年来，计算机技术和科学的飞速发展，大大促进了凸轮的研究和应用，凸轮的理论和方法已经渗透到物理、化学、通信科学、建筑学、运筹学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点来表示这些具体的事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”、七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 正文：在寒假中，学习了图论这一章以后，对于此类问题的解决方法就是构造
基于人工神经网络的故障诊断 基于人工神经网络的故障诊断 【摘要】随着高新技术的发展，人工神经网络的模式识别在设备的故障诊断上得以广泛地应用。机器设备或者系统的故障诊断实质是一个模式识别过程。把对经过处理后的信号数据的有效时、频特征值作为神经网络的输入层，利用Matlab软件，便可得到不同的模式输出，进而可以辨别设备是否有故障。 【关键词】人工神经网络；故障诊断；模式识别；Matlab软件 一、人工神经网络综述 BP神经网络是目前应用最为广泛和成功的神经网络之一，它是由一个输入层，一个或多个隐层以及一个输出层组成，上下层之间实现全连接，而每层神经元之间没有连接。网络的学习过程包括信号正向传播和误差反向传播。在正向传播进程中，输入信息从输入层经隐层加权处理传向输出层，经功能函数运算后得到的输出值与期望值进行比较，若有误差，则误差反向传播，沿原先的连接通道返回，通过逐层修改各层的权重系数，减小误差。随着这种误差逆向传播修正的不断进行，网络对输入模式响应的正确率也不断上升。 二、人工神经网络的识别、诊断过程 滚动轴承在设备中是比较典型的，本文以滚动轴承的故障识别、诊断为例。进行模式识别的大体步骤为：首先对经过零均值化后的振动信号数据进行时域、频域分析，将筛选后的有效时域、频域特征值作为人工神经网络输入层的输入，经Matlab软件进行神经网络的训练，最后可得出一个可以识别轴承工作状态的神经网络，进而可以对滚动轴承进行模式识别。可见采用振动信号检测法对机器设备进行故障诊断的过程包含信号采集、特征提取、状态识别、故障分析和决策干预等五个基本环节，在滚动轴承故障诊断中，振动信号的采集是关键，保证信号采集的准确性、合理性和实时性是正确实现故障诊断的前提。（1）信号采集。每台机器设备都有自身的固有频率，若设备发生故障，其频率变化，其振动信号也会发生变化。因此，振动信号可
动力学系统建模课程报告
神经网络综述 1 神经网络介绍 1.1 神经网络概述 人工神经网络简称为神经网络或称作连接模型，它是一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络可以看成以人工神经为节点，用有向加权弧连接起来的有向图，有向弧的权值表示两个人工神经元相互作用的强弱。人工神经网络模拟人类大脑神经元结构及处理问题的方式，成为为人工智能控制上的一大创新。 人工神经网络主要优点是能够自适应样本数据，不会被噪音等影响；能够处理来自多个资源和决策系统的数据；能够提供简单工具进行特征选取，产生有用的数据表示；可作为专家系统的前端；有十分快的优化功能。神经网络可以处理非线性适应性信息，克服了传统人工智能方法对于直觉的缺陷，使之在神经专家系统、模式识别、智能控制、组合优化、预测等领域取得成功应用。 1.2人工神经网络基本要素 人工神经元四个基本要素： (1) 连接权，用于表示各个神经元的连接强度，正值表示加强，负值表示削弱，对应生物神经元的突触。 (2) 求和单元，求取对应节点输入信号的加权和，对输入信号求加权和即求解神经节点的输入信号。数学表达式：j p j kj k x w u ∑==1。 (3) 激活函数，相当于细胞体的功能，对输入的信号进行非线性映射，使输出幅值限制在一定范围内。输出表达式：)(k k net g y =。激活函数有阶跃函数、分段线性函数、sigmoid 函数及双曲正切对称S 型函数。 (4) 阀值，其作用可用数学表达式来表示：k k k u net θ-=。 1.3人工神经网络的工作方式 其工作过程主要分为两个阶段： (1) 学习期，此时每一个计算单元的状态不变，样本数据进行输入，得到实际输出，与期望输出进行对比得出输出误差，根据输出误差修改权值，直至系统参数满足输出误
关于人工神经网络的学习方法 信计一班陈思为0857129 摘要：人工神经网络是一种新的数学建模方式，它具有通过学习逼近任意非线性映射的能力。本文提出了一种基于动态BP神经网络的猜测方法，阐述了其基本原理，并以典型实例验证。关键字：神经网络，BP模型。 引言： 在系统建模、辨识和猜测中，对于线性系统，在频域，传递函数矩阵可以很好地表达系统的黑箱式输入输出模型；在时域，Box－Jenkins方法、回归分析方法、ARMA模型等，通过各种参数估计方法也可以给出描述。对于非线性时间序列猜测系统，双线性模型、门限自回归模型、ARCH模型都需要在对数据的内在规律知道不多的情况下对序列间关系进行假定。可以说传统的非线性系统猜测，在理论研究和实际应用方面，都存在极大的困难。相比之下，神经网络可以在不了解输入或输出变量间关系的前提下完成非线性建模[4，6]。神经元、神经网络都有非线性、非局域性、非定常性、非凸性和混沌等特性，与各种猜测方法有机结合具有很好的发展前景，也给猜测系统带来了新的方向与突破。建模算法和猜测系统的稳定性、动态性等研究成为当今热点问题。目前在系统建模与猜测中，应用最多的是静态的多层前向神经网络，这主要是因为这种网络具有通过学习逼近任意非线性映射的能力。利用静态的多层前向神经网络建立系统的输入/输出模型，本质上就是基于网络逼近能力，通过学习获知系统差分方程中的非线性函数。但在实际应用中，需要建模和猜测的多为非线性动态系统，利用静态的多层前向神经网络必须事先给定模型的阶次，即预先确定系统的模型，这一点非常难做到。近来，有关基于动态网络的建模和猜测的研究，代表了神经网络建模和猜测新的发展方向。 正文： 2BP神经网络模型BP网络是采用Widrow－Hoff学习算法和非线性可微转移函数的多层网络。典型的BP算法采用梯度下降法，也就是Widrow－Hoff算法。现在有许多基本的优化算法，例如变尺度算法和牛顿算法。 BP神经网络包括以下单元： ①处理单元（神经元），即神经网络的基本组成部分。输入层的处理单元只是将输入值转入相邻的联接权重，隐层和输出层的处理单元将它们的输入值求和并根据转移函数计算输出值。 ②联接权重。它将神经网络中的处理单元联系起来，其值随各处理单元的联接程度而变化。 ③层。神经网络一般具有输入层x、隐层y和输出层o。④阈值。其值可为恒值或可变值，它可使网络能更自由地获取所要描述的函数关系。⑤转移函数F。它是将输入的数据转化为输出的处理单元，通常为非线性函数。 BP神经网络结构。 1基本算法BP算法主要包含4步，分为向前传播和向后传播两个阶段：1）向前传播阶段从样本集中取一个样本，将Xp输入网络；计算相应的实际输出Op在此阶段，信息从输入层经过逐级的变换，传送到输出层。这个过程也是网络在完成练习后正常运行时的执行过程。2）向后传播阶段计算实际输出Op与相应的理想输出Yp的差；按极小化误差的方式调整权矩阵。这两个阶段的工作受到精度要求的控制，在这里取作为网络关于第p个样本的误差测度，而将网络关于整个样本集的误差测度定义为。 基本算法流程。2动态BP神经网络猜测算法在经典的BP算法以及其他的练习算法中都有很多变量，这些练习算法可以确定一个ANN结构，它们只练习固定结构的ANN权值。在自动设计ANN结构方面，也已有较多的尝试，比如构造性算法和剪枝算法。前一种是先随机化
§4 通讯网络的最小生成树 连通的无圈图称为树。树是最简单但又是十分重要的一类图，它在许多学科领域中有广泛的应用，例如分子结构，电网络分析等。最短连接问题与树有关，学科分类和一些决策过程也往往可以用树的形式表示。 图m E n V E V T ==,),,(，则下面关于树的命题是等价的。 （1）T 是一个树。 （2）T 无圈，且1-=n m 。 （3）T 连通，且1-=n m 。 （4）T 无圈，但加一新边即得唯一一个圈。 （5）T 连通，但舍去一边就不连通。 （6）T 中任意两点，有唯一链相连。 上述性质中每一个命题均可作为树的定义，它们对判断和构造树将极为方便。 若1G 是连通图2G 的生成子图，且1G 本身是树，则称1G 为2G 的生成树。 对图),(E V G =的每一条边E e ∈赋以相应的实数权)(e w ，得到一个网络，记为),,(W E V N =。设),(E V T '=是N 的一个生成树，令∑∈=' )()(E e e w T W ，则)(T W 称为T 的权， N 中权最小的生成树称为N 的最小生成树。 许多实际问题，如在若干个城市之间建造铁路网、输电网或通信网等，都可归纳为寻求连通赋权图（网络）的最小生成树问题。例如已知城市i v 和j v 间的直通线路的造价为 )),(()(j i ij ij ij v v e e w w == 要求一个总造价为最小的设计方案。又如一个城市中，对若干新建居民点供应自来水和煤气，已测知连接各点间的直通管道的造价，要求给出一个总造价最小的铺设方案等等。下面介绍在给定网络),,(W E V N =内求最小生成树的两种算法。设网络点数为n ，此时最小生成树的边数为1-n 。 算法1 （克鲁斯凯尔，Kruskal ） 算法I 的中心思想是每次添加权尽可能小的边，使新的图无圈，直到生成最小生成树为止。也形象地简称“最小边的加入法”。其步骤如下： （1）把N 内的所有边按照权的非减次序排列。 （2）按（1）排列的次序检查N 中的每一条边，如果这条边与已得到的边不产生圈，则取这一条边为解的一部分。 （3）若已取到1-n 条边，算法终止。此时以V 为顶点集，以取到的1-n 条边为边集的图即为最
人工神经网络学习总结笔记 主要侧重点： 1.概念清晰 2.进行必要的查询时能从书本上找到答案 第一章：绪论 1.1人工神经网络的概述 “认识脑”和“仿脑”：人工智能科学家在了解人脑的工作机理和思维的本质的基础上，探索具有人类智慧的人工智能系统，以模拟延伸和扩展脑功能。我认为这是人工神经网络研究的前身。 形象思维：不易被模拟 人脑思维抽象推理 逻辑思维：过程：信息概念最终结果 特点：按串行模式 人脑与计算机信息处理能力的不同点： 方面类型人脑计算机 记忆与联想能力可存储大量信息，对信息有 筛选、回忆、巩固的联想记 忆能力无回忆与联想能力，只可存取信息 学习与认知能力具备该能力无该能力 信息加工能力具有信息加工能力可认识 事物的本质与规律仅限于二值逻辑，有形式逻辑能力，缺乏辩证逻辑能力 信息综合能力可以对知识进行归纳类比 和概括，是一种对信息进行 逻辑加工和非逻辑加工相 结合的过程 缺乏该能力 信息处理速度数值处理等只需串行算法就能解决的应用问题方便，计算 机比人脑快，但计算机在处理文字图像、声音等类信息的 能力远不如人脑 1.1.2人脑与计算机信息处理机制的比较 人脑与计算机处理能力的差异最根本的原因就是信息处理机制的不同，主要有四个方面 方面类型人脑计算机 系统结构有数百亿神经元组成的神经 网络由二值逻辑门电路构成的按串行方式工作的逻辑机器 信号形式模拟量（特点：具有模糊性。离散的二进制数和二值逻辑容易被机器模拟的思维方式
难以被机器模拟）和脉冲两种 形式 形式 信息储存人脑中的信息分布存储于整个系统，所存储的信息是联想式 的 有限集中的串行处理机制信息处理机制高度并行的非线性信息处理系统 （体现在结构上、信息存储上、信 息处理的运行过程中） 1.1.3 人工神经网络的概念：在对人脑神经网络的基本认识的基础上，用数理方法从信息处理的角度对人脑神经网络进行抽象，并建立某种简化模型，称之为人工神经网络，是对人脑的简化、抽象以及模拟，是一种旨在模仿人脑结构及其功能的信息处理系统。 其他定义：由非常多个非常简单的处理单元彼此按某种方式相互连接而形成的计算系统，外部输入信息之后，系统产生动态响应从而处理信息。 它是由许多简单的并行工作的处理单元组成的系统，其功能会因网络结构、连接强度以及各单元的处理方式的不同而不同 1.3神经网络的基本特点与功能 基本特点：1、结构特点：信息处理的并行性、信息存储的分布性、信息处理单元的互联性、结构的可塑性。神经网络内在的并行性与分布性表现在其信息的存储于处理都是空间上分布、时间上并行的。 2、性能特点：高度的非线性、良好的容错性和计算的非精确性。 3、能力特征：自学习、自组织（重构）与自适应性。 神经网络的基本功能：1、联想记忆：自联想记忆与异联想记忆 2、非线性映射 3、分类与识别 4、优化计算 5、知识处理 第二章人工神经网络建模基础 2.1～2.2 讲述了生物神经系统以及生物神经网络的建模基础 神经元所产生的信息是具有电脉冲形式的神经冲动，脉冲的宽度和幅度相同，但是间隔是随机变化的。 人脑中，外界的刺激不同可以改变神经元之间的突触关系，即突触厚膜电位的方向以及大小，从突触信息传递的角度来看，表现为放大倍数和极性的变化。 空间整合的概念（BP29）信息整合这一段中 阀值特性：我认为阀值特性即静息电位必须上升到一定数值范围即超过阀值电位之后，神经元才会产生兴奋，信息才能以脉冲的形式得到传递。 所谓的时间整合，如果由一个脉冲所引起的突触膜后电位很小，只有在持续时间内当另一脉冲到达的时候，总的突触膜后电位增大。 2.3 人工神经元模型 人工神经网络是在现代神经生物学研究基础上提出的模拟生物的过程，反映人脑某些特性的一种计算结构，是人脑神经系统的一种抽象、简化和模拟而不是对它的真实描写。神经网络的基本器件是神经元和突触。人工神经网络当中的神经元是处理单元，也称之为节点。人工神经元是对生物神经元的信息处理过程的抽象模拟，通过数学语言对其进行描述，对其结构和功能进行模拟，用模型图予以表达。 2.3.1 神经元的建模