基于复杂网络的元胞自动机复杂度分类研究

《基于复杂网络的元胞自动机复杂度分类研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代号10530学号201510111153分类号O236密级硕士学位论文基于复杂网络的元胞自动机复杂度分类研究学位申请人徐成指导教师舒适教授李澄清教授学院名称数学与计算科学学院学科专业数学研究方向信息处理二零一八年四月十日基于复杂网络的元胞自动机复杂度分类研究学位申请人徐成指导教师舒适教授李澄清教授学院名称数学与计算科学学院学科专业数学研究方向信息处理学位申请级别理学硕士学位授予单位湘潭大学论文提交日期2018–04–10ComplexityClassificationofCellularAutomataBasedonComplexNetworkAnalysisCandidateCh

2、engXuSupervisorProfessorShiShuSupervisorProfessorChengqingLiCollegeMathematicsandComputationalScienceProgramMathematicsSpecializationInformationProcessingDegreeMasterofScienceUniversityXiangtanUniversityDateApril10th,2018摘要元胞自动机是一类离散动力学系统，简单的结构单元通过局部相互作用产生了丰富的动力学行为。根据Wolfram分类，元胞自动机的演化行为归为四类：稳定型、

3、周期型、混沌型、复杂型。不同于以往定义复杂度和统计观测时空演化图的方法，将元胞自动机用状态空间网络描述，通过理论推导、实验仿真、定量分析来研究88条独立规则的状态空间网络的局部和全局性质，从而获得元胞自动机的复杂度分类。本文的主要工作和结论如下：1、分析了88条独立规则的状态空间网络的最大度关于网络规模的标度行为，数据分析结果显示，幂律指数与转移矩阵的谱有关，幂律指数不能作为区分元胞自动机的复杂度的指标。基于Kayama提出的一类网络，应用复杂网络来分析元胞自动机的规则空间。2、研究规则4的度与度分布的一些性质，推导和证明了规则4的度分布拟合方法和精确计算方法。分析了88条独立规则的状态

4、空间网络的路径多样性关于网络规模的标度行为。数据分析表明，除规则30、45、106、154以外，路径多样性?关于网络规模?呈现幂律分布，幂律一致的接近于0.9718。3、实验仿真和理论推导证明最大度与路径多样性不能作为元胞自动机的复杂度分类指标。提出表征状态空间网络的拓扑结构特征的两个中尺度量化指标：平均路径长度、平均吸引环周期，获得量化分类结果与Wolfram分类较为一致，可以作为Wolfram分类的补充。关键词:元胞自动机；状态空间网络；最大度；度分布；复杂网络；元胞自动机分类IAbstractCellularautomata(CA)isadiscretedynamicalsyste

5、mandabundantdynamicalbehaviorsareemergedfromitssimplercomponentsandinteractionlaws.AccordingtoWolframclassification,CArulescanbeclassifiedasstable,periodic,chaoticandcomplex.Inrecentyears,theriseofcomplexnetworkprovidesanewideafordescribingthecomplexrelationshipbetweenindividualsandmultipleindivi

6、duals.ToobtainthecomplexityclassificationofCA,wedescribeCAasastatespacenetwork(SSN)andstudythelocalandglobalpropertiesofnetworkthatcorrespondtothedynamicalbehaviorsofCAbytheoreticalderivations,experimentalsimulationsandquantitativeanalysis.Ourapproachapparentlyisdifferentfromthecommonmethodssucha

7、sthedefinitionsofcomplexityandstatisticalobservationsofspace-timeevolutionpatterns.Themainworkandconclusionsofthisthesisareasfollows:1.ThisthesisanalyzedthescalingbehaviorsofthemaximumdegreeofSSNsfor88independentrulesa