TAILIEUCHUNG - Báo cáo toán học: "Rate of convergence of the short cycle distribution in random regular graphs generated by pegging"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Rate of convergence of the short cycle distribution in random regular graphs generated by pegging. | Rate of convergence of the short cycle distribution in random regular graphs generated by pegging Pu Gao and Nicholas Wormald Department of Combinatorics and Optimization University of Waterloo 200 University Ave W Ontario Canada p3gao@ nwormald@ Submitted Aug 30 2008 Accepted Mar 24 2009 Published Mar 31 2009 Mathematics Subject Classification 05C80 Abstract The pegging algorithm is a method of generating large random regular graphs beginning with small ones. The e-mixing time of the distribution of short cycle counts of these random regular graphs is the time at which the distribution reaches and maintains total variation distance at most e from its limiting distribution. We show that this e-mixing time is not o e-1 . This demonstrates that the upper bound O e-1 proved recently by the authors is essentially tight. 1 Introduction Different random graph models have been applied to analyse the behavior of real-world networks. The most classical and commonly studied one is the Erdos-Renyi model 1 which is the probability space of random graphs on n vertices with each edge appearing independently with some probability p. The properties of the random network degree distribution connectivity diameter etc. vary when p is assigned different values. However the Erdos-Renyi model cannot produce scale-free networks 2 whose degree distribution obeys the power law. The scale-free network caught a lot of attention because a diverse group of networks of interest are thought to be scale-free such as the collaboration network and the World Wide Web. The preferential attachment model was first introduced by Yule 13 and then studied by many other authors 3 7 in an attempt to simulate the properties of such scale-free networks. A new type of peer-to-peer ad-hoc network called the SWAN network was introduced recently by Bourassa and Holt 4 . The underlying topology of the SWAN network is a random regular graph. In the SWAN network clients arrive and .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.