TAILIEUCHUNG - Về một điều kiện đủ cho đồ thị ngẫu nhiên đường kính nhỏ, giúp phân tích mạng thế giới nhỏ

Bài viết đưa ra một cách tiếp cận tổng quát, đề xuất một mô hình đồ thị ngẫu nhiên khái quát, sử dụng tiếp cận “thêm liên kết ngẫu nhiên vào một đồ thị cơ sở” nói trên. Chúng tôi khảo sát mô hình này và cho thấy nhiều mô hình TGN và thiết kế tô-pô cụ thể đã có có thể coi là trường hợp riêng của mô hình phổ quát này. | Về một điều kiện đủ cho đồ thị ngẫu nhiên đường kính nhỏ, giúp phân tích mạng thế giới nhỏ Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 11 (31), tháng 6/2014 Về một điều kiện đủ cho đồ thị ngẫu nhiên đường kính nhỏ, giúp phân tích mạng thế giới nhỏ Analyzing Small-Worlds: A Sufficient Condition for Obtaining Small Diameter in A New Random Graph Model Nguyễn Khanh Văn Abstract: Network structures and graphs that công trình của Milgram trong mạng xã hội dựa trên thí feature the Small-World property have drawn a strong nghiệm chuyển thư giới thiệu để xác lập chuỗi quen interest from the research community in two biết [18]. Watt và Strogatz chính thức đặt nền móng perspectives: 1) The Small-world effect is a popular cho địa hạt nghiên cứu này [22], thu hút sự quan tâm phenomenon amongst several real-world complex từ nhiều giới khác nhau, như toán học và vật lý networks; 2) Small-world graphs are considered very (nghiên cứu về cấu trúc chung), xã hội học (các mạng useful tools to model real-world complex networks as xã hội, ví dụ mạng quan hệ diễn viên, quan hệ đồng well as to design new topologies for certain tác giả, quan hệ qua Facebook), sinh học (các mạng applications in computer networks. We propose to sinh học) và các nhà tin học (Internet và các dạng study a new general random graph model that can be mạng máy tính và cấu trúc tô-pô liên kết). Kleinberg used to analyze the small-world effect (such an đưa ra một mô hình cơ bản khác [10], phát triển từ mô approach is already widely used). Our main result is hình Watt-Strogatz, đem lại một cách nhìn mới cho to construct a general sufficient condition for this hiện tượng này, đậm nét ý nghĩa thuật toán (định tuyến graph model to have logarithmic diameter, . và tìm kiếm thông tin). O(logn) for n as the number of the vertices. This result Các mô hình TGN nói trên đều dựa vào một tiếp can help to assess and analyze several new graphs cận cơ .

• Toán học
• Đồ thị ngẫu nhiên đường kính nhỏ
• Mô hình đồ thị ngẫu nhiên khái quát
• Thiết kế tô pô
• Bất đẳng thức Chernoff
• Mô hình mở rộng NAN