关于随机场及复杂网络的极限定理
|
摘要
本学位论文主要研究了树指标随机场及非齐次增长网络的极限定理。全文主要内容分为六章。
第一章,我们着重介绍了树指标随机场及复杂网络的基本知识、研究背景与发展现状,同时给出本学位论文所获得的主要结论以及使用的方法。
第二章我们给出树指标中心化随机场的定义并研究树指标中心化随机场的中心极限定理。
第三章给出树指标准相伴随机场的定义,利用Stein方法证明相应的中心极限定理。
第四章,首先研究一致有界树上齐次马氏链场的强大数定律及熵定理,然后用类似的方法得到一致有界树上非齐次马氏链场的强大数定律及熵定理。利用鞅序列的中心极限定理证明了一致有界树图上平稳马氏链场的中心极限定理,最后给出了一致有界树上齐次马氏链场序偶经验测度的弱大偏差原理。
第五章,我们将提出一个非齐次增长网络,当网络节点数目趋于无穷大时,考察与网络拓扑相关的极限性质,如度分布、度相关性等。
第六章,我们利用效用函数描述偏好效应,在考虑效用函数随机演化机制和偏好连接效应作用下,建立并研究一个非对称演化增长模型。
In this thesis, we mainly study the limit theorems based on random fields indexed by trees and complex networks. There are six chapters in this doctoral dissertation.
In chapter 1, we will present the basic theory and the background of random fields indexed by trees and complex networks. The main results obtained and the main methods we used in this thesis are stated.
In chapter 2, we give the definition of centered random field indexed by trees and study the central limit theorem of such case.
In chapter 3, we give the definition of quasi-associated random fields indexed by trees and study the central limit theorem of it.
In chapter 4, at first we study the strong law of large numbers and Shannon theo-rem on homogeneous Markov chain fields indexed by uniformly bounded trees, then we obtain the similar results of non-homogeneous Markov chain fields indexed by uniformly bounded trees by using the similar method as homogeneous case. By using the central limit theorem of martingale sequence, we also get the central limit theorem of stationary Markov chain fields indexed by uniformly bounded trees. At last, we give the weak large deviation principle of empirical pair measures of homogeneous Markov chain fields indexed by uniformly bounded trees.
In chapter 5, we put forward a model of non-homogeneous growing network, then we consider the limit properties in connection with the topology of the network such as the degree distributions and the degree correlations, when the number of nodes of our network tends to infinity.
In chapter 6, we use utility to describe the attractive effect and then study a simple asymmetrical evolving model, considering both preferential attachment and the random-ness of the utility.
第一章,我们着重介绍了树指标随机场及复杂网络的基本知识、研究背景与发展现状,同时给出本学位论文所获得的主要结论以及使用的方法。
第二章我们给出树指标中心化随机场的定义并研究树指标中心化随机场的中心极限定理。
第三章给出树指标准相伴随机场的定义,利用Stein方法证明相应的中心极限定理。
第四章,首先研究一致有界树上齐次马氏链场的强大数定律及熵定理,然后用类似的方法得到一致有界树上非齐次马氏链场的强大数定律及熵定理。利用鞅序列的中心极限定理证明了一致有界树图上平稳马氏链场的中心极限定理,最后给出了一致有界树上齐次马氏链场序偶经验测度的弱大偏差原理。
第五章,我们将提出一个非齐次增长网络,当网络节点数目趋于无穷大时,考察与网络拓扑相关的极限性质,如度分布、度相关性等。
第六章,我们利用效用函数描述偏好效应,在考虑效用函数随机演化机制和偏好连接效应作用下,建立并研究一个非对称演化增长模型。
In this thesis, we mainly study the limit theorems based on random fields indexed by trees and complex networks. There are six chapters in this doctoral dissertation.
In chapter 1, we will present the basic theory and the background of random fields indexed by trees and complex networks. The main results obtained and the main methods we used in this thesis are stated.
In chapter 2, we give the definition of centered random field indexed by trees and study the central limit theorem of such case.
In chapter 3, we give the definition of quasi-associated random fields indexed by trees and study the central limit theorem of it.
In chapter 4, at first we study the strong law of large numbers and Shannon theo-rem on homogeneous Markov chain fields indexed by uniformly bounded trees, then we obtain the similar results of non-homogeneous Markov chain fields indexed by uniformly bounded trees by using the similar method as homogeneous case. By using the central limit theorem of martingale sequence, we also get the central limit theorem of stationary Markov chain fields indexed by uniformly bounded trees. At last, we give the weak large deviation principle of empirical pair measures of homogeneous Markov chain fields indexed by uniformly bounded trees.
In chapter 5, we put forward a model of non-homogeneous growing network, then we consider the limit properties in connection with the topology of the network such as the degree distributions and the degree correlations, when the number of nodes of our network tends to infinity.
In chapter 6, we use utility to describe the attractive effect and then study a simple asymmetrical evolving model, considering both preferential attachment and the random-ness of the utility.
引文
[1]Aiello W., Chung F. and Lu L.. A random graph model for power law graphs. Experiment. Math.10:53-66.(2001)
[2]Alexander Bulinski and Alexey Shashkin, Limit Theorems For Associated Random fields and Related Systems. World Scientific Publishing Co.Pte.Ltd.(2007)
[3]Alon N., Spencer J.H., and Erdos P. The Probability Method. Wiley Inter science,New York. (1992)
[4]Albert R., Jeong H. and Barabasi A.-L.. Internet:Diameter of the world-wide web. Nature,401:130-131, (1999).
[5]Albert R., Barabasi A.-L.. Statistical mechanics of complex networks.Rev. Mod. Phys.74: 47-92.(2002)
[6]Amir Dembo,and O. Zeitouni. Large Deviations Techniques and Applications Springer,New York. (1998)
[7]Amir Dembo,Peter Mortersb and Scott Sheffield.Large deviations of Markov chains indexed by random trees.Annales de I'Institut Henri Poincare (B) Probability and Statistics.VOL. 41, NO.6:971-996 (2005)
[8]Barabasi A.-L. and Albert R.. Emergence of scaling in random networks. Science 286, 509-512.(1999)
[9]Barabasi A.-L., Albert R. and Jeong H.. Mean-field theory for scale-free random networks. Phys. A,272:pp.173-187.(1999)
[10]Barabasi A.-L., Albert R. and Jeong H.. Scale-free characteristics of random networks:the topology of the world-wide web. Physica A 311:69-77. (2000)
[11]Barabasi A.-L., Jeong H. and Neda Z., Ravasz E., Schubert A. and Vicsek T.. Evolution of the social network of scientific collaborations. Phys. A,311(3-4):590-614, (2002)
[12]Bebek G., Berenbrink P., Cooper C., Friedetzky T., Nadeau J. and Sahinalp S.C.The degree distribution of the generalized duplication model. Theoretical Computer Science 369 234-249.(2006)
[13]Borgs C.,Chayes J., Mossel E.and Roch S..The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). (2006)
[14]Bender E.A. and Canfield E.R.. The asymptotic number of labelled graphs with a given degree sequences. Journal of Combinatorial Theory (A),24:296-307.(1978)
[15]Benjamini I. and Peres Y., Markov chains indexed by trees. Ann Probab,22:219-243 (1994)
[16]Berger T. and Ye Z.X., Entropic aspects of random fields on trees. IEEE Trans Inform Theory,36:1006-1018.(1990)
[17]Bollobas B.. Random Graphs. Academic Press, London 1985.
[18]Bollobas B.. The isoperimetric number of random regular graphs.European J. Combin.9, pp.241-244. (1988)
[19]Bollobas B.. A probabilistic prool of an asymptotic formula for the number of labeled regular graphs. European J. Combin.1:311-316.(1980)
[20]Bollobas B., Riordan,O., Spencer,J., and Tusnady,G. The degree sequence of a scale-free random graph process. Random Structures Algorithms 18(3):279-290, (2001)
[21]Bollobas B. and Riordan,O..Robustness and Vulnerability of Scale-Free Random Graphs. Internet Mathematics Vol.1, No.1:1-35.(2003)
[22]Bollobas B. and Riordan,O.. The diameter of a scale-free random graph.Combinatorica 24 (1):5-34.(2004)
[23]Bollobas B., Janson, S., and Riordan, O.. The phase transition in inhomogeneous random graphs. arXiv math.PR/0504859.2006.
[24]Bolthausen E., On the central limit theorem for stationary mixing random fields. The Annals of Probability. Vol.10, No.4(1982) 1047-1050.
[25]Boris Pittel. Edge percolation on a random regular graph of low degree. Ann. Probab. Vol. 36, No.4 1359-1389.(2008)
[26]Britton T., Deijfen M. and Martin-Lof A. Generating simple random graphs with arbitrary degree sequences. J. Stat. Phys.124(6):1377-1397(2006)
[27]Brown.B.M.. Martingale central limit theorems. The Annals of Mathematical Statistics, 42:59-66 (1971)
[28]Callaway D.S., Hopcroft J.E., and Kleinbergm J.M. Newman M.E.J.,& Strogatz,S.H.. Are randomly grown graphs really random? Phys. Rev. E 64 (2001),041902.
[29]Chung F.R. and Lu L.Y. Complex Graphs and Networks. CBMS regional Conference series in mathematics. USA 107.2006.
[30]Chung, F.R., and Lu, L.Y., Connected components in random graphs with given degrees sequences. Ann. Comb.6:125-145,(2002)
[31]Chung F.R. and Lu, L.Y. The average distances in random graphs with given expected degrees. Internet Math.1(1):91-113, (2003).
[32]Chung F.R. and Lu, L.Y. The volume of the giant component of a random graph with given expected degrees.SIAM J. Discrete Math.20:395-411,2006.
[33]Chung F.R.,Lu L.Y. and Van Vu. The spectra of random graphs with given expected degrees. Internet Math 1:257-275. (2003)
[34]Chung F.R. and Lu, L.Y., Dewey T.G. and Galas D.J..Duplication models for biological networks. J. Comput. Biol.10:677-687.(2003)
[35]Cohen R. and Havlin S.. Scale-Free Networks Are Ultrasmall. Phys. Rev. Lett.90,058701 (2003)
[36]Cooper C. and Frieze A.M.. A general model of web graphs. Random Structures Algorithms 22(3):311-335 (2003)
[37]Cooper C. and Frieze A.M.. The cover time of the preferential attachment graph. J. Com. Theo.Series 597:29-290.(2007)
[38]Cooper C., Frieze A.M. and Vera J.. Random deletions in a scale free random graph pro-cess. Internet Mathematics 1:463-483.(2004)
[39]Dorogovtsev S. N., Mendes J. F. F. and Samukhin A. N.. Structure of growing networks with preferential linking.Phys. Rev. Lett.85:4633-4636.(2000)
[40]Maria Deijfen, Henri van den Esker,Remco van der Hofstad,Gerard Hooghiemstra. A pref-erential attachment model with random initial degrees.Mathematical Statistics.Stockholm University Research Report 2007:2, http://www.math.su.se/matstat
[41]Erdos P. and Renyi A. On random graphs. Publ. Math.6:290-297,1959.
[42]Erdos P. and Renyi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci.5:17-61,1960.
[43]Esary J., Proschan F., Walkup, D. Association of random variables with applications. Ann. Math. Statist.38,1466-1474.(1967)
[44]EVANS W., KEN YON C., PERES Y. and SCHULMAN L. J.. Broadcasting on trees and the Ising model. Ann. Appl. Probab.10:410-433.(2000)
[45]Faloutsos M., Faloutsos P. and Faloutsos C.. On power-law relationships of the internet topology. SIC-COMM 1999,Comput. Commun. Rev.29:251-262.(1999)
[46]Farkas, I. J., Derenyi, I., Barabasi, A.-L. and Vicsek, T.. Spectra of "Real-World" graphs: Beyond the semi-circle law.Phys. Rev. E.64,026704. (2001)
[47]Flaxman A.D., Frieze A. M. and Vera J.. Adversarial deletion in a Scale Free Random Graph Process. Combinatorics, Probability and Computing.Volume 16, Issue 2:261-270 (2007)
[48]Flaxman A.D., Frieze A. M. and Vera J.. A Geometric Preferential Attachment Model of Networks. Internet Mathematics 3(2):187-206. (2007)
[49]Flaxman A.D., Frieze A. M. and Vera J..A Geometric Preferential Attachment Model of Networks Ⅱ. WAW 2007, LNCS 4863,Springer-Verlag pp.41-55, (2007)
[50]Francis Comets, Martin Janzura. A central limit theorem for conditionally centred random fields with application to Markov fields. J.Appl.Prob.35:608-621.(1998)
[51]Fortuin C., Kasteleyn P., Ginibre J.. Correlation inequalities on some partially ordered sets. Comm. Math. Phys.22:89-103.(1971)
[52]Fountoulakis N. and Panagiotou K.. Rumor Spreading on Random Regular Graphs and Expanders.arXiv:1002.3518v1 (2010)
[53]Georgii H.O.. Gibbs Measures and Phase Transitions. Walter De Gruyter, Berlin. (1988)
[54]Gilbert N.. A simulation of the structure of academic science. Sociological Research Online 2.(1997)
[55]Goerdt A. The giant component threshold for random regular graphs with edge faults. Lecture Notes in Computer Science, vol.1295, Springer, Berlin, pp.279-288. Proc. MFCS 1997
[56]Goerdt A. Random regular graphs with edge faults:Expansion through cores. Theoretical Computer Science,Vol.264, No.1, pp.91-125(35) (2001)
[57]Goerdt A., Molloy M.. Analysis of edge deletion processes in faulty random regular graphs. Lecture Notes in Computer Science, vol.1776, Springer, Berlin,pp.38-47. Proc. Latin 2000.
[58]Goh K.-I., Kahng B. and Kim D.. Spectra and eigenvectors of scale-free networks, cond-mat/0103361. (2001)
[59]Gut,A.. Probability:A graduate course. Spinger.(2005)
[60]Huilin Huang. The degree sequences of an asymmetrical growing network. Statistics and Probability Letters.79:420-425 (2009)
[61]Huilin Huang, Weiguo Yang. Strong law of large numbers for Markov chains indexed by an infinite tree with uniformly bounded degree. Science in China Series A:Mathematics Vol. 51, No.2,195-202 (2008)
[62]IOFFE D.. A note on the extremality of the disordered state for the Ising model on the Bethe lattice.Lett. Math. Phys.37:137-143 (1996)
[63]IOFFE D.. A note on the extremality of the disordered state for the Ising model on the Bethe lattice. In Trees (B. Chauvin, S. Cohen and A. Roualt, eds.). Birkhauser, Boston.(1996)
[64]KENYON, C., MOSSEL E. and PERES Y.. Glauber dynamics on trees and hyperbolic graphs (extended abstract).In Proceedings of FOCS 2001.
[65]Janson S. and MOSSEL E.. Robust Reconstruction on Trees Is Determined by the Second Eigenvalue. The Annals of Probability,Vol.32, No.3, B.pp.2630-2649.(2004)
[66]Janson S., Luczak T., and Rucinski,A.. Random graphs. Wiley, New York(2000)
[67]Kang, M. and Seierstad, T. G.. Phase transition of the minimum degree random multigraph process. Random Structures Algorithms 31:330-353(2007)
[68]Kim J.H Sudakov B. and Van Vu.Small subgraphs of random regular graphs. Discrete Mathematics Vol.307, No.15 1961-1967.(2007)
[69]Kim J.H Sudakov B. and Van Vu. On the asymmetry of random graphs and random regular graphs. Random Structures and Algorithms.21 pp.216-224(2002)
[70]Krapivsky P. L., Redner S. and Leyvraz F.. Connectivity of growing random networks. Phys. Rev. Lett.85:pp.4629-4632.(2000)
[71]Krapivsky P. L. and Redner S.. Organization of growing random networks. Phys. Rev. E, art. no.066123.63 (2001)
[72]Kumar R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A. and Upfal E.. Stochas-tic models for the web graph. FOCS, pp.57-65.(2000)
[73]van den Esker H., van der Hofstad R. and G. Hooghiemstra. Universality for the distance infinite variance random graphs. Preprint,2006.
[74]Harris T.E.. A lower bound for the critical probability in a certain percolation process. Proc. Camb. Phil. Soc.159,13-20.(1960)
[75]Janson S., Luczak T. and Rucinski,A.. Random Graphs. Wiley, New York (2000)
[76]Joag-Dev, K., Proschan, F.. Negative association of random variables with applications. Ann. Statist.11,286-299.(1983)
[77]Kemeny J.G., Snell J.L. and Knapp A.W., Denumberable Markov Chains. Springer, New York.(1976)
[78]Krapivsky P. L., and Redner.S., Organization of growing random networks. Physical Review E 066123, (2001)
[79]Krivelevich M., Sudakov B., Vu V. and Wormald N.. Random regular graphs of high degree. Random Structures and Algorithms 18.pp.346-363.(2001)
[80]L. A. Adamic and B. A. Huberman. Power-law distribution of the world wide web. Science 287,P2115a, (2000)
[81]Lehmann E.. Some concepts of dependence. Ann. Math. Statist.37,1137(?)1153.(1966)
[82]Liu,W. and Yang, W.G., A extension of Shannon-McMillan theorem and some limit prop-erties for nonhomogeneous Markov chains. Stocha Proc Appl,61:129-145 (1996)
[83]Liu,W. and Yang, W.G., The Markov approximation of the sequences of N-valued random variables and a class of deviation theorems.Stochas Proc Appl,89:117-130(2000)
[84]Lotka A. J.. The frequency distribution of scientific productivity. J. of the Washington Acad. of Sci.16:317-323.(1926)
[85]陆传荣,林正炎,相依随机变量的极限定理.科学出版社,(1997)
[86]McKay B. and Wormald N.. Uniform generation of random regular graphs of moderate degree. J. Algorithms.11 pp.52-67.(1990)
[87]Molloy, M. and Reed, B. A critical point for random graphs with a given degree sequence. Rand. Struct. Alg.6:161-179,(1995)
[88]Molloy, M. and Reed, B. The size of the giant component of a random graphs with a given degree sequence, Comb. Prob. Comp.7:295-305,(1998)
[89]MOSSEL E.. Recursive reconstruction on periodic trees.Random Structures Algorithms 13: 81-97.(1998)
[90]MOSSEL E.. Reconstruction on trees:Beating the second eigenvalue. Ann. Appl. Probab.ll: 285-300. (2001).
[91]MOSSEL E. and Peres Y.. Information Flow on Trees. The Annals of Applied Probabil-ity,Vol.13, No.3 pp.817-844.(2003)
[92]Newman M. E. J.. Models of the small world. J. Statist. Phys.,101, pp.819-841.(2000)
[93]Newman M. E. J.. Clustering and preferential attachment in growing networks.Phys. Rev. E,64, art. no.025102.(2001)
[94]Newman M. E. J.. Scientific collaboration networks:I. Network construction and funda-mental results.Phys. Rev. E,64, art. no.016131.(2001)
[95]Newman M. E. J.. Scientific collaboration networks:II. Shortest paths, weighted networks, and centrality.Phys. Rev. E,64, art. no.016132.(2001)
[96]Newman M. E. J.. The structure of scientific collaboration networks.Proc. Natl. Acad. Sci. USA,98, pp.404-409.(2001)
[97]Newman M. E. J.. Assortative mixing in networks.Phys. Rev. Lett.,89, art. no. 208701.(2002)
[98]Newman M. E. J.. Spread of epidemic disease on networks.Phys. Rev. E,66, art. no.016128. (2002)
[99]Newman M. E. J.. The structure and function of networks, Comput. Phys. Comm.,147, pp.40-45.(2002)
[100]Newman M. E. J.. Ego-centered networks and the ripple effect. Social Networks,25, pp. 83-95.(2003)
[101]Newman M. E. J.. Mixing patterns in networks.Phys. Rev. E,67, art. no.026126. (2003)
[102]Newman M. E. J.. Random graphs as models of networks, in Handbook of Graphs and NetworksS. Bornholdt and H. G. Schuster, eds., Wiley-VCH, Berlin, pp.35-68.(2003)
[103]Newman M. E. J., Barabasi A.-L. and Watts D. J.. The Structure and Dynamics of Net-works Princeton University Press, Princeton, NJ,2003.
[104]Newman M. E. J., Forrest S. and Balthrop J.. Email networks and the spread of computer viruses.Phys. Rev. E,66, art. no.035101.(2002)
[105]Newman M. E. J., Moore C. and Watts D. J.. Mean-field solution of the small-world network model.Phys. Rev. Lett,84, pp.3201-3204.(2000)
[106]Newman M. E. J., Strogatz S. H. and Watts D. J.. Random graphs with arbitrary degree distributions and their applications.Phys. Rev. E,64, art. no.026118.(2001)
[107]Newman M. E. J. and Watts D. J.. Renormalization group analysis of the small-world network model.Phys. Lett. A,263, pp.341-346.(1999)
[108]Newman M. E. J. and Watts D. J.. Scaling and percolation in the small-world network model.Phys. Rev. E,60, pp.7332-7342.(1999)
[109]Newman, C. Normal Fluctuations and the FKG inequalities. Comm. Math. Phys.74,119-128.(1980)
[110]Newman, C. Asymptotic independence and limit theorems for positively and negatively dependent random variables. In:Tong,Y.L. (Ed.), Inequalities in Statistics and Probabil-ity.IMS Lecture Notes - Monograph Ser., vol.5. Inst. Math. Statist., Hayward, CA, pp. 127-140. (1984)
[111]Nikoloski,Z., Deo N., and Kucera. L., Degree-correlation of a Scale-free Random Graph Process.Euro Comb, DMTCS proc. AE.239-244(2005)
[112]Nikoletseas S., Spirakis P.. Expander properties of random regular graphs with edge faults.Lecture Notes in Computer Science, vol.900, Springer, Berlin, pp.421-432.Proc. STACS 1995
[113]Ohno S.. Evolution by Gene DuplicationSpringer, Berlin.(1970)
[114]Pemantle R.. Antomorphism invariant measure on trees. Ann Prob,20:1549-1566. (1992)
[115]Pemantle R. and STEIF, J. E.. Robust phase transitions for Heisenberg and other models on general trees. Ann. Probab.27:876-912.(1999).
[116]Price D. J. de S.. Networks of scientific papers.Science.149 pp:510-515.(1965)
[117]Price D. J. de S.. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inform. Sci.27:pp.292-306. (1976)
[118]Reittu H. and Ilkka Norros I..On the power-law random graph model of massive data networks. Performance Evaluation.55:3-23.(2004)
[119]Satorras R. P., Smith E. and Sole R.V.. Evolving protein interaction networks through gene duplication.J. Theor. Biol.222:199-210.(2003)
[120]S. Strogatz. Exploring complex networks.Nature 410(8):268-276. (2001).
[121]Soderberg,B. General formalism for inhomogeneous random graphs. Phys. Rev. E 66 (2002),066121.
[122]Spitzer, F., Markov random fields on an infinite tree. Ann Probab,3:387-398 (1975)
[123]Stein, C., A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proc. Sixth Berkeley Symp. Math. Statist. Probab. Ⅱ. Probability Theory Univ. California Press, Berkeley.583-602,(1972).
[124]Stein, C. Approximate computation of expectations. Institute of Mathematical Statistics, Hayward, CA (1986)
[125]Stein, C. A way of using auxiliary randomization.In:Chen, L.H.Y., Choi, K.P., Hu, K., Lou, J.H. (eds):Probability theory. De Gruyter, Berlin.159-180,(1992)
[126]Takacs. C., Strong law of large numbers for branching Markov chains. Markov Proc Related Fields,8:107-116 (2001)
[127]Tenner T., Flaxman A. and Frieze A.. High degree vertices and eigenvalues in the prefer-ential attachment graph. Internet Mathematics,2:1-20.(2005)
[128]Turova T.S. Dynamical random graphs with memory, Phys. Rev. E 65 (2002),066102. Erratum:Phys. Rev. E 70,059902(E).(2004)
[129]Turova,T.S. Long paths and cycles in dynamical graphs. J. Statist. Phys.110:385-417.(2003)
[130]Turova,T.S. Continuity of the percolation threshold in randomly grown graphs, preprint, (2005).
[131]Turova,T.S. Phase transitions in dynamical random graphs. J. Statist. Phys.123(5),(2006).
[132]Van der Hofstad, R. Random Graphs and Complex Networks.Preprint(2008)
[133]Van der Hofstad, R., Hooghiemstra G. and Van Mieghem P.. Distances in random graphs with finite variance degrees. Random Structures Algorithms,27(1):76-123, (2005).
[134]Van der Hofstad, R., Hooghiemstra G. and Znamenski D.. Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab.,12(25):703-766 (electronic), (2007).
[135]Van der Hofstad, R., Hooghiemstra G. and Znamenski D.. Random graphs with arbitrary i.i.d. degrees. arXiv:math/0502580v2(2006)
[136]van den Esker H., van der Hofstad R., Hooghiemstra G. and Znamenski D.. Distances in random graphs with infinite mean degrees. Extremes 8:111-141.(2006)
[137]Watts,D. J., Networks, dynamics, and the small world phenomenon.Amer. J. Sociol. 105(1999), pp.493-592.
[138]Watts, D. J., Small Worlds. Princeton University Press, Princeton, NJ 1999.
[139]Watts D. J., and Strogatz S. H. Collective dynamics of "small-world" networks, Nature 393 pp.440-442.(1998)
[140]Wormald N.. The asymptotic distribution of short cycles in random regular graphs, J. Combm. Theory B 31 pp.168-182(1981)
[141]Wormald N.. Models of random regular graphs, in:Surveys in Combinatorics, Proceeding Cambridge 1999, London Mathematical Society Lecture Note Ser., vol.276, Cambridge University Press, Cambridge pp.239-298. (1999)
[142]Wormald, N.C. Some problems in the enumeration of labelled graphs, Doctoral thesis, Newcastle University.(1978)
[143]Yang, W.G. and Liu, W., Strong law of large numbers for Markov chains fields on a Bethe tree.Statist Prob Lett,49:245-250 (2000)
[144]Yang,W.G., Some limit properties for Markov chains indexed by a homogeneous tree. Statist Prob Lett,65:241-250(2003)
[145]Ye,Z.X, and Berger, T., Ergodic, regulary and asymptotic equipartition property of ran-dom fields on trees. J Combin Inform System Sci,21:157-184. (1996)
[146]Ye,Z.X, and Berger, T., Information Measures for Discrete Random Fields. Science, Bei-jing,(1998)
[147]Zheng J.F.,Gao Z.Y. and Zhao H..Properties of asymmetrical evolving networks. Physica A 376:719-724,(2007)
[2]Alexander Bulinski and Alexey Shashkin, Limit Theorems For Associated Random fields and Related Systems. World Scientific Publishing Co.Pte.Ltd.(2007)
[3]Alon N., Spencer J.H., and Erdos P. The Probability Method. Wiley Inter science,New York. (1992)
[4]Albert R., Jeong H. and Barabasi A.-L.. Internet:Diameter of the world-wide web. Nature,401:130-131, (1999).
[5]Albert R., Barabasi A.-L.. Statistical mechanics of complex networks.Rev. Mod. Phys.74: 47-92.(2002)
[6]Amir Dembo,and O. Zeitouni. Large Deviations Techniques and Applications Springer,New York. (1998)
[7]Amir Dembo,Peter Mortersb and Scott Sheffield.Large deviations of Markov chains indexed by random trees.Annales de I'Institut Henri Poincare (B) Probability and Statistics.VOL. 41, NO.6:971-996 (2005)
[8]Barabasi A.-L. and Albert R.. Emergence of scaling in random networks. Science 286, 509-512.(1999)
[9]Barabasi A.-L., Albert R. and Jeong H.. Mean-field theory for scale-free random networks. Phys. A,272:pp.173-187.(1999)
[10]Barabasi A.-L., Albert R. and Jeong H.. Scale-free characteristics of random networks:the topology of the world-wide web. Physica A 311:69-77. (2000)
[11]Barabasi A.-L., Jeong H. and Neda Z., Ravasz E., Schubert A. and Vicsek T.. Evolution of the social network of scientific collaborations. Phys. A,311(3-4):590-614, (2002)
[12]Bebek G., Berenbrink P., Cooper C., Friedetzky T., Nadeau J. and Sahinalp S.C.The degree distribution of the generalized duplication model. Theoretical Computer Science 369 234-249.(2006)
[13]Borgs C.,Chayes J., Mossel E.and Roch S..The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). (2006)
[14]Bender E.A. and Canfield E.R.. The asymptotic number of labelled graphs with a given degree sequences. Journal of Combinatorial Theory (A),24:296-307.(1978)
[15]Benjamini I. and Peres Y., Markov chains indexed by trees. Ann Probab,22:219-243 (1994)
[16]Berger T. and Ye Z.X., Entropic aspects of random fields on trees. IEEE Trans Inform Theory,36:1006-1018.(1990)
[17]Bollobas B.. Random Graphs. Academic Press, London 1985.
[18]Bollobas B.. The isoperimetric number of random regular graphs.European J. Combin.9, pp.241-244. (1988)
[19]Bollobas B.. A probabilistic prool of an asymptotic formula for the number of labeled regular graphs. European J. Combin.1:311-316.(1980)
[20]Bollobas B., Riordan,O., Spencer,J., and Tusnady,G. The degree sequence of a scale-free random graph process. Random Structures Algorithms 18(3):279-290, (2001)
[21]Bollobas B. and Riordan,O..Robustness and Vulnerability of Scale-Free Random Graphs. Internet Mathematics Vol.1, No.1:1-35.(2003)
[22]Bollobas B. and Riordan,O.. The diameter of a scale-free random graph.Combinatorica 24 (1):5-34.(2004)
[23]Bollobas B., Janson, S., and Riordan, O.. The phase transition in inhomogeneous random graphs. arXiv math.PR/0504859.2006.
[24]Bolthausen E., On the central limit theorem for stationary mixing random fields. The Annals of Probability. Vol.10, No.4(1982) 1047-1050.
[25]Boris Pittel. Edge percolation on a random regular graph of low degree. Ann. Probab. Vol. 36, No.4 1359-1389.(2008)
[26]Britton T., Deijfen M. and Martin-Lof A. Generating simple random graphs with arbitrary degree sequences. J. Stat. Phys.124(6):1377-1397(2006)
[27]Brown.B.M.. Martingale central limit theorems. The Annals of Mathematical Statistics, 42:59-66 (1971)
[28]Callaway D.S., Hopcroft J.E., and Kleinbergm J.M. Newman M.E.J.,& Strogatz,S.H.. Are randomly grown graphs really random? Phys. Rev. E 64 (2001),041902.
[29]Chung F.R. and Lu L.Y. Complex Graphs and Networks. CBMS regional Conference series in mathematics. USA 107.2006.
[30]Chung, F.R., and Lu, L.Y., Connected components in random graphs with given degrees sequences. Ann. Comb.6:125-145,(2002)
[31]Chung F.R. and Lu, L.Y. The average distances in random graphs with given expected degrees. Internet Math.1(1):91-113, (2003).
[32]Chung F.R. and Lu, L.Y. The volume of the giant component of a random graph with given expected degrees.SIAM J. Discrete Math.20:395-411,2006.
[33]Chung F.R.,Lu L.Y. and Van Vu. The spectra of random graphs with given expected degrees. Internet Math 1:257-275. (2003)
[34]Chung F.R. and Lu, L.Y., Dewey T.G. and Galas D.J..Duplication models for biological networks. J. Comput. Biol.10:677-687.(2003)
[35]Cohen R. and Havlin S.. Scale-Free Networks Are Ultrasmall. Phys. Rev. Lett.90,058701 (2003)
[36]Cooper C. and Frieze A.M.. A general model of web graphs. Random Structures Algorithms 22(3):311-335 (2003)
[37]Cooper C. and Frieze A.M.. The cover time of the preferential attachment graph. J. Com. Theo.Series 597:29-290.(2007)
[38]Cooper C., Frieze A.M. and Vera J.. Random deletions in a scale free random graph pro-cess. Internet Mathematics 1:463-483.(2004)
[39]Dorogovtsev S. N., Mendes J. F. F. and Samukhin A. N.. Structure of growing networks with preferential linking.Phys. Rev. Lett.85:4633-4636.(2000)
[40]Maria Deijfen, Henri van den Esker,Remco van der Hofstad,Gerard Hooghiemstra. A pref-erential attachment model with random initial degrees.Mathematical Statistics.Stockholm University Research Report 2007:2, http://www.math.su.se/matstat
[41]Erdos P. and Renyi A. On random graphs. Publ. Math.6:290-297,1959.
[42]Erdos P. and Renyi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci.5:17-61,1960.
[43]Esary J., Proschan F., Walkup, D. Association of random variables with applications. Ann. Math. Statist.38,1466-1474.(1967)
[44]EVANS W., KEN YON C., PERES Y. and SCHULMAN L. J.. Broadcasting on trees and the Ising model. Ann. Appl. Probab.10:410-433.(2000)
[45]Faloutsos M., Faloutsos P. and Faloutsos C.. On power-law relationships of the internet topology. SIC-COMM 1999,Comput. Commun. Rev.29:251-262.(1999)
[46]Farkas, I. J., Derenyi, I., Barabasi, A.-L. and Vicsek, T.. Spectra of "Real-World" graphs: Beyond the semi-circle law.Phys. Rev. E.64,026704. (2001)
[47]Flaxman A.D., Frieze A. M. and Vera J.. Adversarial deletion in a Scale Free Random Graph Process. Combinatorics, Probability and Computing.Volume 16, Issue 2:261-270 (2007)
[48]Flaxman A.D., Frieze A. M. and Vera J.. A Geometric Preferential Attachment Model of Networks. Internet Mathematics 3(2):187-206. (2007)
[49]Flaxman A.D., Frieze A. M. and Vera J..A Geometric Preferential Attachment Model of Networks Ⅱ. WAW 2007, LNCS 4863,Springer-Verlag pp.41-55, (2007)
[50]Francis Comets, Martin Janzura. A central limit theorem for conditionally centred random fields with application to Markov fields. J.Appl.Prob.35:608-621.(1998)
[51]Fortuin C., Kasteleyn P., Ginibre J.. Correlation inequalities on some partially ordered sets. Comm. Math. Phys.22:89-103.(1971)
[52]Fountoulakis N. and Panagiotou K.. Rumor Spreading on Random Regular Graphs and Expanders.arXiv:1002.3518v1 (2010)
[53]Georgii H.O.. Gibbs Measures and Phase Transitions. Walter De Gruyter, Berlin. (1988)
[54]Gilbert N.. A simulation of the structure of academic science. Sociological Research Online 2.(1997)
[55]Goerdt A. The giant component threshold for random regular graphs with edge faults. Lecture Notes in Computer Science, vol.1295, Springer, Berlin, pp.279-288. Proc. MFCS 1997
[56]Goerdt A. Random regular graphs with edge faults:Expansion through cores. Theoretical Computer Science,Vol.264, No.1, pp.91-125(35) (2001)
[57]Goerdt A., Molloy M.. Analysis of edge deletion processes in faulty random regular graphs. Lecture Notes in Computer Science, vol.1776, Springer, Berlin,pp.38-47. Proc. Latin 2000.
[58]Goh K.-I., Kahng B. and Kim D.. Spectra and eigenvectors of scale-free networks, cond-mat/0103361. (2001)
[59]Gut,A.. Probability:A graduate course. Spinger.(2005)
[60]Huilin Huang. The degree sequences of an asymmetrical growing network. Statistics and Probability Letters.79:420-425 (2009)
[61]Huilin Huang, Weiguo Yang. Strong law of large numbers for Markov chains indexed by an infinite tree with uniformly bounded degree. Science in China Series A:Mathematics Vol. 51, No.2,195-202 (2008)
[62]IOFFE D.. A note on the extremality of the disordered state for the Ising model on the Bethe lattice.Lett. Math. Phys.37:137-143 (1996)
[63]IOFFE D.. A note on the extremality of the disordered state for the Ising model on the Bethe lattice. In Trees (B. Chauvin, S. Cohen and A. Roualt, eds.). Birkhauser, Boston.(1996)
[64]KENYON, C., MOSSEL E. and PERES Y.. Glauber dynamics on trees and hyperbolic graphs (extended abstract).In Proceedings of FOCS 2001.
[65]Janson S. and MOSSEL E.. Robust Reconstruction on Trees Is Determined by the Second Eigenvalue. The Annals of Probability,Vol.32, No.3, B.pp.2630-2649.(2004)
[66]Janson S., Luczak T., and Rucinski,A.. Random graphs. Wiley, New York(2000)
[67]Kang, M. and Seierstad, T. G.. Phase transition of the minimum degree random multigraph process. Random Structures Algorithms 31:330-353(2007)
[68]Kim J.H Sudakov B. and Van Vu.Small subgraphs of random regular graphs. Discrete Mathematics Vol.307, No.15 1961-1967.(2007)
[69]Kim J.H Sudakov B. and Van Vu. On the asymmetry of random graphs and random regular graphs. Random Structures and Algorithms.21 pp.216-224(2002)
[70]Krapivsky P. L., Redner S. and Leyvraz F.. Connectivity of growing random networks. Phys. Rev. Lett.85:pp.4629-4632.(2000)
[71]Krapivsky P. L. and Redner S.. Organization of growing random networks. Phys. Rev. E, art. no.066123.63 (2001)
[72]Kumar R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A. and Upfal E.. Stochas-tic models for the web graph. FOCS, pp.57-65.(2000)
[73]van den Esker H., van der Hofstad R. and G. Hooghiemstra. Universality for the distance infinite variance random graphs. Preprint,2006.
[74]Harris T.E.. A lower bound for the critical probability in a certain percolation process. Proc. Camb. Phil. Soc.159,13-20.(1960)
[75]Janson S., Luczak T. and Rucinski,A.. Random Graphs. Wiley, New York (2000)
[76]Joag-Dev, K., Proschan, F.. Negative association of random variables with applications. Ann. Statist.11,286-299.(1983)
[77]Kemeny J.G., Snell J.L. and Knapp A.W., Denumberable Markov Chains. Springer, New York.(1976)
[78]Krapivsky P. L., and Redner.S., Organization of growing random networks. Physical Review E 066123, (2001)
[79]Krivelevich M., Sudakov B., Vu V. and Wormald N.. Random regular graphs of high degree. Random Structures and Algorithms 18.pp.346-363.(2001)
[80]L. A. Adamic and B. A. Huberman. Power-law distribution of the world wide web. Science 287,P2115a, (2000)
[81]Lehmann E.. Some concepts of dependence. Ann. Math. Statist.37,1137(?)1153.(1966)
[82]Liu,W. and Yang, W.G., A extension of Shannon-McMillan theorem and some limit prop-erties for nonhomogeneous Markov chains. Stocha Proc Appl,61:129-145 (1996)
[83]Liu,W. and Yang, W.G., The Markov approximation of the sequences of N-valued random variables and a class of deviation theorems.Stochas Proc Appl,89:117-130(2000)
[84]Lotka A. J.. The frequency distribution of scientific productivity. J. of the Washington Acad. of Sci.16:317-323.(1926)
[85]陆传荣,林正炎,相依随机变量的极限定理.科学出版社,(1997)
[86]McKay B. and Wormald N.. Uniform generation of random regular graphs of moderate degree. J. Algorithms.11 pp.52-67.(1990)
[87]Molloy, M. and Reed, B. A critical point for random graphs with a given degree sequence. Rand. Struct. Alg.6:161-179,(1995)
[88]Molloy, M. and Reed, B. The size of the giant component of a random graphs with a given degree sequence, Comb. Prob. Comp.7:295-305,(1998)
[89]MOSSEL E.. Recursive reconstruction on periodic trees.Random Structures Algorithms 13: 81-97.(1998)
[90]MOSSEL E.. Reconstruction on trees:Beating the second eigenvalue. Ann. Appl. Probab.ll: 285-300. (2001).
[91]MOSSEL E. and Peres Y.. Information Flow on Trees. The Annals of Applied Probabil-ity,Vol.13, No.3 pp.817-844.(2003)
[92]Newman M. E. J.. Models of the small world. J. Statist. Phys.,101, pp.819-841.(2000)
[93]Newman M. E. J.. Clustering and preferential attachment in growing networks.Phys. Rev. E,64, art. no.025102.(2001)
[94]Newman M. E. J.. Scientific collaboration networks:I. Network construction and funda-mental results.Phys. Rev. E,64, art. no.016131.(2001)
[95]Newman M. E. J.. Scientific collaboration networks:II. Shortest paths, weighted networks, and centrality.Phys. Rev. E,64, art. no.016132.(2001)
[96]Newman M. E. J.. The structure of scientific collaboration networks.Proc. Natl. Acad. Sci. USA,98, pp.404-409.(2001)
[97]Newman M. E. J.. Assortative mixing in networks.Phys. Rev. Lett.,89, art. no. 208701.(2002)
[98]Newman M. E. J.. Spread of epidemic disease on networks.Phys. Rev. E,66, art. no.016128. (2002)
[99]Newman M. E. J.. The structure and function of networks, Comput. Phys. Comm.,147, pp.40-45.(2002)
[100]Newman M. E. J.. Ego-centered networks and the ripple effect. Social Networks,25, pp. 83-95.(2003)
[101]Newman M. E. J.. Mixing patterns in networks.Phys. Rev. E,67, art. no.026126. (2003)
[102]Newman M. E. J.. Random graphs as models of networks, in Handbook of Graphs and NetworksS. Bornholdt and H. G. Schuster, eds., Wiley-VCH, Berlin, pp.35-68.(2003)
[103]Newman M. E. J., Barabasi A.-L. and Watts D. J.. The Structure and Dynamics of Net-works Princeton University Press, Princeton, NJ,2003.
[104]Newman M. E. J., Forrest S. and Balthrop J.. Email networks and the spread of computer viruses.Phys. Rev. E,66, art. no.035101.(2002)
[105]Newman M. E. J., Moore C. and Watts D. J.. Mean-field solution of the small-world network model.Phys. Rev. Lett,84, pp.3201-3204.(2000)
[106]Newman M. E. J., Strogatz S. H. and Watts D. J.. Random graphs with arbitrary degree distributions and their applications.Phys. Rev. E,64, art. no.026118.(2001)
[107]Newman M. E. J. and Watts D. J.. Renormalization group analysis of the small-world network model.Phys. Lett. A,263, pp.341-346.(1999)
[108]Newman M. E. J. and Watts D. J.. Scaling and percolation in the small-world network model.Phys. Rev. E,60, pp.7332-7342.(1999)
[109]Newman, C. Normal Fluctuations and the FKG inequalities. Comm. Math. Phys.74,119-128.(1980)
[110]Newman, C. Asymptotic independence and limit theorems for positively and negatively dependent random variables. In:Tong,Y.L. (Ed.), Inequalities in Statistics and Probabil-ity.IMS Lecture Notes - Monograph Ser., vol.5. Inst. Math. Statist., Hayward, CA, pp. 127-140. (1984)
[111]Nikoloski,Z., Deo N., and Kucera. L., Degree-correlation of a Scale-free Random Graph Process.Euro Comb, DMTCS proc. AE.239-244(2005)
[112]Nikoletseas S., Spirakis P.. Expander properties of random regular graphs with edge faults.Lecture Notes in Computer Science, vol.900, Springer, Berlin, pp.421-432.Proc. STACS 1995
[113]Ohno S.. Evolution by Gene DuplicationSpringer, Berlin.(1970)
[114]Pemantle R.. Antomorphism invariant measure on trees. Ann Prob,20:1549-1566. (1992)
[115]Pemantle R. and STEIF, J. E.. Robust phase transitions for Heisenberg and other models on general trees. Ann. Probab.27:876-912.(1999).
[116]Price D. J. de S.. Networks of scientific papers.Science.149 pp:510-515.(1965)
[117]Price D. J. de S.. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inform. Sci.27:pp.292-306. (1976)
[118]Reittu H. and Ilkka Norros I..On the power-law random graph model of massive data networks. Performance Evaluation.55:3-23.(2004)
[119]Satorras R. P., Smith E. and Sole R.V.. Evolving protein interaction networks through gene duplication.J. Theor. Biol.222:199-210.(2003)
[120]S. Strogatz. Exploring complex networks.Nature 410(8):268-276. (2001).
[121]Soderberg,B. General formalism for inhomogeneous random graphs. Phys. Rev. E 66 (2002),066121.
[122]Spitzer, F., Markov random fields on an infinite tree. Ann Probab,3:387-398 (1975)
[123]Stein, C., A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proc. Sixth Berkeley Symp. Math. Statist. Probab. Ⅱ. Probability Theory Univ. California Press, Berkeley.583-602,(1972).
[124]Stein, C. Approximate computation of expectations. Institute of Mathematical Statistics, Hayward, CA (1986)
[125]Stein, C. A way of using auxiliary randomization.In:Chen, L.H.Y., Choi, K.P., Hu, K., Lou, J.H. (eds):Probability theory. De Gruyter, Berlin.159-180,(1992)
[126]Takacs. C., Strong law of large numbers for branching Markov chains. Markov Proc Related Fields,8:107-116 (2001)
[127]Tenner T., Flaxman A. and Frieze A.. High degree vertices and eigenvalues in the prefer-ential attachment graph. Internet Mathematics,2:1-20.(2005)
[128]Turova T.S. Dynamical random graphs with memory, Phys. Rev. E 65 (2002),066102. Erratum:Phys. Rev. E 70,059902(E).(2004)
[129]Turova,T.S. Long paths and cycles in dynamical graphs. J. Statist. Phys.110:385-417.(2003)
[130]Turova,T.S. Continuity of the percolation threshold in randomly grown graphs, preprint, (2005).
[131]Turova,T.S. Phase transitions in dynamical random graphs. J. Statist. Phys.123(5),(2006).
[132]Van der Hofstad, R. Random Graphs and Complex Networks.Preprint(2008)
[133]Van der Hofstad, R., Hooghiemstra G. and Van Mieghem P.. Distances in random graphs with finite variance degrees. Random Structures Algorithms,27(1):76-123, (2005).
[134]Van der Hofstad, R., Hooghiemstra G. and Znamenski D.. Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab.,12(25):703-766 (electronic), (2007).
[135]Van der Hofstad, R., Hooghiemstra G. and Znamenski D.. Random graphs with arbitrary i.i.d. degrees. arXiv:math/0502580v2(2006)
[136]van den Esker H., van der Hofstad R., Hooghiemstra G. and Znamenski D.. Distances in random graphs with infinite mean degrees. Extremes 8:111-141.(2006)
[137]Watts,D. J., Networks, dynamics, and the small world phenomenon.Amer. J. Sociol. 105(1999), pp.493-592.
[138]Watts, D. J., Small Worlds. Princeton University Press, Princeton, NJ 1999.
[139]Watts D. J., and Strogatz S. H. Collective dynamics of "small-world" networks, Nature 393 pp.440-442.(1998)
[140]Wormald N.. The asymptotic distribution of short cycles in random regular graphs, J. Combm. Theory B 31 pp.168-182(1981)
[141]Wormald N.. Models of random regular graphs, in:Surveys in Combinatorics, Proceeding Cambridge 1999, London Mathematical Society Lecture Note Ser., vol.276, Cambridge University Press, Cambridge pp.239-298. (1999)
[142]Wormald, N.C. Some problems in the enumeration of labelled graphs, Doctoral thesis, Newcastle University.(1978)
[143]Yang, W.G. and Liu, W., Strong law of large numbers for Markov chains fields on a Bethe tree.Statist Prob Lett,49:245-250 (2000)
[144]Yang,W.G., Some limit properties for Markov chains indexed by a homogeneous tree. Statist Prob Lett,65:241-250(2003)
[145]Ye,Z.X, and Berger, T., Ergodic, regulary and asymptotic equipartition property of ran-dom fields on trees. J Combin Inform System Sci,21:157-184. (1996)
[146]Ye,Z.X, and Berger, T., Information Measures for Discrete Random Fields. Science, Bei-jing,(1998)
[147]Zheng J.F.,Gao Z.Y. and Zhao H..Properties of asymmetrical evolving networks. Physica A 376:719-724,(2007)