独立马氏链边随机图过程与随机分枝树研究
|
摘要
二十世纪五十年代末六十年代初，Erd s和Rényi创立了随机图理论，至此，随机图理论在近半个多世纪得到了迅速发展，并被广泛应用于自然科学和社会科学的各个研究领域。近十年来随着复杂网络研究热潮的兴起，随机图理论再一次引起了数学、物理、计算机、经济、生物、社会学等学科学者的关注，并取得了许多新的研究成果。本文主要对独立马氏链边随机图过程、随机分枝树进行研究，建立了两类随机图过程的数学模型，讨论了它们的图拓扑性质。主要工作如下：
1.对网络序列的极限、网络间的距离、可测图空间等一些基本概念和命题进行了梳理和讨论；借助经典随机过程理论中的概念及研究方法，探讨了贝努力随机图序列、平稳随机图过程、马氏随机图过程的概念和部分统计特性。
2.推导了独立马氏链边随机图过程的转移函数并证明了该过程的平稳性，得到了它的平稳分布；拓广了孤立节点的概念，引入了随机图过程的区间孤立节点；对以平稳分布为初始分布的独立同分布马氏链边随机图过程，给出了其孤立节点数的分布和不存在孤立节点的概率；讨论了该过程的连通性，得到了任意两个节点连通的概率，估计了随机图连通概率的下界，并证明当节点数充分大时，随机图是几乎处处连通的。
3.建立了出生率和死亡率与年龄段有关的随机分枝树模型；对出生率与年龄段有关的随机分枝树模型进行了特别研究：用两种不同的表达式给出了任一节点的1─代子节点总数的分布；引入了节点虚度的概念，证明了活着的（节点的度）和死亡的（节点的虚度）1─代子节点数的条件分布皆为Possion分布；得到了1─代子节点在某个时刻或时段全部死光或全部活着的概率；探讨了严格单调函数和随机终止Possion过程，证明了子节点计数过程是随机终止的Possion过程；得到了任一节点首生年龄的条件分布函数，证明了n个子节点相对出生年龄的顺序统计量同分布于n个均匀分布的独立随机变量的顺序统计量；引入了时段孤立节点的概念，给出了节点在某个时刻或时段为孤立节点的概率。
In the late of1950s and early of1960s, Erd s and Rényi established the theory ofrandom graph. The theory of random graph had a great development in the next halfcentury and widely applied in the areas of nature science and social science. In therecent years, because of the rasing of the research of the complex network, randomtheory draws much attentions of many researchers, such as mathematician, physicistand so on. Many new results of research are presented. In this dissertation, weresearch the edge-Markovian independent random graph processes and randombranching processes and give the mathematics models of random graph processes ofthese two classes and discuss their topological properties. We organize thisdissertation as follows:
1. Some basic concepts and propositions are sorted and discussed, such as the limitof network sequence, distance between networks, measurable graph space, and so on.By the concepts and methods of the classic random processes, the statistics propertiesof Bernoulli random graph sequence, stationary random graph processes and Markovrandom graph processes are discussed.
2. For edge-Markovian independent random graph processes, we derive thetransition probability function, prove its stability, obtain its stationary distribution;Wegeneralize the concept of isolated node and establish the isolated node of randomgraph process; When the initial distribution of the edge-Markovian independentrandom graph processes is stationary distribution, we give the distribution sequence ofthe number of isolated node, prove the probability of no isolated node;We discuss itsconnection,and obtain the probability of two nodes which are connected, estimate thelower bound of the connection probability for random graph and prove that therandom graph is almost connected everywhere if the number of node is infinite.
3. We establish the birth and death random branching tree model whose birth rateand death rate are dependent on the age period. In the model of birth rate which isdependent on the age period, we discuss the distribution of the total I-generationnode’s number by two difference expressions. We give the concept of node falsedegree,prove the distribution of living(node degree) and dead(node false degree)I-generation node’s number are the Possion distribution, and obtain the probabilities of all keeping alive or dead of I-generation node; We discuss the monotone functions,random terminate Possion processes, and prove the1-generation node countingprocess is the random terminate Possion processes.We obtain the conditionaldistribution function of a arbitrary node’s first birth age,prove that order statistic ofthe related of n nodes’ birth age is subject to order statistic of n independent randomvariable of uniformly distribution.We also give the concept of period isolated nodeand give the probabilities that node is a period isolated node at sometime or in someperiod.
1.对网络序列的极限、网络间的距离、可测图空间等一些基本概念和命题进行了梳理和讨论；借助经典随机过程理论中的概念及研究方法，探讨了贝努力随机图序列、平稳随机图过程、马氏随机图过程的概念和部分统计特性。
2.推导了独立马氏链边随机图过程的转移函数并证明了该过程的平稳性，得到了它的平稳分布；拓广了孤立节点的概念，引入了随机图过程的区间孤立节点；对以平稳分布为初始分布的独立同分布马氏链边随机图过程，给出了其孤立节点数的分布和不存在孤立节点的概率；讨论了该过程的连通性，得到了任意两个节点连通的概率，估计了随机图连通概率的下界，并证明当节点数充分大时，随机图是几乎处处连通的。
3.建立了出生率和死亡率与年龄段有关的随机分枝树模型；对出生率与年龄段有关的随机分枝树模型进行了特别研究：用两种不同的表达式给出了任一节点的1─代子节点总数的分布；引入了节点虚度的概念，证明了活着的（节点的度）和死亡的（节点的虚度）1─代子节点数的条件分布皆为Possion分布；得到了1─代子节点在某个时刻或时段全部死光或全部活着的概率；探讨了严格单调函数和随机终止Possion过程，证明了子节点计数过程是随机终止的Possion过程；得到了任一节点首生年龄的条件分布函数，证明了n个子节点相对出生年龄的顺序统计量同分布于n个均匀分布的独立随机变量的顺序统计量；引入了时段孤立节点的概念，给出了节点在某个时刻或时段为孤立节点的概率。
In the late of1950s and early of1960s, Erd s and Rényi established the theory ofrandom graph. The theory of random graph had a great development in the next halfcentury and widely applied in the areas of nature science and social science. In therecent years, because of the rasing of the research of the complex network, randomtheory draws much attentions of many researchers, such as mathematician, physicistand so on. Many new results of research are presented. In this dissertation, weresearch the edge-Markovian independent random graph processes and randombranching processes and give the mathematics models of random graph processes ofthese two classes and discuss their topological properties. We organize thisdissertation as follows:
1. Some basic concepts and propositions are sorted and discussed, such as the limitof network sequence, distance between networks, measurable graph space, and so on.By the concepts and methods of the classic random processes, the statistics propertiesof Bernoulli random graph sequence, stationary random graph processes and Markovrandom graph processes are discussed.
2. For edge-Markovian independent random graph processes, we derive thetransition probability function, prove its stability, obtain its stationary distribution;Wegeneralize the concept of isolated node and establish the isolated node of randomgraph process; When the initial distribution of the edge-Markovian independentrandom graph processes is stationary distribution, we give the distribution sequence ofthe number of isolated node, prove the probability of no isolated node;We discuss itsconnection,and obtain the probability of two nodes which are connected, estimate thelower bound of the connection probability for random graph and prove that therandom graph is almost connected everywhere if the number of node is infinite.
3. We establish the birth and death random branching tree model whose birth rateand death rate are dependent on the age period. In the model of birth rate which isdependent on the age period, we discuss the distribution of the total I-generationnode’s number by two difference expressions. We give the concept of node falsedegree,prove the distribution of living(node degree) and dead(node false degree)I-generation node’s number are the Possion distribution, and obtain the probabilities of all keeping alive or dead of I-generation node; We discuss the monotone functions,random terminate Possion processes, and prove the1-generation node countingprocess is the random terminate Possion processes.We obtain the conditionaldistribution function of a arbitrary node’s first birth age,prove that order statistic ofthe related of n nodes’ birth age is subject to order statistic of n independent randomvariable of uniformly distribution.We also give the concept of period isolated nodeand give the probabilities that node is a period isolated node at sometime or in someperiod.
引文
[1]Erd s P., Rényi A..On the Strength of Connectedness of a Random Graph [J]. ActaMathematica Scientia Hungary1961,12,261-267.
[2]Erd s P., Rényi A.. On the Evolution of Random Graphs [J]. Publications of theMathematical Institute of the Hungarian Academy of Sciences1960,5:17-61.
[3]Erd s P., Rényi A.. On the Evolution of Random Graphs [J]. Bull. Inst. Internat. Statist.1961,38:343-347.
[4]Bollobasi B.Random Graphs[M].New York:Academic Press,2001.
[5]Hoeffding W. Probability Inequalities for Sums of Bounded Random Variables [J]. J.Amer.Statist. Assoc.,1963,58:13-30.
[6]Jodan J. The Degree Sequences and Spectra of Scale-free Random Graph [J]. RandomStructures and Algorithms,2006,29:226-242.
[7]Birmelé E.A Scale-free Graph Model Based on Bipartite Graphs [J].Discrete AppliedMathematics,2008,doi:10.1016.
[8]Cao Y. The Degree Distribution of Random k-trees [J]. Theoretical Computer Science,2009,410:688-695.
[9]Faloutsos M., Faloutsos P., Faloutsos C..On Power-law Relationships of the InternetTopology [J]. Com-puter Communications Review1999,29:251-262.
[10]Yanqing Wang,Fuqing Gao.Deviation Inequality for the Number of K-cycles in a RandomGraph [J]. Wu Han: Wuhan University Journal of Natural Sciences,2009,4(1):11-13.
[11]Erd s P., Rényi A.,On Random Graphs [J]. Publicationes Mathematicae Debrecen,1959,5:290-297.
[12]West D B. Introduction to Graph Theory[M].NJ:Prentice Hall,2001.
[13]Avin C., Ercal G..On the Cover Time and Mixing Time of Random Geometricgraphs[J].Theoretical Computer Science,2007,380:2-22.
[14]Aldous D.J., Fill J.A, Reversible Markov Chains and Random Walks on Graphs,toappear,2002http://stat2www.berkeley. edu/users/aldous/book/html/. MathematicaScientia Hungary12,261-267(1961).
[15]Buffet E,Pule J V.Polymers and Random Graphs[J]. J. Stat. Phya.,1991,64(1/2):87-110.
[16]Wang Hanxing,Ma Chi.The Evolution about a Kind of Random Graph[J].ORTransactions,2006,10(1):55-60.
[17]Han Dong. The Stationary Distribution of a Continuous-time Random Graph Process withInteracting Edges [J]. Acta Mathematics Scientia.1994,14:98-102.
[18]Aiello W., Chung F., Lu L., A Random Graph Model for Massive Graphs, in Proceedingsof the32nd Annual ACM Symposium on Theory of Computing,171-180, Association ofComputing Machinery, New York (2000).
[19]Ferreira A, Jarry A.Complexity of Minimum Spanning Tree in Evolving Graphs and theMinimum-enerage Broadcast Routing Problem[C]//Proc. of WIOPT`04.Cambridge,UK:[s. n.],2004.
[20]Jarry A, Lotker A.Connectivity in Evolving Graphs with Geometric Propertier.[C]//Proc.of DIALM-POMC`04.Philedelphia,USA:[s. n.],2004:24-30.
[21]Aleliunas R., Karp R.M., Lipton R.J., Lov′asz L., RackoC..Random Walks,UniversalTraversal Sequences, and the Complexity of Maze Problems. Proceed-ings of the20th AnnualIEEE Symposium on Foundations of Computer Science,1979:218-223.
[22]Clementi A E F,Macci C,Monnti M,et al.Flooding Time in Edge-Markovian DynamicGraphs[C]//Proc. of the27th ACM Symp. On Principles of Distributed Computing. Toronto,Canada:[s. n.]2008:213-222.
[23]Hervé B, Pierluigi C,Pierre F.Parsimonious Flooding in Dynamic Graphs[C]//Proc. of the28th ACM Symp. On Principles of Distributed Computing.Calgary, USA:ACMPress,2009:260-269.
[24]Feige U..A Tight Upper Bound for the Cover Time of Random Walks on Graphs [J].Random Structures Algorithms,1995,6:51–54.
[25]颜云志,王汉兴.关于有向无标度图的一个推广模型[J].运筹学学报,2011,15(1):35–45.
[26]颜云志,王汉兴.一类幂律图模型[J].上海交通大学学报,2009,43(8):1347–1356.
[27]覃森,戴冠中,王林.具有边连接增长速度的演化网络度分布研究[J].系统工程理论与实践2007,11:159-163.
[28]Cooper C., Frieze A..A General Model of Undirected Web Graphs[J].Random Structuresand Algorithms,2003,22:311-335.
[29]周涛,徐俊明,刘隽.图直径与平均距离的极值问题研究[J].中国科技大学学报,2004,34(4):410-413.
[30] Bollobás B, Riordan O, Spencer J, Tusnády G. The Degree Sequence of a Scale-freeRandom Graph Process [J]. Random Structures and Algorithms,2001,18:279-290.
[31] Barabási A L.Linked:The New Science of Networks Massachusotts:Persus Publishing,2002.
[32]Watts D J.The "new" Science of Networks.Annual Review of Sociology,2004,30:243-270.
[33]Guillaume J L, Latapy M. Bipartite Structure of all Complex networks[J].InformationProcessing Letters,2004,90:215-221.
[34]Tan L, Liu X R. The Stability Analysis of Random Growing Networks[J].Journal of HebeiUniversity of Technology,2010.39:17-19.
[35]Liu Z H, Lai Y C, Ye N, Dasgupta P. Connective Distribution and Attack Tolerance ofGeneral Networks with Both Preferential and Random Attachments [J]. Phy. Lett. A,2002,303:337-344.
[36]Reka Zsuzsanna Albert. Statistical Mechanics of Complex Networks[D].Department ofPhysics Notre Dame2001.
[37]Watts D. J., Strogatz S. H.. Collective dynamics of ‘Small-world’ Networks [J].Nature.1998,393:440-442.
[38]Newman M.E.J., Watts D.J.. Renormalization Group Analysis of the Small-worldNetwork Model [J]. Physics Letters A,1999,263:341-346.
[39]Barabási A.L, Albert R..Emergence of Scaling in Random Networks [J]. Science,1999,286:509-512.
[40]Barabási A., Albert R., Jeong H..Mean-field Theory for Scale-free Random Networks[J].Physica A,1999,272:173-187.
[41]Albert R, Barabási A.L...Topology of Evolving Networks:Local Events and Uiversality[J]. Phys Rev Lett,2000,85:5234-5237.
[42]Barabási A L,Ravasz E,Vicsek T. Deterministic Scale-free Networks[J].PhysicaA,2001,299:559-564.
[43]Francesc Comellas,Michael Sampels. Deterministic Small-world Networks[J].Physica A,2002,309:231-235.
[44] Fan Z P,Chen G R.Evolving Networks:from Topology to Dynamics[J].Journal of ControlTheory and Application,2004,2:60-64.
[45]Wang X F.Complex Networks: Topology,Dynamics and Synchronization[J].Int J ofBifurcation and Chaos,2002,5(12):885-916.
[46]Krapivsky P L, Redner S, Leyvraz F.Connectivity of Growing Random Networks[J]. PhysRev Lett,2000,85:4629-4632.
[47]Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of Growing Networks withPreferential Linking [J]. Phys Rev Lett.2000,85:4633-4636.
[48]Newman M E J.Assortative mixing in networks[J]. Phys Rev Lett.2002,89:208701.
[49]Liu Z H, Lai Y C, Ye N, Dasgupta P. Connective Distribution and Attack Tolerance ofGeneral Networks with Both Preferential and Random Attachments [J]. Phy. Lett. A,2002,303:337-344.
[50]Jespersen S., Sokolov I.M., Blumen A.. Relaxation Properties of Small-world Networks[J]. Phys. Rev. E2000,62,4405–4408.
[51]C.Avin,M.Koucky,Z.Lotker.How to Explore a Fast-Changing World.In Proceedings of the35th International Colloquium on Automata,Languages and Programming,2008,Springer:121-132.
[52]Albert R., Jeong H., Barabási A.L..Attack and Error Tolerance of Complex Net-works [J].Nature,2000,406:378-382.
[53]Fall K. A Delay-tolerent Network Architecture for Chanllenged Internets[C]//Proc. OfACM SIGCOMM`03.Karlsruhe, Germany:[s. n.],2003.
[54]Macarthur B D,Sanchez-Garcia R J,Anderson J W.Symmetry in Complex Networks.http://lanl.arxiv.org/abs/0705.3215v2,2007.
[55]Albert R., Barabási A..Statistical Mechanics of Complex Networks [J]. Rev. Mod.Phys.2002,74:47-97.
[56]Adamic L.A., Lukose R.M.. Puniyani A.R., et al. Search in Power-law Networks.Phys [J].Rev. E,2001,64:046135.
[57]Monteiro J, Goldman A,Ferreira A.Performance Evaluation of Dynamic Networks Usingan Evolving Graph Combinatorial Model [C]//Proc. of WIMOB`06,Montreal USA:[s. n.],2006;173-180.
[58]Krapivsky P L, Redner S.Organization of Growing Random Networks[J]. Phys Rev Lett,2001,63:066123
[59]Albet R, Jeong H, Barabási A L. Diameter of the World-Wide Web[J]. Nature,1999,401:130-131.
[60]郑中团.基于随机图演化与图上随机游动的复杂网络研究[D].上海大学博士学位论文2009.
[61]颜云志,.有向无标度图与二项随机图图因子[D],上海大学博士学位论文2007.
[62]Pandit S.A., Amritkar R.E. Random Spread on the Family of Small World Networks [J].Phys. Rev. E63,041104(2001).
[63]Drinea E., Enachescu M., Mitzenmacher M..Variations on Random Graph Models for theWeb.Technical Report, Harvard University, Department of Computer Science,2001.
[64]Wang Shaoping,Pei Wenjiang.First Passage Time of Multiple Brownian Particles onNetworks with Applications[J].Physica A.2008,387:4699–4708.
[65]Bollob′as B., Riordan O..The Diameter of a Scale-free Random Graph.Preprint[J],Department of Mathematical Sciences, University of Memphis,2002.
[66]Barab′asi A.L., Albert R., Jeong H..Scale-free Characteristics of Random Networks: TheTopology of the World Wide Web[J].Physica A,2000,281:69-77.
[67]Dorogovtsev S. N., Mendes J. F. F., and Samukhin, A. N..Metric Structure of RandomNetworks. Preprint cond-mat/0210085(2002).
[68]Merugu S, Ammar M, Zegura E. Routing in Space and Time in Networks withPredictable Mobility [R]. Georgia Institute of Technology.Tech. Rep.: IRB-TR-04-020,2004.
[69]蔡青松,牛建伟.基于边独立演化的机会网络时间演化图模型[J].计算机工程,2011,37(15):17-22.
[70]杜彩凤.随机网络的马氏链模型[J].科学技术与工程.2010,10(30):7380-7383.
[71]胡西.移动自组网络网络中若干问题的建模与分析[D].上海大学博士学位论文2007.
[72]王汉兴,马驰.一类随机图的演化[J].运筹学学报.2006,3,10[1]:55-60.
[73]David M.Hull.A Reconsideration of Galton’s Problem (Using a Two-sex Population)[J].Theoretical Population Biology,1998,54:1051-1061.
[74]Harris T E. Branching Processes[M].Berlin:Springer,1963.
[75]Bellman,R.T.E.Harris.On Age-dependent Binary Branching Process[J].Ann. of Math.,1952,55:280-295.
[76]Athreya,K.B.On the Supercritical One Dimensional Age Dependent Branching Process[J].Ann. Math.Statist.,1969,40:743-763.
[77]Cohn H. On the Growth of the Multitype Supercrical Branching Processes in a RandomEnvironments [J]. Ann Probab,1989,17:1118-1123.
[78]Geoff Wild. Inclusive Fitness from Multitype Branching Process [J].Bull Math Biol.2011,73:1028-1051.
[79]Esty,W.W.Critical Age Dependent Branching Process[J].Ann.Prob.,1975,3:49-60.
[80]Cohn,H.Norming constants for the Finite Mean Supercritical Bellman-HarrisProcess[J].Z.Wahrscheinlichkeitstheorieverw.Geb.,1982,61:189-205.
[81]Yingqiu Li, Quansheng Liu. Age-dependent Branching Processes in RandomEnvironments[J]. Science in China series A:Mathematics,2008,51(10).
[82]李应求,刘全升.随机环境中依赖年龄的分枝过程[J].中国科学(A辑,数学),2008,7(38):799-818.
[83]李应求.随机环境中依赖年龄分枝过程的爆炸问题[J].数学学报(中文版).2010,53(5):1027-1034.
[84]Gonzalez,M.,Molina,M.,Mota,M..Limit Behabiour for a Subcritical BisexualGalton-Watson Branching Process with Immigration[J].Statist. Probab.Lett.2000,49:19-24.
[85]Delay,D.J..Extinction Conditions for Certain Bisexual Galton-Watson Branching Process[J].Z.Wahrscheinlichkeitsth,1968,9:315-322.
[86]Ma Shixia, Wang Yongjin. On the Limit Behavior of the Population-Size-DependentBisexual Branching Processes[J]. Chinese Journal of Applied Probability and Statistics.2007,23(4):352-360.
[87]Klebaner,F. C..Geometric Rate of Growth in Population-Size-Dependent BranchingProcesses[J].J. Appl. Prob.,1984,21:40-49.
[88]SmithW.L.,WilkinsonW.E..On Branching Processes in Random Environments[J].Ann.Math.Statist,1969,40:814-827.
[89]Smith,W.L.,Wilkinson,W.E.. Branching Processes in Markovian Environments[J]. DuckMath. J.,1971,38:749-763.
[90]Athereya K B,Karlin S.On Branching Processes with Random Environments:I ExtinctionProbabilities [J].Ann Math Statist.1971,42(5):1499-1520.
[91]Athereya K B,Karlin S.On Branching Processes with Random Environments:II LimitTheorems[J].Ann Math Statist.1971,42:1843-1858.
[92]Molina,M.,Mota,M.,Ramos,A..Bisexual Galton-Watson Branching Process withPopulation-size Dependent Mating[J].J. Appl.Probab.2002,39:479-490.
[93]王汉兴.平稳随机环境中的P-S-D分枝模型[J].自然杂志,1997.
[94]Xing,Y.S.,Wang,T.J..On the Extinction of one Class of Population-Size-DependentBisexual Branching Processes[J].J. Appl. Prob.,2005,42:174-185.
[95]Chen A.Li J.Zhang H. Uniqueness and Extinction Properties of Interacting BranchingCollision Processes.2009,substract.
[96]Chen A Y,Li J P,Ramesh N I. Uniqueness and Extinction of Weighted Markov BranchingProcess[J].Meth. and Comp. Appl. Prob.,2005,7:489-516.
[97]王汉兴.随机环境中的分枝游动[J].应用概率统计,1997,13(3):259-263.
[98]王汉兴.随机环境中的多物种分枝游动[J].应用概率统计,1997,13(2):165-170.
[99]Nagaev,S.V., Vakhtel,V.I.. On the Local Limit Theorem for Critical Galton-WatsonProcesses [J]. Theor. Probab..2006,50:400-419.
[100]Patsy Haccou, Peter Jagers,Vladimir A. Vatutin. Branching Processes Variation,Growth,and Extinction of Populations[M]. Cambridge: Cambridge University Press,2005.
[101]方大凡,王汉兴.独立平稳随机环境中的P-S-D分枝过程[J].应用概率统计,1999,15(4):345-350.
[102]Spouge J L.Polyers and Random Graphs:Asymptotic, Equivalence to BranchingProcesses[J].J. Stat. Phya.,1985,38(3/4):573-587.
[103]Chen M F. From Markov Chains to Non-Equilibrium Particle Systems [M]. Singapore:World Scientific,1992.
[104]Good I. J.. The Number of Individuals in a Cascade Process [J]. Proc. Camb. Phil.Soc.,1949,45:360-363.
[105]Athreya K B and Ney P E. Branching Processes [M].Berlin: Springer Verlag,1972.
[106]Jages P.,Lu Zhunwei. Branching Processes with Deteriorating Random Environments[J].J. Appl. Prob.,2002,39(2):395-401.
[107]Wang Hanxing, Zhao Fei, Lu Jinyu. A Note on Asymptotic Behavior of Galton-WatsonBranching Processes in Random Environments [J].Journal of Shanghai University (EnglishEdition),2006,10(2):95-99.
[108]Wang Hanxing. On Extinction Probabilities for Markov Chains in Independent RandomEnvironments[J].Acta. Sci. Nat. Univ. Normal, Hunan.1997,20(2):22-25.(in Chinese)
[109]王汉兴,方大凡.有限状态马氏环境中的随机环境中的P-S-D分枝过程[J].自然杂志,1998,20(5):300-301.
[110]Zhao Lihua,Lei Enlin,Lu Zhunwei,Liu Guifen.The Asymptotic Behaviour of theExtinction Probability in Bisexual Galton-Watson Branching Processes with Independent andIndentically Distributed Random Environments[J].Chinese Journal of Applied Probability andStatistics,2011,27(13):289-296.
[111]Chen A Y,Li J P,Ramesh N I. Uniqueness and Extinction of Weighted Markov BranchingProcess[J].Meth. and Comp. Appl. Prob.,2005,7:489-516.
[112]Wang Jun, Li Junping. Uniqueness and Extinction Properties of Branching-collisionProcesses. Mathematical Theory and Applications.2009,29(3),16-20.
[113]Smith W L. Necessary Conditions forAlmost Sure Extinction of a Branching Processwith Random Environment [J]. Ann.Math. Statist.1968,39:2136-2140.
[114]汪小帆,李翔,陈关荣.复杂网络:理论与应用[M].北京:北京清华大学出版社,2006.
[115]方锦清等.一门崭新的交叉科学:网络科学[J].物理学进展,2007,27(3).
[116]陈关荣.复杂网络及其新近研究进展介绍[J].力学进展,2008,38(25):653-660.
[117]吴金闪,狄增如.从统计物理学看复杂网络研究[J].物理学进展,2004,24(1):18-46.
[118]钟开莱著.吴让泉译.概率论教程[M].上海:上海科技出版社,1989.
[119]严士健,王隽骧,刘秀芳.概率论基础[M].科学出版社,1982.
[120]何声武.随机过程引论[M].高等教育出版社,1999.
[121]刘次华.随机过程[M].华中科技大学出版社,2004.
[2]Erd s P., Rényi A.. On the Evolution of Random Graphs [J]. Publications of theMathematical Institute of the Hungarian Academy of Sciences1960,5:17-61.
[3]Erd s P., Rényi A.. On the Evolution of Random Graphs [J]. Bull. Inst. Internat. Statist.1961,38:343-347.
[4]Bollobasi B.Random Graphs[M].New York:Academic Press,2001.
[5]Hoeffding W. Probability Inequalities for Sums of Bounded Random Variables [J]. J.Amer.Statist. Assoc.,1963,58:13-30.
[6]Jodan J. The Degree Sequences and Spectra of Scale-free Random Graph [J]. RandomStructures and Algorithms,2006,29:226-242.
[7]Birmelé E.A Scale-free Graph Model Based on Bipartite Graphs [J].Discrete AppliedMathematics,2008,doi:10.1016.
[8]Cao Y. The Degree Distribution of Random k-trees [J]. Theoretical Computer Science,2009,410:688-695.
[9]Faloutsos M., Faloutsos P., Faloutsos C..On Power-law Relationships of the InternetTopology [J]. Com-puter Communications Review1999,29:251-262.
[10]Yanqing Wang,Fuqing Gao.Deviation Inequality for the Number of K-cycles in a RandomGraph [J]. Wu Han: Wuhan University Journal of Natural Sciences,2009,4(1):11-13.
[11]Erd s P., Rényi A.,On Random Graphs [J]. Publicationes Mathematicae Debrecen,1959,5:290-297.
[12]West D B. Introduction to Graph Theory[M].NJ:Prentice Hall,2001.
[13]Avin C., Ercal G..On the Cover Time and Mixing Time of Random Geometricgraphs[J].Theoretical Computer Science,2007,380:2-22.
[14]Aldous D.J., Fill J.A, Reversible Markov Chains and Random Walks on Graphs,toappear,2002http://stat2www.berkeley. edu/users/aldous/book/html/. MathematicaScientia Hungary12,261-267(1961).
[15]Buffet E,Pule J V.Polymers and Random Graphs[J]. J. Stat. Phya.,1991,64(1/2):87-110.
[16]Wang Hanxing,Ma Chi.The Evolution about a Kind of Random Graph[J].ORTransactions,2006,10(1):55-60.
[17]Han Dong. The Stationary Distribution of a Continuous-time Random Graph Process withInteracting Edges [J]. Acta Mathematics Scientia.1994,14:98-102.
[18]Aiello W., Chung F., Lu L., A Random Graph Model for Massive Graphs, in Proceedingsof the32nd Annual ACM Symposium on Theory of Computing,171-180, Association ofComputing Machinery, New York (2000).
[19]Ferreira A, Jarry A.Complexity of Minimum Spanning Tree in Evolving Graphs and theMinimum-enerage Broadcast Routing Problem[C]//Proc. of WIOPT`04.Cambridge,UK:[s. n.],2004.
[20]Jarry A, Lotker A.Connectivity in Evolving Graphs with Geometric Propertier.[C]//Proc.of DIALM-POMC`04.Philedelphia,USA:[s. n.],2004:24-30.
[21]Aleliunas R., Karp R.M., Lipton R.J., Lov′asz L., RackoC..Random Walks,UniversalTraversal Sequences, and the Complexity of Maze Problems. Proceed-ings of the20th AnnualIEEE Symposium on Foundations of Computer Science,1979:218-223.
[22]Clementi A E F,Macci C,Monnti M,et al.Flooding Time in Edge-Markovian DynamicGraphs[C]//Proc. of the27th ACM Symp. On Principles of Distributed Computing. Toronto,Canada:[s. n.]2008:213-222.
[23]Hervé B, Pierluigi C,Pierre F.Parsimonious Flooding in Dynamic Graphs[C]//Proc. of the28th ACM Symp. On Principles of Distributed Computing.Calgary, USA:ACMPress,2009:260-269.
[24]Feige U..A Tight Upper Bound for the Cover Time of Random Walks on Graphs [J].Random Structures Algorithms,1995,6:51–54.
[25]颜云志,王汉兴.关于有向无标度图的一个推广模型[J].运筹学学报,2011,15(1):35–45.
[26]颜云志,王汉兴.一类幂律图模型[J].上海交通大学学报,2009,43(8):1347–1356.
[27]覃森,戴冠中,王林.具有边连接增长速度的演化网络度分布研究[J].系统工程理论与实践2007,11:159-163.
[28]Cooper C., Frieze A..A General Model of Undirected Web Graphs[J].Random Structuresand Algorithms,2003,22:311-335.
[29]周涛,徐俊明,刘隽.图直径与平均距离的极值问题研究[J].中国科技大学学报,2004,34(4):410-413.
[30] Bollobás B, Riordan O, Spencer J, Tusnády G. The Degree Sequence of a Scale-freeRandom Graph Process [J]. Random Structures and Algorithms,2001,18:279-290.
[31] Barabási A L.Linked:The New Science of Networks Massachusotts:Persus Publishing,2002.
[32]Watts D J.The "new" Science of Networks.Annual Review of Sociology,2004,30:243-270.
[33]Guillaume J L, Latapy M. Bipartite Structure of all Complex networks[J].InformationProcessing Letters,2004,90:215-221.
[34]Tan L, Liu X R. The Stability Analysis of Random Growing Networks[J].Journal of HebeiUniversity of Technology,2010.39:17-19.
[35]Liu Z H, Lai Y C, Ye N, Dasgupta P. Connective Distribution and Attack Tolerance ofGeneral Networks with Both Preferential and Random Attachments [J]. Phy. Lett. A,2002,303:337-344.
[36]Reka Zsuzsanna Albert. Statistical Mechanics of Complex Networks[D].Department ofPhysics Notre Dame2001.
[37]Watts D. J., Strogatz S. H.. Collective dynamics of ‘Small-world’ Networks [J].Nature.1998,393:440-442.
[38]Newman M.E.J., Watts D.J.. Renormalization Group Analysis of the Small-worldNetwork Model [J]. Physics Letters A,1999,263:341-346.
[39]Barabási A.L, Albert R..Emergence of Scaling in Random Networks [J]. Science,1999,286:509-512.
[40]Barabási A., Albert R., Jeong H..Mean-field Theory for Scale-free Random Networks[J].Physica A,1999,272:173-187.
[41]Albert R, Barabási A.L...Topology of Evolving Networks:Local Events and Uiversality[J]. Phys Rev Lett,2000,85:5234-5237.
[42]Barabási A L,Ravasz E,Vicsek T. Deterministic Scale-free Networks[J].PhysicaA,2001,299:559-564.
[43]Francesc Comellas,Michael Sampels. Deterministic Small-world Networks[J].Physica A,2002,309:231-235.
[44] Fan Z P,Chen G R.Evolving Networks:from Topology to Dynamics[J].Journal of ControlTheory and Application,2004,2:60-64.
[45]Wang X F.Complex Networks: Topology,Dynamics and Synchronization[J].Int J ofBifurcation and Chaos,2002,5(12):885-916.
[46]Krapivsky P L, Redner S, Leyvraz F.Connectivity of Growing Random Networks[J]. PhysRev Lett,2000,85:4629-4632.
[47]Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of Growing Networks withPreferential Linking [J]. Phys Rev Lett.2000,85:4633-4636.
[48]Newman M E J.Assortative mixing in networks[J]. Phys Rev Lett.2002,89:208701.
[49]Liu Z H, Lai Y C, Ye N, Dasgupta P. Connective Distribution and Attack Tolerance ofGeneral Networks with Both Preferential and Random Attachments [J]. Phy. Lett. A,2002,303:337-344.
[50]Jespersen S., Sokolov I.M., Blumen A.. Relaxation Properties of Small-world Networks[J]. Phys. Rev. E2000,62,4405–4408.
[51]C.Avin,M.Koucky,Z.Lotker.How to Explore a Fast-Changing World.In Proceedings of the35th International Colloquium on Automata,Languages and Programming,2008,Springer:121-132.
[52]Albert R., Jeong H., Barabási A.L..Attack and Error Tolerance of Complex Net-works [J].Nature,2000,406:378-382.
[53]Fall K. A Delay-tolerent Network Architecture for Chanllenged Internets[C]//Proc. OfACM SIGCOMM`03.Karlsruhe, Germany:[s. n.],2003.
[54]Macarthur B D,Sanchez-Garcia R J,Anderson J W.Symmetry in Complex Networks.http://lanl.arxiv.org/abs/0705.3215v2,2007.
[55]Albert R., Barabási A..Statistical Mechanics of Complex Networks [J]. Rev. Mod.Phys.2002,74:47-97.
[56]Adamic L.A., Lukose R.M.. Puniyani A.R., et al. Search in Power-law Networks.Phys [J].Rev. E,2001,64:046135.
[57]Monteiro J, Goldman A,Ferreira A.Performance Evaluation of Dynamic Networks Usingan Evolving Graph Combinatorial Model [C]//Proc. of WIMOB`06,Montreal USA:[s. n.],2006;173-180.
[58]Krapivsky P L, Redner S.Organization of Growing Random Networks[J]. Phys Rev Lett,2001,63:066123
[59]Albet R, Jeong H, Barabási A L. Diameter of the World-Wide Web[J]. Nature,1999,401:130-131.
[60]郑中团.基于随机图演化与图上随机游动的复杂网络研究[D].上海大学博士学位论文2009.
[61]颜云志,.有向无标度图与二项随机图图因子[D],上海大学博士学位论文2007.
[62]Pandit S.A., Amritkar R.E. Random Spread on the Family of Small World Networks [J].Phys. Rev. E63,041104(2001).
[63]Drinea E., Enachescu M., Mitzenmacher M..Variations on Random Graph Models for theWeb.Technical Report, Harvard University, Department of Computer Science,2001.
[64]Wang Shaoping,Pei Wenjiang.First Passage Time of Multiple Brownian Particles onNetworks with Applications[J].Physica A.2008,387:4699–4708.
[65]Bollob′as B., Riordan O..The Diameter of a Scale-free Random Graph.Preprint[J],Department of Mathematical Sciences, University of Memphis,2002.
[66]Barab′asi A.L., Albert R., Jeong H..Scale-free Characteristics of Random Networks: TheTopology of the World Wide Web[J].Physica A,2000,281:69-77.
[67]Dorogovtsev S. N., Mendes J. F. F., and Samukhin, A. N..Metric Structure of RandomNetworks. Preprint cond-mat/0210085(2002).
[68]Merugu S, Ammar M, Zegura E. Routing in Space and Time in Networks withPredictable Mobility [R]. Georgia Institute of Technology.Tech. Rep.: IRB-TR-04-020,2004.
[69]蔡青松,牛建伟.基于边独立演化的机会网络时间演化图模型[J].计算机工程,2011,37(15):17-22.
[70]杜彩凤.随机网络的马氏链模型[J].科学技术与工程.2010,10(30):7380-7383.
[71]胡西.移动自组网络网络中若干问题的建模与分析[D].上海大学博士学位论文2007.
[72]王汉兴,马驰.一类随机图的演化[J].运筹学学报.2006,3,10[1]:55-60.
[73]David M.Hull.A Reconsideration of Galton’s Problem (Using a Two-sex Population)[J].Theoretical Population Biology,1998,54:1051-1061.
[74]Harris T E. Branching Processes[M].Berlin:Springer,1963.
[75]Bellman,R.T.E.Harris.On Age-dependent Binary Branching Process[J].Ann. of Math.,1952,55:280-295.
[76]Athreya,K.B.On the Supercritical One Dimensional Age Dependent Branching Process[J].Ann. Math.Statist.,1969,40:743-763.
[77]Cohn H. On the Growth of the Multitype Supercrical Branching Processes in a RandomEnvironments [J]. Ann Probab,1989,17:1118-1123.
[78]Geoff Wild. Inclusive Fitness from Multitype Branching Process [J].Bull Math Biol.2011,73:1028-1051.
[79]Esty,W.W.Critical Age Dependent Branching Process[J].Ann.Prob.,1975,3:49-60.
[80]Cohn,H.Norming constants for the Finite Mean Supercritical Bellman-HarrisProcess[J].Z.Wahrscheinlichkeitstheorieverw.Geb.,1982,61:189-205.
[81]Yingqiu Li, Quansheng Liu. Age-dependent Branching Processes in RandomEnvironments[J]. Science in China series A:Mathematics,2008,51(10).
[82]李应求,刘全升.随机环境中依赖年龄的分枝过程[J].中国科学(A辑,数学),2008,7(38):799-818.
[83]李应求.随机环境中依赖年龄分枝过程的爆炸问题[J].数学学报(中文版).2010,53(5):1027-1034.
[84]Gonzalez,M.,Molina,M.,Mota,M..Limit Behabiour for a Subcritical BisexualGalton-Watson Branching Process with Immigration[J].Statist. Probab.Lett.2000,49:19-24.
[85]Delay,D.J..Extinction Conditions for Certain Bisexual Galton-Watson Branching Process[J].Z.Wahrscheinlichkeitsth,1968,9:315-322.
[86]Ma Shixia, Wang Yongjin. On the Limit Behavior of the Population-Size-DependentBisexual Branching Processes[J]. Chinese Journal of Applied Probability and Statistics.2007,23(4):352-360.
[87]Klebaner,F. C..Geometric Rate of Growth in Population-Size-Dependent BranchingProcesses[J].J. Appl. Prob.,1984,21:40-49.
[88]SmithW.L.,WilkinsonW.E..On Branching Processes in Random Environments[J].Ann.Math.Statist,1969,40:814-827.
[89]Smith,W.L.,Wilkinson,W.E.. Branching Processes in Markovian Environments[J]. DuckMath. J.,1971,38:749-763.
[90]Athereya K B,Karlin S.On Branching Processes with Random Environments:I ExtinctionProbabilities [J].Ann Math Statist.1971,42(5):1499-1520.
[91]Athereya K B,Karlin S.On Branching Processes with Random Environments:II LimitTheorems[J].Ann Math Statist.1971,42:1843-1858.
[92]Molina,M.,Mota,M.,Ramos,A..Bisexual Galton-Watson Branching Process withPopulation-size Dependent Mating[J].J. Appl.Probab.2002,39:479-490.
[93]王汉兴.平稳随机环境中的P-S-D分枝模型[J].自然杂志,1997.
[94]Xing,Y.S.,Wang,T.J..On the Extinction of one Class of Population-Size-DependentBisexual Branching Processes[J].J. Appl. Prob.,2005,42:174-185.
[95]Chen A.Li J.Zhang H. Uniqueness and Extinction Properties of Interacting BranchingCollision Processes.2009,substract.
[96]Chen A Y,Li J P,Ramesh N I. Uniqueness and Extinction of Weighted Markov BranchingProcess[J].Meth. and Comp. Appl. Prob.,2005,7:489-516.
[97]王汉兴.随机环境中的分枝游动[J].应用概率统计,1997,13(3):259-263.
[98]王汉兴.随机环境中的多物种分枝游动[J].应用概率统计,1997,13(2):165-170.
[99]Nagaev,S.V., Vakhtel,V.I.. On the Local Limit Theorem for Critical Galton-WatsonProcesses [J]. Theor. Probab..2006,50:400-419.
[100]Patsy Haccou, Peter Jagers,Vladimir A. Vatutin. Branching Processes Variation,Growth,and Extinction of Populations[M]. Cambridge: Cambridge University Press,2005.
[101]方大凡,王汉兴.独立平稳随机环境中的P-S-D分枝过程[J].应用概率统计,1999,15(4):345-350.
[102]Spouge J L.Polyers and Random Graphs:Asymptotic, Equivalence to BranchingProcesses[J].J. Stat. Phya.,1985,38(3/4):573-587.
[103]Chen M F. From Markov Chains to Non-Equilibrium Particle Systems [M]. Singapore:World Scientific,1992.
[104]Good I. J.. The Number of Individuals in a Cascade Process [J]. Proc. Camb. Phil.Soc.,1949,45:360-363.
[105]Athreya K B and Ney P E. Branching Processes [M].Berlin: Springer Verlag,1972.
[106]Jages P.,Lu Zhunwei. Branching Processes with Deteriorating Random Environments[J].J. Appl. Prob.,2002,39(2):395-401.
[107]Wang Hanxing, Zhao Fei, Lu Jinyu. A Note on Asymptotic Behavior of Galton-WatsonBranching Processes in Random Environments [J].Journal of Shanghai University (EnglishEdition),2006,10(2):95-99.
[108]Wang Hanxing. On Extinction Probabilities for Markov Chains in Independent RandomEnvironments[J].Acta. Sci. Nat. Univ. Normal, Hunan.1997,20(2):22-25.(in Chinese)
[109]王汉兴,方大凡.有限状态马氏环境中的随机环境中的P-S-D分枝过程[J].自然杂志,1998,20(5):300-301.
[110]Zhao Lihua,Lei Enlin,Lu Zhunwei,Liu Guifen.The Asymptotic Behaviour of theExtinction Probability in Bisexual Galton-Watson Branching Processes with Independent andIndentically Distributed Random Environments[J].Chinese Journal of Applied Probability andStatistics,2011,27(13):289-296.
[111]Chen A Y,Li J P,Ramesh N I. Uniqueness and Extinction of Weighted Markov BranchingProcess[J].Meth. and Comp. Appl. Prob.,2005,7:489-516.
[112]Wang Jun, Li Junping. Uniqueness and Extinction Properties of Branching-collisionProcesses. Mathematical Theory and Applications.2009,29(3),16-20.
[113]Smith W L. Necessary Conditions forAlmost Sure Extinction of a Branching Processwith Random Environment [J]. Ann.Math. Statist.1968,39:2136-2140.
[114]汪小帆,李翔,陈关荣.复杂网络:理论与应用[M].北京:北京清华大学出版社,2006.
[115]方锦清等.一门崭新的交叉科学:网络科学[J].物理学进展,2007,27(3).
[116]陈关荣.复杂网络及其新近研究进展介绍[J].力学进展,2008,38(25):653-660.
[117]吴金闪,狄增如.从统计物理学看复杂网络研究[J].物理学进展,2004,24(1):18-46.
[118]钟开莱著.吴让泉译.概率论教程[M].上海:上海科技出版社,1989.
[119]严士健,王隽骧,刘秀芳.概率论基础[M].科学出版社,1982.
[120]何声武.随机过程引论[M].高等教育出版社,1999.
[121]刘次华.随机过程[M].华中科技大学出版社,2004.