PDF(621 KB)
PDF(621 KB)
PDF(621 KB)
修正的Newman-Watts小世界及其上随机游走的混合时
On the Modified Newman-Watts Small World and Its Random Walk
在一个常规构建的图中加"长边（shortcuts）"会得到一个小世界模型，这是经典的构造小世界模型的方法.最近，吴宪远在文[Internet Mathematics，DOI：10.1080/15427951，2015.101208]中指出，在加"长边"过程中加的所有边，只有与图的直径成正比才会对小世界模型的构造起决定性作用.我们依据此文的加边机制，对体积为nd的d（d ≥ 1）维格点图，只添加起决定性作用的长边，得到的小世界模型修正了原始的Newman-Watts小世界模型，并证明该模型的直径和混合时是log n阶的.
It is well known that adding "long edges (shortcuts)" to a regularly constructed graph will make the resulted model a small world. Recently,[Internet Mathematics, DOI:10.1080/15427951, 2015.101208] indicated that, among all long edges, those edges with length proportional to the diameter of the regularly constructed graph may play the key role. In this paper, we modify the original Newman-Watts small world by adding only long special edges to the d (d ≥ 1)-dimensional lattice torus (with size nd) according to[Internet Mathematics, DOI:10.1080/15427951, 2015.101208], and show that both the diameter of the modified model and the mixing time of random walk on it grow polynomially fast in log n.
随机网络 / 小世界效应 / 随机游走 / 混合时 {{custom_keyword}} /
random networks / small world effect / random walk / mixing time {{custom_keyword}} /
[1] Aldous D., Diaconis P., Shuffling cards and stopping times, The American Mathematical Monthly, 1986, 93(5):333-348.
[2] Alon N., Milman V. D., λ1, Isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory Series B, 1985, 38(1):73-88.
[3] Berman A., Zhang X. D., Lower bounds for the eigenvalues of Laplacian matrices, Linear Algebra and its Applications, 2000, 316(1-3):13-20.
[4] Bollobás B., Chung F. R. K., The diameter of a cycle plus a random matching, SIAM Journal on Discrete Mathematics, 1988, 1(3):328-333.
[5] Bollobás B., Riordan O. M., Mathematical results on scale-free random graphs, Handbook of Graphs and Networks:From the Genome to the Internet, 2002.
[6] Bollobás B., Riordan O., The diameter of a scale-free random graph, Combinatorica, 2004, 24(1):5-34.
[7] Chung F., Lu L. Y., The average distance in a random graph with given expected degrees, Internet Mathematics, 2004, 1(1):91-113.
[8] Cramér H., Sur un nouveau théoreme-limite de la théorie des probabilités, Actual. Sci. Ind., 1938, 736:5-23.
[9] Durrett R., Random Graph Dynamics, Cambridge University Press Cambridge, Cambridge, 2007.
[10] Grimmett G., Percolation, Springer, New York, 1999.
[11] Karinthy F., Chains, Everything is Different, Budapest, 1929.
[12] Levin D. A., Peres Y., Wilmer E. L., Markov Chains and Mixing Times, Amer. Math. Soc. Providence, RI, United States of America, 2009.
[13] Meester R., Roy. R., Continuum Percolation, Cambridge University Press, Cambridge, 1996.
[14] Milgram S., The small world problem, Psychology Today, 1967, 2(1):60-67.
[15] Newman M. E. J., The structure and function of complex networks, SIAM Review, 2003, 45(2):167-256.
[16] Newman M. E. J., Watts D. J., Renormalization group analysis of the small-world network model, Physics Letters A, 1999, 263(4-6):341-346.
[17] Penrose M. D., Pisztora A., Large deviations for discrete and continuous percolation, Advances in Applied Probability, 1996, 28(1):29-52.
[18] Sinclair A., Jerrum M., Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains, Information and Computation, 1989, 82(1):93-133.
[19] Travers J., Milgram S., An Experimental Study of the Small World Problem, Sociometry, 1969, 32(4):425-443.
[20] Watts D. J., Strogatz S. H., Collective Dynamics of "Small-world" Networks, Nature, 1998, 393(6684):440.
[21] Wu X. Y., Mixing Time of Random Walk on Poisson Geometry Small World, Internet Mathematics, DOI:10.1080/15427951, 2015.101208.
[22] Wu X. Y., Zhu R., On the modified Newman-Watts small world and its random walk, arXiv preprint arXiv:1704.01707, 2017.
国家自然科学基金资助项目（11271356，11471222）；北京市自然科学基金（KM201510028002）；首都师范大学交叉科学研究院（19530012012）资助
/
| 〈 |
|
〉 |
