Khóa luận Nghiên cứu mạng thư điện tử và ứng dụng trong lọc thư rác

dường như là thể không thể. Bởi, cuộc chiến không ngừng giữa những tên gửi thư rác và những bộ lọc làm cho siêu bộ lọc thư rác của hôm nay có thể trở thành cái lỗi thời của ngày mai. Bộ lọc thư rác mạnh nhất sẽ là bộ lọc sử dụng kết hợp nhiều bộ lọc khác, hoặc tất cả các thuộc tính đã liệu kê ở trên đây. - 26 - Chương 2 KIẾN THỨC CƠ SỞ Bản chất của việc lọc thư rác dựa trên phương pháp mạng xã hội là việc áp dụng các tính chất của đồ thị của mạng, cấu trúc của mạng để tính được độ phân cụm của các thành phần của của các node mạng, từ đó có thể đánh giá được thành phần ứng với node nào là th0ư rác. Chương này trình bày một cách cơ sở và về nguồn gốc cấu trúc của các mạng liên quan, là cơ sở khoa học của phương pháp lọc thư rác sẽ được đưa ra ở phần sau. 2.1 Mạng phức hợp (Complex Networks) Trong một vài năm gần đây người ta đã bắt đầu nhận thấy được tầm quan trọng của mạng phức hợp (Complex Networks) trong nhiều lĩnh vực trong khoa học cũng như trong đời sống của xã hội hiện đại. Việc nghiên cứu về mạng phức hợp cũng được khuyến khích và đã có rất nhiều nhà khoa học, nhà nghiên cứu trên thế giới quan tâm và tìm hiểu về mạng phức hợp. Theo biểu đồ thống kê (Hình 2.1) cho thấy số lượng bài báo nghiên cứu về mạng phức hợp đã gia tăng một cách đột biến trong những năm gần đây [16]. Hình 2.1 : Biểu đồ số lượng bài báo nghiên cứu về mạng phức hợp - 27 - Mạng phức hợp là một tập các hệ thống được tạo bởi các yếu tố đồng nhất hoặc không đồng nhất kết nối với nhau thông qua sự tương tác khác nhau giữa các yếu tố này và được trải ra trên diện rộng. Chúng có mặt ở khắp nơi trong tự nhiên và trong xã hội. Trong thực tế, có rất nhiều hệ thống trong tự nhiên có thể miêu tả thông qua các mô hình của mạng phức hợp. Đó là những hệ thống có cấu trúc gồm các node (hay các đỉnh) gắn với nhau thành một mạng bởi các liên kết (hoặc các cung). Thí dụ như: mạng Internet là mạng của các router hoặc các domain (Hình 2.2); mạng World Wide Web (WWW) là mạng của những trang web (Hình 2.3); bộ não chính là mạng của các nơron thần kinh (Hình 2.4); một tổ chức là mạng của những thành viên trong tổ chức; nền kinh tế toàn cầu là mạng của kinh tế của các nước thành phần, nền kinh tế mỗi nước lại là một mạng các thị trường, mỗi thị trường lại là một mạng tương tác giữa những sản phẩm hàng hóa và người tiêu thụ; Web thức ăn (Food Web) (Hình 2.5) và những đường trao đổi chất cũng có thể biểu diễn bởi một mạng (Hình 2.6); mạng của các chất hóa học (liên kết với nhau bởi các phản ứng hóa học); mạng ngôn ngữ (thí dụ như mạng đồng âm khác nghĩa, mạng đồng nghĩa); các mạng lưới điện cao thế (Electrical Power Grid); các chủ đề của một buổi nói chuyện và thậm chí việc vạch kế hoạch cho xử lý một vẫn đề toán học nào đó cũng có thể mô hình bằng một mạng.... Hình 2.2 Mạng Internet Hình 2.3 Mạng World Wide Work Hình 2.4 Mạng Nơron Hình 2.5 Mạng Food web - 28 - Nếu quan sát bằng trực quan ta có thể thấy chúng được thường xuất hiện một cách hỗn loạn, mang tính chất phức tạp cố hữu (cấu trúc rắc rối, tính đa dạng trong liên kết). Hình 2.6 Mạng trao đổi chất Mạng phức hợp được ứng dụng rất nhiều trong tự nhiên cũng như trong khoa học và công nghệ. Chính vì vậy, việc tìm hiểu về mạng này và tìm ra cấu trúc phù hợp để trên cơ sở đó xây dựng được một hệ thống mạnh, hiệu quả nhưng đơn giản là rất cần thiết. Liên qua đến vấn đề này, nhiều câu hỏi đã được đặt ra như: tại sao bệnh tật lại có thể lan truyền thông qua cấu trúc của mạng xã hội hay thế nào là một kiến trúc phù hợp và thuận tiện cho một tổ chức chuyên biệt... Những vấn đề đặt ra này chính là những vấn đề bức thiết trong cuộc sống đòi hỏi câu trả lời và các giải pháp thích hợp. Hơn một thế kỉ qua, mô hình các hệ thống vật lý cũng như là các hệ thống phi vật lý và các quy trình được tiến hành với giả định rằng các kiểu tương tác giữa các thành phần riêng lẻ của hệ thống và các quy trình đó có thể nhúng được vào một cấu trúc thông thường và phổ biến như lưới Ơ-clít (Euclidean lattice). Vào cuối những năm 1950, hai nhà toán học Erdös and Rényi (ER) đã tạo ra một bước ngoặt mang ý nghĩa đột phá về lý thuyết đồ thị trong thuật toán cổ điển. Hai ông đã mô phỏng được một mô hình mạng với cấu trúc hình học phức tạp bằng đồ thị ngẫu nhiên (Random Graph) [12]. Công trình nghiên cứu này không chỉ có ý nghĩa đặt nền móng cho lý thuyết về mạng ngẫu nhiên (Random Networks) mà nó còn mở ra cho nhiều phát minh và nghiên cứu sau này. Trong 40 năm tiếp theo và thậm chí cho tới tận ngày nay, mô hình ER của hai ông vẫn còn mang ý nghĩa sâu sắc và được ứng dụng trong nhiều lĩnh vực của khoa học và đời sống. Mặc dù, bằng quan sát thực tế ta có thể thấy rõ nhiều mạng phức hợp trong cuộc sống thực (real-life complex networks) - 29 - không hoàn toàn đã là mạng thông thường (Regular Networks) cũng không hoàn toàn là một mạng ngẫu nhiên nhưng mô hình đồ thị ngẫu nhiên ER vẫn là một hướng tiếp cận khá nhạy cảm và thể hiện sự nhìn xa trông rộng của tác giả mà cho đến tận nửa thập kỉ gần đây vẫn tạo được ảnh hưởng sâu sắc đến những nghiên cứu về mạng phức hợp của các nhà khoa học. Trong một vài năm gần đây, hầu hết dữ liệu đã được đưa vào xử lý bằng máy tính và đạt được tốc độ tính toán cao. Hơn nữa, các siêu máy tính còn có khả năng xử lý lượng dữ liệu khổng lồ được biểu diễn bởi nhiều cấu trúc hình học phức tạp của mạng thực. Do đó, việc đáp ứng sự truy cập của cộng đồng đến lượng dữ liệu lớn đó đã thôi thúc những sự quan tâm đặc biệt vào việc cố gắng tìm ra những đặc điểm chung của các loại mạng phức hợp khác nhau. Với sự cố gắng đó, người ta đã khám phá ra hai thuộc tính có ý nghĩa quan trọng của hầu hết các mạng phức hợp đó là hiệu ứng thế giới nhỏ (small-world effect) và đặc trưng co dãn tự do (scale-free feature). Năm 1998, nhằm mô tả sự chuyển tiếp từ đồ thị mạng thường sang đồ thị mạng ngẫu nhiên, hai nhà khoa học Watts và Strogatz (WS) đã đưa ra khái niệm về mạng small-world [36]. Trong cuộc sống đời thường chúng ta cũng có thể bắt gặp hiện tượng small-world này rất nhiều, chẳng hạn ngay sau khi gặp một người lạ mặt rồi cả hai cùng bất ngờ nhận ra rằng giữa họ có mối quan hệ rất gần gũi và cả hai cùng thốt lên “Thế giới này thật nhỏ bé!”. Một hiện tượng khác cũng khá thú vị của biểu hiện small-worlds được nhà tâm lý học xã hội Milgran đề cập tới vào cuối những năm 1960 gọi là nguyên tắc “sáu mức ngăn cách” (six degree of separation)[21]. Mặc dù, nguyên tắc này đã để lại rất nhiều tranh luận sau này, nhưng người ta thấy rằng kiểu biểu hiện của small-world xuất hiện trong hầu hết các mạng thực. Một đặc điểm phổ biến và đặc trưng cho đồ thị ngẫu nhiên ER và mô hình small-world WS là sự phân bố các kết nối giữa các node trong mạng đạt giá trị cực đại tại giá trị trung bình và giảm theo hàm mũ. Những mạng như vậy còn được gọi là mạng hàm mũ (Exponential networks) hay mạng đồng nhất (Homogeneous networks) bởi vì các node trong mạng có số liên kết đến như nhau. Một khám phá gần đây cũng ý nghĩa quan trọng lĩnh vực mạng phức hợp đó là nhiều mạng phức hợp co dãn trên diện rộng (large-scale) là mạng co dãn tự do (scale-free). Kiểu mạng này có phân bố các liên kết trong mạng tuân theo hàm lũy thừa và không phục thuộc vào độ lớn của mạng [4,5]. Không giống với các mạng hàm mũ, mạng scale-free không đồng nhất trong tự nhiên: hầu hết các node trong mạng có một vài liên kết và cá biệt có một số node có rất nhiều liên kết trỏ tới. - 30 - Sự phát hiện hai đặc tính small-world và scale-free của mạng phức hợp chính là “chìa khóa” cho sự phát triển của lý thuyết về mạng phức hợp sau này. Để đánh giá một mạng phức hợp nào đó người ta thường dùng ba độ đo: độ dài đường dẫn trung bình (Average Path Length), độ phân cụm (Clustering Coefficient), độ phân bố bậc (Degree Distribution). 2.1.1 Độ dài đường dẫn trung bình Trong một mạng, gọi ijd là khoảng cách giữa hai node được gắn nhãn lần lượt là i và j. Khi đó, ijd được định nghĩa là số các cung dọc theo đường dẫn ngắn nhất nối giữa node i và j. Từ đó, đường kính D của một mạng được định nghĩa là khoảng cách lớn nhất trong số tất cả các khoảng cách của bất kì hai node nào trong mạng. Độ dài đường dẫn trung bình L của mạng là trung bình khoảng cách của tất cả các cặp node trong toàn mạng. Trong trường hợp này, độ dài đường dẫn trung bình L của một mạng xác định độ lớn hiệu quả của mạng và khoảng cách giữa các cặp node trong mạng đó. Trong mạng của những người bạn (Friendship networks) (Hình 2.7), L là trung bình của số người bạn tồn tại trong chuỗi liên kết ngắn nhất giữa hai người bất kì trong mạng. Bằng thực nghiệm người ta đã chứng minh được rằng độ dài đường dẫn trung bình của hầu hết các mạng phức hợp thực khá nhỏ, thậm chí ngay cả trong trường hợp số cung liên kết của nó ít hơn so với mạng cặp đôi đầy đủ với cùng số node như nhau. Hiện tượng này đã nảy sinh hiệu ứng small-world và do đó cái tên mạng small-world (Small-world Networks) được ra đời. Hình 2.7 Đồ thị mạng những người bạn - 31 - 2.1.2 Độ phân cụm Trong mạng những người bạn (Hình 2.7), khả năng "bạn của bạn của bạn cũng là bạn trực tiếp của bạn" hay nói cách khác, xác suất "hai người bạn của một người trở thành bạn của nhau" là rất cao. Đặc tính này nói lên độ phân cụm của một mạng. Một cách chính xác hơn, độ phân cụm C của một mạng là trung bình của các phân số ứng với từng node i có tử là số liên kết của node i với các node xung quanh và mẫu là số liên kết của các cặp node hàng xóm (neighbors) của node i với nhau. Giả sử, node i trong mạng có ki cung và chúng liên kết với ki node khác. Các node khác này chính là những node hàng xóm của node i. Như vậy, rõ ràng số luợng cung nhiều nhất có thể tồn tại giữa các node hàng xóm của i là 2/)1( +ii kk và điều này chỉ xảy ra khi mọi node trong tập các node hàng xóm này đều có cung liên kết với các node khác trong tập node hàng xóm trên của i. Khi đó, độ phân cụm của node i được định nghĩa là tỉ lệ giữa số cung Ei tồn tại thực sự giữa ki node hàng xóm của i và tổng số cung có thể 2/)1( +ii kk , công thức độ phân cụm ứng với từng node i )1( *2 −= ii i i kk EC (2.1) Độ phân cụm C của toàn mạng là trung bình độ phân cụm Ei của các node i. Từ công thức độ phân cụm trung bình của C ở trên ta có thể thấy 10 ≤≤ C , C=1 nếu và chỉ nếu mạng đó là mạng cặp đôi đầy đủ hay nói cách khác tất cả các node trong mạng đều có cung nối với mọi node còn lại trong mạng, Ci = 0 trong trường hợp Ei = 0 hay giữa các node hàng xóm của i không có liên hệ với nhau. Đối với mạng ngẫu nhiên hoàn toàn gồm N node thì khi đó độ phân cụm NC /1~ , độ phân cụm này khá nhỏ so với độ phân cụm của hầu hết các mạng thực. Bằng thực nghiệm người ta đã chứng minh được rằng độ phân cụm của các mạng thực large-scale có độ phân cụm lớn hơn nhiều so với )/1( NO . Do vậy, hầu hết mạng phức hợp thực không phải là mạng ngẫu nhiên hoàn toàn. Vì vậy, chúng không nên bị coi như là mạng ngẫu nhiên hoàn toàn (Completely random networks) hay mạng lưới cặp đôi đầy đủ (Fully coupled lattices). 2.1.3 Độ phân bố bậc Thuộc tính quan trọng nhất của một node đơn lẻ là bậc của nó. Bậc ki của một node i thông thường được định nghĩa là tổng số liên kết của nó. Do vậy, nếu một node có bậc càng lớn thì node ấy lại càng quan trọng trong mạng, có ý nghĩa quyết định cho - 32 - tính chất của mạng. Trung bình các bậc ki của tất cả các node i gọi là bậc trung bình của mạng và được kí hiệu là . Sự phân bố bậc của các node trong mạng được mô tả bởi hàm phân phối P(k), hàm này cho biết xác suất của một node được chọn ngẫu nhiên có chính xác k cung liên kết (có bậc là k). Một mạng lưới thông thường (Regular lattice) có bậc trung bình đơn giản bởi vì tất cả các node đều có số các cung liên kết bằng nhau và do đó, khi vẽ đồ thị độ phân bố nó là một đường thẳng dốc (theo phân bố delta). Trong giới hạn của mạng ngẫu nhiên hoàn toàn, bậc của các node trong mạng tuân theo phân phối Poisson và đồ thị của phân phối Poisson này tuân theo hàm mũ, và giá trị cực đại đạt tại giá trị trung bình . Trong một vài năm gần đây, nhiều kết quả dựa trên kinh nghiệm đã chứng minh rằng hầu hết các mạng thực large-scale có độ phân phối không tuân theo hàm phân phối Poisson. Một cách cá biệt, đối với một số mạng độ phân bố có thể thể hiện hiệu quả hơn bởi hàm lũy thừa (power-law) P(k)~k-γ. Đặc tính small-world và scale-free là phổ biến đối với nhiều mạng phức hợp thực. Bảng 1 liệt kê một số mạng với các đại lượng đo về chúng. Mạng Cỡ Độ phân cụm Trung bình đường dẫn Độ phân bố Internet, domain level [34] 32711 0.24 3.56 2.1 Internet, router level [34] 228298 0.03 9.51 2.1 WWW [3] 153127 0.11 3.1 γin= 2.1 γout=2.45 Email [11] 56969 0.03 4.95 1.81 Software [33] 1376 0.06 6.39 2.5 Electronic circuits [7] 329 0.34 3.17 2.5 Language [8] 460902 0.437 2.67 2.7 Movie actors [36,4] 225226 0.79 3.65 2.3 - 33 - Math, co- authorship [26] 70975 0.59 9.50 2.5 Food web [23,37] 154 0.15 3.40 1.13 Metabolic system [18] 778 - 3.2 γin= γout= 2.2 Bảng 1 Kiểu small-world và thuộc tính scale-free của một vài mạng thực. Mỗi mạng có số node là N, độ phân cụm C, độ dài đường dẫn trung bình L và số mũ γ của phân phối mũ. Mạng WWW và mạng trao đổi chất được thể hiện bằng đồ thị có hướng. 2.2 Các mô hình của mạng phức hợp Để hiểu được cấu trúc của một mạng phức hợp đầu tiên ta cần phải hiểu được một số tính chất cơ sở của một mạng chẳng hạn như độ dài đường dẫn trung bình L, độ phân cụm C và độ phân phối P(k). Bước tiếp theo, phát triển mô hình thuật toán với cấu trúc hình học của các thuộc tính tĩnh tương tự. Từ đó, có được cơ sở để sự phân tích các thuật toán là có thể. Phần dưới đây trình bày một số mô hình đặc trưng của mạng phức hợp. 2.2.1 Mạng cặp thông thường (Regular coupled networks) Bằng quan sát thực tế ta có thể thấy, mạng cặp đôi đầu đủ (mạng mà các node đều có liên kết với tất cả các node khác trong mạng) có độ dài trung bình nhỏ nhất và có độ phân cụm lớn nhất. Mạng cặp đôi đầy đủ này cũng mang tính chất small-world và large-clustering của nhiều mạng thực nhưng ta có thể dễ nhận thấy giới hạn của nó: một mạng cặp toàn bộ có N node thì sẽ có N(N-1)/2 cung, trong khi hầu hết hầu hết các cung liên kết của các mạng thực large-scale xuất hiện một cách rải rác, đó là các mạng thực không đầy đủ các liên kết. Sau khi nghiên cứu về mạng này, người ta thấy rằng mô hình mạng thông thường là mạng của các cặp đôi của những node xung quanh gần nhất gọi là một lưới (lattice). Lattice là đồ thị thông thường trong đó mọi node được nối lại với nhau bởi một vài các node xung quanh nó. Thuật ngữ “lattice” ở đây có thể đề cập tới một lưới hình vuông hai chiều (Hình 2.8) nhưng có thể có rất nhiều dạng hình học khác nhau. Một lưới lattice tối thiểu là một cấu trúc đơn giản một chiều giống như một hàng người đứng bắt tay nhau. Một lưới lattice của những node xung quanh gần nhất với đường biên xung quanh của N node được xếp thành vòng tròn, mỗi node i được xếp liền kề với các node hàng xóm của nó i=1, 2,..., k/2 vói k là số nguyên chẵn. Nếu với k - 34 - đủ lớn, mạng có độ phân cụm cao, khi đó độ phân cụm của mạng cặp đôi những hàng xóm gần nhất xấp xỉ C=3/4. Hình 2.8 Mô hình lưới Lattice Mạng cặp đôi những hàng xóm gần nhất không phải là mạng small-world, chiều dài trung bình của nó khá lớn và tiến tới vô cùng N → ∞. Điều này lý giải vì sao khó dùng mô hình mạng này để hoàn tất bất kì tiến trình động nào (chẳng hạn, quá trình đồng bộ hóa). Tuy nhiên, đối với mạng thông thường thì các node của nó cũng tồn tại rải rác và bị phân cụm nhưng nó lại có độ dài đường dẫn trung bình khá nhỏ. Một ví dụ đơn giản về mạng phân cặp hình sao trong đó có một node trung tâm và và N-1 node khác được nối trực tiếp với node trung tâm này nhưng giữa N-1 node này không có liên kết với nhau. Đối với loại mô hình mạng kiểu này, độ dài đường dẫn trung bình tiến tới 2 và độ phân cụm tiến tới 1 khi N → ∞. Mô hình mạng hình sao cũng mang tính chất rải rác, phân cụm, small-world và một số thuộc tính khác của nhiều mạng thực. Chính vì vậy, theo hướng này thì mô hình mạng hình sao tốt hơn là các lưới lattice thông thường và nhiều mạng thực nổi tiếng khác. Nhưng rõ ràng hầu hết các mạng thực không có dạng hình sao chuẩn. 2.2.2 Đồ thị ngẫu nhiên (Random Graphs) Đối lập với hình ảnh cuối cùng của một mạng thông thường ở trên là một mạng với đồ thị ngẫu nhiên hoàn toàn. Mạng đồ thị ngẫu nhiên này được Erdös và Rényi (ER) nghiên cứu và phát minh ra cách đây 40 năm [12]. - 35 - Giả thiết rằng bạn có một số N rất lớn (N >> 1) các nút đặt rải rác trên sàn nhà. Bạn buộc hai nút bất kì với xác suất p thành các cặp nút bằng một sợi dây. Khi đó, tổng số cung là pN(N-1)/2 (Hình 2.9). Mục tiêu chính của lý thuyết đồ thị ngẫu nhiên là để các định tại liên kết nào xác suất p của một thuộc tính cụ thể của đồ thị sẽ xuất hiện gần như là nhiều nhất. Một điều khá đặc biệt đó là các tính chất chính và quan trọng của các đồ thị ngẫu nhiên có thể xuất hiện khá đột ngột. Ví dụ, nếu bạn nâng một nút lên liệu sẽ có bao nhiêu nút bị nâng theo? ER chỉ ra rằng nếu xác suất p lớn hơn một ngưỡng pc nào đó pc~(lnN)/N thì hầu hết mọi node trong đồ thị ngẫu nhiên là được kết nối, điều này có nghĩa là bạn sẽ nhặt tất cả các nút bằng cách nâng một nút lên. Hình 2.9 Sự phát triển của một đồ thị ngẫu nhiên: khởi tạo 10 node trong(a), nối các cặp node với xác suất p=0.1 trong (b), p= 0.15 trong (c) và p= 0.25 trong (d). Bậc trung bình của một đồ thị ngẫu nhiên là pNNpk ≅−>=< )1( . Gọi Lrand là độ dài đường dẫn trung bình của mạng ngẫu nhiên. Bằng quan sát ta có thể thấy sẽ có randLk >< các node trong mạng ngẫu nhiên có khoảng cách Lrand hoặc rất gần với nó. Do vậy, randLkN >< kNLrand /ln~ . Sự gia tăng của hàm - 36 - loga trong độ dài đường dẫn trung bình với độ lớn của mạng là một ảnh hưởng phổ biến của small-world. Bởi vì lnN tăng chậm so với N, nó cho phép chiều dài trung bình phải khá nhỏ thậm chí ngay cả trong một mạng khá lớn. Mặt khác, trong mạng ngẫu nhiên hoàn toàn (ví dụ mạng của những người bạn thân) xác suất mà hai người bất kì của bạn là bạn của nhau không lớn hơn xác suất hai người được trọn ngẫu nhiên trong mạng của bạn là bạn của nhau. Vì thế, độ phân cụm của mô hình ER là 1/ =<= NkpC . Điều này có nghĩa là mạng ngẫu nhiên trên diện rộng nói chung là không bị phân cụm. Trong thực tế, với N lớn thuật toán ER sinh ra một mạng đồng nhất có các liên kết tuân theo phân phối Poisson (Hình 2.10). Hình 2.10 Phân bố Poisson Hình 2.11 Phân bố hàm lũy thừa 2.2.3 Các mô hình Small-world Như đã đề cập ở trên, những mạng lưới (lattice) thông thường bị phân cụm nhưng nhìn chung nó không thừa kế đặc tính small-world. Mặt khác, đồ thị ngẫu nhiên có tính chất small-world nhưng lại không bị phân cụm. Chính vì thế, cả mô hình lưới thông thường và mô hình ngẫu nhiên ER đều không thỏa mãn trong việc xây dựng lại một số thuộc tính quan trọng của của nhiều mạng thực. Xét một cách tổng quát, hầu hết những mạng thế giới thực cũng không hoàn toàn thông thường, cũng không hoàn toàn ngẫu nhiên. Sự thật là mọi người thường biết những hàng xóm của họ nhưng cái “vòng tròn” của những người quen của họ có thể bị hạn chế đối với những người sống bên cạnh phía bên phải giống như mô hình lưới lattice được đề cập ở trên. Bên cạnh đó, những tình huống giống như những liên kết giữa các trang web trong mạng World Wide Web cũng không được tạo bởi mô hình ngẫu nhiên hay tiến trình ER như mong đợi. - 37 - Nhằm mục đích miêu tả sự chuyển đổi từ lưới lattice thông thường sang một đồ thị ngẫu nhiên, Watts và Strogatz [36] đã đưa ra mô hình mạng được gọi là mạng small-world. Mô hình WS được sinh ra giống như Hình 2.12. Hình 2.12 Trong mạng những người bạn thân thông thường (a), mọi người là bạn chỉ với 4 người hàng xóm gần nhất. Trong mạng small- world (b), trung bình một người biết 4 người khác nhưng những người này có thể không phải là những người gần nhất. Trong mạng ngẫu nhiên (c), trung bình mỗi người vẫn biết 4 người khác nhưng 4 người này ở vị trí rải rác Thuật toán của mô hình WS Small-world. Khởi đầu theo thứ tự: Bắt đầu với mạng phân cặp nearest- neighbor bao gồm N node được sắp vào một vòng tròn, các node i sắp kề sát các node hàng xóm của nó, i=1,2,3,...,K/2 với K là số nguyên chẵn Ngẫu nhiên hóa các liên kết: Nối các cặp đỉnh một cách ngẫu nhiên bằng một cung với xác suất p, thay đổi giá trị của p trong khoảng từ p=0 đến p=1 để có kết quả giám sát tỉ mỉ. Việc nối các đỉnh ở trong nội dung trên có nghĩa là làm thay đổi một đầu cuối của liên kết tới một node được chọn một cách ngẫu nhiên từ cả mạng với ràng buộc bất kì hai node khác nhau không thể có hơn một liên kết giữa chúng và không có node nào liên kết với chính nó. Tiến trình này tạo ra pNK/2 các cung có sắp xếp dài, các cung này liên kết tất cả các node với nhau và nó cũng có thể là một phần của những node hàng xóm khác. Đối với hệ số phân cụm C(p) và độ dài đường dẫn trung bình L(p) - 38 - trong mô hình WS có thể được xem như một hàm cho việc nối các đỉnh với xác suất p. Một lưới lattice tròn thông thường (p=0) có độ phân cụm cao ( 4/3)0( ≅C ) nhưng nó có độ dài đường dẫn trung bình dài ( 1)0( 2 >>≅ KNL ) (Hình 2.11). Người ta đã chứng minh rằng, đối với một mạng có xác suất liên kết p nhỏ khi mà các thuộc tính cục bộ của mạng vẫ gần giống với những thuộc tính của mạng thông thường nguyên thủy, và khi độ phân cụm không lớn hơn nhiều so với giá trị khởi tạo của nó ( )0(~)( CpC ) thì độ dài đường dẫn trung bình giảm nhanh chóng giống như trong các mạng ngẫu nhiên( )0()( LpL >> ) (Hình 2.13). Đây là một kết quả nghiên cứu thực nghiệm trong tự nhiên. Một mặt có thể tạo một vài liên kết ngẫu nhiên để giảm đáng kể độ dài đường dẫn trung bình. Mặt khác, một vài kết nối đã được tạo ra thì không thể thay đổi thuộc tính phân cụm địa phương của mạng. Hình 2.13 Độ dài đường dẫn trung bình và độ phân cụm của mô hình WS small-world Mô hình small-world cũng có thể được xem như mạng đồng nhất trong đó tất cả các node có số cung xấp xỉ bằng nhau. Với sự tôn kính tác giả, mô hình WS small- world được tạo ra giống với mô hình đồ thị ngẫu nhiên ER. Những công trình nghiên cứu trên mạng small-world WS đã mở ra những nghiên cúu trên những mô hình mới của mạng phức hợp, bao gồm một số sự biến đổi của mô hình WS. Một sự biến đổi phổ biến đã được đề xuất bởi Newman và Watts [24] được biết đến như là mô hình NW small-world. Trong mô hình NW, không thể phá vỡ được liên kết giữa hai node hàng xóm gần nhất nhưng thay vì đó có thể thêm với xác suất p một liên kết p nối giữa các cặp node. Tương tự như trên, trong mô hình này không cho phép một node kết cặp với một node khác hơn một lần và không kết cặp với chính nó. Với p=0, mô - 39 - hình NW giảm so với mạng kết cặp nearest-neighbor và nếu p=1 nó trở thành mạng cặp đôi đầy đủ. Mô hình NW có phần dễ hơn trong phân tích so với mô hình WS nguyên thủy bởi vì nó điều khiển sự tạo thành của các cụm biệt lập, ngược lại điều này lại có thể xảy ra thực sự trong mô hình WS. Với p đủ nhỏ và N đủ lớn, mô hình NW về cơ bản là tương đương với mô hình WS. Ngày nay, hai mô hình này cùng nhau là mô hình nguyên thủy của mô hình small-world một cách phổ biến. Mô hình Small-world đóng vai trò chủ chốt trong các mạng xã hội, nơi mà hầu hết mọi người đều là bạn bè với những người hàng xóm ngay bên cạnh, ví dụ những người hàng xóm trên cùng một con phố hoặc những người bạn đồng nghiệp trong cùng một văn phòng. Mặt khác, nhiều người có những người bạn cách xa về khoảng cách chẳng hạn những người bạn ở các nước khác nhau sẽ được biểu diễn bởi những cung rất dài được nối trong mô hình WS hoặc bởi kết nối thêm vào như trong mô hình NW. 2.2.4 Các mô hình Scale-free Một đặc trưng phổ biến của đồ thị ngẫu nhiên ER và mô hình WS small-world đó là sự phân bố liên kết của mạng đồng nhất, đạt giá trị cực đại tại giá trị trung bình và giảm nhanh theo hàm mũ. Các mạng như vậy gọi là mạng hàm mũ (exponentially networks). Một khám phá có ý nghĩa gần đây trong lĩnh vực mạng phức hợp là một số các mạng large-scale bao gồm Internet, WWW và mạng trao đổi chất có tính chất scale-free và phân bố liên kết có dạng hàm lũy thừa (Hình 2.11). Để giải thích nguồn gốc của độ phân bố hàm mũ, Barabási và Albert (BA) đã đưa ra một mô hình mạng khác [4,5]. Họ đã tranh cãi là nhiều mô hình mạng hiện nay không thể có đầy đủ cả hai thuộc tính quan trọng nhất của hầu hết các mạng thực. Thứ nhất, các mạng thực là mở (có thể mở rộng) và chúng được tạo thành động bằng cách thêm tiếp các node mới vào mạng nhưng các node khác (cá