Đề tài Nghiên cứu mạng thư điện tử và ứng dụng trong lọc thư rác

ẽ 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ác node đã tồn tại trong mạng) là tĩnh trong khi tất cả các cung có thể được thêm vào hay sắp xếp lại. Số các node là cố định trong suốt quá trình định hình tiến trình. Thí dụ, WWW vẫn tiếp tục tạo ra những trang web mới. Thứ hai, cả đồ thị ngẫu nhiên và mô hình small-world đều có xác suất không thay đổi khi tạo ra những cung mới nhưng điều này lại không đúng trong thực tế. Bằng quan sát ta có thể thấy những trang web có rất nhiều liên kết (chẳng hạn trang chủ của Yahoo hoặc CNN) rất có khả năng nó sẽ có nhiều trong liên kết đến nữa. Điều này cái gọi là hiện tượng “rich-get-richer”. - 40 - Mô hình BA đưa ra giả thuyết là hai vấn đề chính của việc xây dựng một mạng mang cấu trúc scale-free đó là việc phát triển và ưu tiên gắn kèm. Giả thuyết này đã được chứng minh bằng thực tế bởi hầu hết các mạng tiếp tục phát triển bằng cách thêm các node mới và các node mới được ưu tiên gắn với các node đã tồn tại với một số lớn các kết nối (hiện tượng “rich-get-richer). Tiến trình tạo ra một mô hình BA được tiến hành theo: Thuật toán mô hình BA Scale-Free 1. Khởi tạo: Bắt đầu với một lượng nhỏ mo các node. Lặp lại qua trình tạo các node: một node mới được thêm vào và nó được liên kết với 0mm ≤ các node đã tồn tại 2. Sự gắn thêm ưu tiên: Xác suất ∏i mà 1 node mới sẽ được kết nối với node i (một trong số m node đang tồn tại) phụ thuộc vào cấp ki của node i, hay ∏ ∑=i j ji kk / Sau t lần các bước, kết quả của thuật toán này trong một mạng với N= t+ mo node và mt cung (Hình 2.14). Phát triển theo 2 luật này, mạng phát triển thành trạng thái scale-invariant (rộng bất biến): Hình của độ phân bố không thay đổi trong khoảng thời gian cụ thể và không thay đổi theo sự gia tăng của sự co giãn mạng. Độ phân cụm tương ứng được thể hiện bởi hàm lũy thừa với số mũ 3, đó là xác suất tìm một node có k cung là có tỉ lệ với k-3. Những kết quả bằng số đã xác định rằng, trong sự so sánh với một đồ thị ngẫu nhiên có cùng cỡ và cùng bậc trung bình, đường dẫn của mô hình scale-free có phần nhỏ hơn và độ phân cụm lại cao hơn. Điều này khẳng định sự tồn tại của một vài node mới bậc rất cao (ví dụ, với số lượng liên kết rất lớn) đóng vai trò “chìa khóa” trong việc mang các node khác nhau trong mạng đến gần nhau hơn. Mặc dù, cho tới ngày nay chưa có một công thức tính độ dài trung bình của đường dẫn cho mô hình scale- free. Mô hình BA là mô hình nhỏ nhất sử dụng kĩ thuật đáp ứng cho độ phân bố lũy thừa. Mô hình này có một số giới hạn rõ ràng khi so sánh với một số mạng thế giới thực. Sự theo dõi này có ảnh hưởng trong việc nghiên cứu và phát triển mạng, với mục đích khắc phục những giới hạn trong mô hình BA. Một sự tổng kết của mô hình này đã được Albert và Barabási [2] đưa ra. - 41 - Hình 2.14 Một mạng scale-free gồm 130 node được tạo ra theo mô hình BA scale-free. Năm node lớn nhất có màu đỏ, chúng kết nối với 60% các node khác có màu xanh 2.3 Mạng xã hội (Social Networks) Như đã trình bày ở phần trên, mạng xã hội chính là một ví dụ cụ thể của mạng phức hợp. Nó là thành phần khá lớn và quan trọng trong mạng phức hợp. Một cách cụ thể, mạng xã hội là mạng của một nhóm người hoạt động (actors) và các mối quan hệ gắn kết họ với nhau. Những người hoạt động có thể là những cá nhân hoặc là tập thể (các đơn vị như các phòng ban, các tổ chức, các gia đình...). Những người này trao đổi tài nguyên với nhau và chính điều này đã gắn kết họ lại với nhau trong một mạng xã hội. Tài nguyên ở đây bao gồm dữ liệu, thông tin, sản phẩm và các dịch vụ, hỗ trợ xã hội hoặc hỗ trợ tài chính. Mỗi loại tài nguyên trao đổi được xem như một mỗi liên kết của mạng xã hội và những cá nhân duy trì mối liên hệ này được tương ứng với việc duy trì một nút (tie). Sức bền của nút này được sắp xếp từ yếu đến mạnh phụ thuộc vào số lượng và các kiểu của nguồn tài nguyên họ trao đổi, mức độ thường xuyên trao đổi và sự thân mật trong quá trình trao đổi giữa họ. Các mối quan hệ trao đổi thường được tiến hành trong một số lượng dân số lựa chọn nhất định. Những nhà phân tích trong lĩnh vực mạng dựa vào các quan hệ giữa các thành viên của một cộng đồng, các hàng xóm, một nhóm hoặc một lớp để hiểu cách các mạng xác định dân số hay các nhóm nhỏ bên trong một mạng lớn. Cách - 42 - mà một người kết nối với một người khác thể hiện cấu trúc nền tảng của mạng, bao gồm những người thuộc và không thuộc vào một mạng và các kiểu trao đổi nào để xác định một mạng. Mạng này được duy trì bởi sự trao đổi của các tài nguyên đơn lẻ hay rất nhiều tài nguyên lớn tương ứng với các nút mạnh hay yếu. Ví dụ, các nhà phân tích có thể dò tìm sự trao đổi thông tin về công việc của những người quen biết nhưng không mấy thân thiện, mối quan hệ trong dòng tộc hoặc mối quan hệ giữa những người công nhân. Các mạng xã hội được lần dấu bởi những sự chuyển đổi này chỉ ra cách các nguồn tài nguyên di chuyển trong một mạng, cách mà các actors xác định vị trí để tác động tới nguồn tài nguyên trao đổi và các kiểu của tài nguyên trao đổi rất quan trọng trong những môi trường khác nhau. Hình 2.15 Mô hình mạng xã hội Vấn đề nghiên cứu cấu trúc của mạng xã hội đã gây được sự chú ý và quan tâm sâu sắc của các nhà nghiên cứu trong nhiều năm qua. Đầu tiên là thí nghiệm của Stanley Milgram (1967). Milgram đã bị cuốn hút vào việc khám phá ra độ dài đường dẫn giữa mọi người trong một mạng xã hội trên diện rộng. Mặc dù thí nghiệm của ông đã không toàn diện và đầy đủ song giả thuyết của ông đường kính của các mạng xã hội là nhỏ vẫn còn có giá trị. Trên thực tế, người ta đã tìm hiểu được nhiều mạng xã hội thỏa mãn giả thuyết đường kính nhỏ của Milgram, bao gồm các mạng cộng tác khoa học (Newman [26]) và đồ thị các cuộc gọi điện thoại... - 43 - Sự quan tâm nghiên cứu về mạng xã hội của các nhà khoa học được thể hiện thông qua những phát minh khoa học về mạng xã hội trong nhiều thập kỉ qua. nó được mô hình và phân tích bằng các công cụ lý thuyết đồ thị. Qua những nghiên cứu này, người ta đã chứng mình được mạng xã hội thực có xu hướng có cấu trúc của mạng bất ngẫu nhiên (non-random) ngoài ra nó còn mang hai tính chất nổi bật và quan trọng nhất của mạng phức hợp đó là thuộc tính small-world và thuộc tính độ phân phối theo hàm lũy thừa của mạng scale-free (Albert & Barabasi [2], Strogatz [32]). 2.4 Mạng thư điện tử (Email Networks) Mạng thư điện tử là một loại trong mạng xã hội. Nó là mạng của những người trao đổi thư với nhau. Trong đó, mỗi node của mạng thư điện tử là một địa chỉ email của những người dùng khác nhau và nếu hai người dùng bất kì có sự trao đổi thư với nhau thì sẽ có một cung liên kết nối giữa hai node là địa chỉ tương ứng của hai người dùng này. Mô hình mạng thư điện tử đầu tiên được biết đến là mô hình mạng thư điện tử của H. Ebel, L.-I. Mielsch và S. Bornholdt [11]. Họ đã chỉ ra được rằng mạng trao đổi thư điện tử là mạng có hướng và nó mang cả hai thuộc tính của mạng small-world và mạng scale-free. 2.4.1 Mạng thư điện tử scale-free. Mạng thư điện tử dùng để nghiên cứu của H. Ebel, L.-I. Mielsch và S. Bornholdt được tạo ra từ log files của một máy chủ email tại trường đại học Keil, log files này ghi lại địa chỉ gửi và địa chỉ nhận của mọi thư điện tử từ hoặc tới một tài khoản của các sinh viên trong khoảng thời gian 112 ngày. Hình 2.16 Sự phân bố bậc k của các node trong mạng thư điện tử Mạng bao gồm N=59812 node (bao gồm 5156 tài khoản của sinh viên) với giá trị bậc trung bình của các node là =2.88 và gồm một vài cụm có ít hơn 150 node và một - 44 - thành phần lớn nhất có 56969 node (bậc trung bình =2.96). Sự phân phối bậc của các node tuân theo hàm lũy thừa 81.1)( −∝ kkn với giới hạn số mũ (Hình 2.16). Ví dụ của mạng thư điện tử ở trên giới hạn trong một máy chủ email riêng biệt. Vì thế, bậc của những người dùng của máy chủ email này được nhận biết một cách chính xác. Ở đây, những người dùng bên trong tương ứng với những địa chỉ email của các sinh viên. Các node bên ngoài chính là những node tương ứng với địa chỉ email khác có mối quan hệ với những node bên trong là địa chỉ email của các sinh viên này. H. Ebel, L.-I. Mielsch và S. Bornholdt đã chỉ giải quyết độ phân cụm đối với các các node bên trong (Hình 2.17) và nhận thấy rằng nó có thể được xấp xỉ bởi hàm lũy thừa 32.1int )( −∝ kkn cũng như là giá trị bậc trung bình =14.86. Bậc của các node bên ngoài thông thường bị đánh giá thấp, số mũ này nhỏ hơn so với toàn mạng. Chính vì vậy, có nhiều node có bậc nhỏ trong sự phân bố của toàn mạng (Hình 2.16) từ đó trong sự phân cụm giới hạn với các node bên ngoài (Hình 2.17). Chú ý rằng ngưỡng của cả các độ phân phối là giống nhau. Vì thế, các địa chỉ gửi hầu hết là các node bên trong (ví dụ thư quảng cáo hay thư rác) không được xem là bậc tĩnh. Hình 2.17 Sự phân bố bậc k của các node ứng với địa chỉ email của các sinh viên bên trong máy chủ email 2.4.2 Tính chất Small-world của mạng thư điện tử. Bên cạnh tính chất scale-free, mạng thư điện tử còn mang tính chất của mạng “small-world” [36]. Ví dụ, đối với hai node hàng xóm của cùng một node nào đó thì xác suất mà hai node hàng xóm này có liên kết với nhau là rất cao và tồn tại đường dẫn trung bình rất nhỏ l của một đường dẫn ngắn nhất giữa hai node. Để đánh giá sự phân - 45 - cụm của mỗi mạng người ta dùng độ phân cụm C tương ứng với mỗi mạng này. Độ phân cụm C được định nghĩa như sau: Độ phân cụm vC của node v được đưa ra bằng tỉ lệ tồn tại các liên kết vE giữa vk hàng xóm đầu tiên của nó và tổng số các cung có thể )1(21 −vv kk . Bằng việc tính trung bình các vC của tất cả các node trong mạng cho ta độ phân cụm của mạng. vvv v vv kk ECC )1( 2 −=>=< (2.2) Một định nghĩa đơn giản khác cho độ phân cụm: triplesofnumber triplesconnectedfullyofnumberC __ )____(3×=∆ (2.3) Trong đó, number_of_fully_connected_triples là tổng số các bộ ba node có liên kết cặp đầy đủ với nhau (có ba cung liên kết giữa ba node đó), còn number_of_triples là tổng số bộ ba node mà không đầy đủ các liên kết (chỉ có hai liên kết giữa ba node đó). Nhìn vào công thức (2.2) và (2.3) ta có thể thấy hai công thức này là không tương đương. Công thức (2.2) có ý nghĩa định tính (vật lý) còn công thức (2.3) mang ý nghĩa định lượng. Khi tính toán độ phân cụm của một mạng người ta thường tìm hiểu xem nó có chịu ảnh hưởng bởi độ lớn của mạng không. Với dữ liệu tiến hành thực nghiệm ta không thể bao quát hết được các liên kết của các node bên ngoài với nhau hay nói cách khác mối liên kết giữa các node bên ngoài nói chung là không xác định được. Áp dụng định nghĩa (2.2) và (2.3) đối với mạng ví dụ ở trên người ta tính được độ phân cụm của mạng 21044.3 −×=C và 31015.3 −∆ ×=C . So sánh giá trị này với độ phân cụm của mạng mạng ngẫu nhiên có xác suất nối giữa hai node là p không đổi khi đó độ phân cụm của mạng ngẫu nhiên là pCrand = . Cả hai giá trị C và ∆C đều lớn hơn độ phân cụm trong một mạng ngẫu nhiên thực sự có cùng độ lớn (cùng số node) 51082.4 −×=randC . Giá trị của phân số tính độ phân cụm phân bố bởi phần của các node bên trong thì nhỏ hơn phần của các node bên ngoài bởi vì mạng ví dụ không bao quát hết được những liên kết giữa các node bên ngoài mà những node bên ngoài thì lại chiếm đa phần các node hàng xóm của các node bên trong. Vì vậy, hầu hết các node bên ngoài có một lượng lớn các node bên trong là các node hàng xóm của nó và các node bên ngoài này kết nối với các node bên ngoài khác một cách thưa thớt. Theo định - 46 - nghĩa tính hệ số phân cụm (2.2) và (2.3) thì ∆C nhỏ hơn C thậm chí nó còn nhỏ hơn 2' 1087.1 −×=C là hệ số phân cụm của mạng có cỡ xác định với cùng sự phân bố cấp độ nhưng được gán các liên kết một cách ngẫu nhiên [9]. Theo tính toán với mạng thư điện tử ví dụ này, giá trị đường dẫn trung bình ngắn nhất trong thành phần lớn nhất của mạng được xác định là bằng 03.095.4 ±=l với thuật toán Diskstra [31]. Nó lớn hơn độ dài đường dẫn trong một mạng có độ phân phối bậc của các node là như nhau 43.3' =l [9]. Nó vẫn nhỏ hơn độ dài đường dẫn của mạng ngẫu nhiên 10.10=randl (là mạng mà tất cả các cặp của các node được kết nối với nhau bằng độ lớn xác suất không đổi theo cùng bậc trung bình [9,27]) Điều này có thể giải thích là vì trong mạng thư điện tử có một số node có số lượng các liên kết lớn (hubs) thể hiện tính của mạng scale-free. 2.4.3 Mạng thư điện tử là mạng có hướng Mạng thư điện tử có thể được nghiên cứu như một đồ thị có hướng. Trong mỗi một thư điện tử ta có thể xác định được người gửi và người nhận. Do đó, đường liên kết của hai node có hướng trỏ từ người gửi đến người nhận. Tuy nhiên, ta cũng có thể coi mạng thư điện tử như là một đồ thị không có hướng được đề cập trong nội dung phân tích sự lan truyền của virus được trình bày ở dưới đây. Điều này cũng có vẻ hợp lý bởi bởi vì việc nhận thư và việc gửi thư được điều khiển bởi những tiến trình khác nhau. Hình 2.18 Phân phối in-degree đối với mạng thư điện tử - 47 - Khi xem xét mạng thư điện tử là mạng có hướng, ta có thể xác định chính xác số liên kết node đó với các node bên trong và số liên kết của các node đó với các node bên ngoài. Do đó một lần nữa, việc tính toán độ phân phối bậc đối với của tất cả các node xung quanh và chỉ các node xung quanh ở bên trong lại được đặt ra. Độ phân phối bậc chỉ tính riêng đối với các node hàng xóm bên trong máy chủ email của một node (in-degree) rất giống với độ phân phối bậc tính cho tất cả các node và tính cho các node bên ngoài (Hình 2.18). Chúng đều có thể xấp xỉ bằng hàm lũy thừa 49.1)( −∝ iin . Theo giả thuyết về sự phát triển trong mô hình mạng của Huberman và Adamic [1,17] có thể giải thích vì sao ta có thể chọn số mũ cho hàm phân phối mũ của in-degree nhận giá trị khoảng -1.5 như trên. Họ đề xuất rằng số các liên kết một node nhận tại một thời điểm là một phân số ngẫu nhiên của các liên kết nó vừa được nhận. Đối với các out-degree thì sự phân bố phức tạp hơn. Trong toàn mạng, sự phân bố của các out-degree j tuân theo sự phân bố bậc của mạng scale-free 03.2)( −∝ jjn (Hình 2.19). Mặc dù sự phân phối tương ứng cho các node bên trong là trải rộng nhưng không thể hiện tính chất scale-free như sự phân phối đối với các node bên ngoài. Nguyên nhân của hiện tượng này là do việc giới hạn cỡ của mạng ví dụ nhưng cũng có thể chỉ ra các lỗi có hệ thống gây ra do khả năng các sinh viên sử dụng nhưng account khác (bên ngoài) cho việc gửi email. Độ co dãn của số mũ out-degree của tất cả các mạng nằm trong khoảng khá rộng cho vấn đề truyền thông và các mạng xã hội ví dụ như mạng của các ngôi sao điện ảnh hoặc mạng điện thoại. Hình 2.19 Phân phối out-degree đối với mạng thư điện tử - 48 - 2.4.4 Sự lan rộng của virus trong mạng thư điện tử Hiện tượng lan truyền virus thông qua mạng thư điện tử là một hiện tượng khá phổ biến trong xã hội ngày nay. Môt virus thư điện tử hay một con sâu thư điện tử là một chương trình được đính kèm với một thư điện tử. Khi người nhận mở thư điện tử có chứa sâu thì chương trình email của người nhận sẽ bị điều khiển để gửi lại một số các email nhiễm virus tới các địa chỉ email được tìm thấy trong sổ địa chỉ của người nhận (address book) hoặc trong những email được lưu trữ trong thư mục inbox trong hòm thư của người nhận. Các virus thư điện tử theo cách này sẽ được nhân lên một cách nhanh chóng, do vậy mạng thư điện tử sẽ là vô hướng. Cách lan rộng của các virus theo hình thức này khác với chuỗi thư điện tử (chain email). Đối với chuỗi thư điện tử, trước khi chuyển tiếp chuỗi thư điện tử tới người khác người nhận sẽ bị hỏi có đồng ý chuyển không, nếu đồng ý thì mới chuyển tiếp chuổi thư điện tử tới địa chỉ khác, nếu không đồng ý thì chuỗi thư điện tử sẽ không được chuyển tiếp. Đối với thư virus, người dùng không hề biết việc thư virus này bị gửi tới tất cả những người có trong sổ địa chỉ của mình. Virus thư điện tử có thể là nguyên nhân dẫn đến nhiều sự phá hoại mạng máy tính một cách nghiêm trọng bằng việc pháp hủy dữ liệu trong các máy tính nhiễm virus hoặc gây quá tải trên máy chủ email và một số thiết bị khác. Trong tháng 5 năm 2000, sâu email “I love you” nhiễm tới 500.000 hệ thống riêng rộng và làm tẵc nghẽn 20% số máy ở Đức. Trong các mạng scale-free, ngưỡng cho tỉ lệ lan truyền thư virus thấp hơn nhiều so với việc lan truyền thư virus trong các mạng được khám phá ra trước đây và thậm trí triệt tiêu. Điều này có nghĩa là các cấu trúc tự tổ chức của mạng thư điện tử làm cho việc lan rộng của các virus máy tính cũng như là của bất cứ thông tin nào khác trở nên dễ dàng. Thêm vào đó, trong mạng thư điện tử ta rất hay gặp trường hợp các node ngẫu nhiên trong mạng không hoạt động như mong đợi (failures). Ví dụ, một số người tham gia không trả lời thư điện tử hoặc máy của người nhận có cài chương trình ngăn virus. Kết luận trên của mạng thư điện tử đã gợi ý ra những ứng dụng hữu dụng và có lợi nhưng đồng thời cũng chỉ ra cái nguy hiểm mang tính cố hữu của mạng thư điện tử. Sự bảo mật trong quá trình liên lạc bằng thư điện tử có thể phát triển theo hướng xác định ra địa chỉ trung tâm của các node có lượng liên kết cao và theo dõi chúng để tìm ra địa chỉ lan truyền virus một cách kĩ lưỡng hơn. - 49 - Như vây, mạng thư điện tử là một mạng mà các node được chỉ ra bằng các địa chỉ email và các liên kết bởi sự chuyển đổi giữa các thư điện tử được thừa kế cả hai thuộc tính scale-free và small-world. Mạng thư điện tử có thể được xem như là một mạng không có hướng hoặc có hướng. 2.4.5 Mạng thư điện tử khi bị spam tấn công Mạng thư điện tử thông thường (không bị tấn công bởi các spam) mang các đặc trưng scale-free và small-world, nó không mang tính chất của mạng ngẫu nhiên như đã trình bày ở trên. Khi mạng bị tấn công bởi các spam thì cấu trúc của mạng sẽ thay đổi như thế nào? Không giống như kiểu lan truyền của virus trong mạng thư điện tử là bị gửi một cách tự động cho tất cả những người có trong danh sách địa chỉ hoặc những người được lưu trong thư mục Inbox, spam do một tổ chức gửi với một số lượng lớn tới những đia chỉ người dùng rất ngẫu nhiên. Thông thường các tổ chức gửi thư rác này có một chương trình để tìm địa chỉ thư điện tử của người dùng rồi dùng những địa chỉ tìm ra đó để gửi thư rác do đó những người bị gửi thư rác này thường không có mối quan hệ thân thích gì với nhau. Khi đó, trong mạng thư điện tử bị tấn công bởi spam địa chỉ gửi spam trở thành một node rất đặc biệt. Nó gửi đi một lượng thư lớn tới rất nhiều người ngẫu nhiên (những người không có mối quan hệ gì với nhau) và nó hầu như không nhận thư phản hồi từ người khác. Như vậy, mạng thư điện tử bị tấn công bởi spam là một mạng thư điện tử nhưng có thêm một số node đặc biệt của những địa chỉ gửi thư rác. Như vậy, mạng thư điện tử bị tấn công bởi vẫn mang đặc trưng ban đầu của nó đó là hai đặc trưng của mạng scale-free và small-world. Ngoài ra, do bị ảnh hưởng của những node là địa chỉ gửi spam, mạng mang thêm tính chất của mạng ngẫu nhiên. Tóm lại, trong mạng thư điện tử, các node thông thường có quan hệ thư qua lại với các node hàng xóm của nó trong mạng và giữa các node hàng xóm của node này cũng có quan hệ qua lại thư với nhau còn những node tương ứng với những địa chỉ gửi spam gửi thư rất nhiều mà không nhận thư của ai và giữa các node hàng xóm của node gửi spam này thường ngẫu nhiên và không có mối quan hệ với nhau. Đây chính một đặc điểm khác nhau giữa các node thông thường và các node gửi thư rác. Những đặc điểm khác biệt của các node gửi spam là cơ sở cho phương pháp lọc thư rác bằng bằng đồ thị thư điện tử mà sẽ được trình bày trong chương 3. - 50 - Chương 3 ỨNG DỤNG MẠNG THƯ ĐIỆN TỬ TRONG LỌC THƯ RÁC Phương pháp lọc thư rác được sử dụng phổ biến trong hầu hết các máy chủ email hiện nay đó là phương pháp dựa trên việc thiết lập các quy tắc SpamAssassin và phương pháp thống kê Bayesian. Tuy vậy, các phương pháp này thường chiếm một lượng tài nguyên lớn của máy chủ khi thực hiện quá trình xác minh các thư điện tử gửi đến là thư rác và thư thường, đặc biệt là đối với những máy chủ có nhiều người dùng và lượng thư điện tử trao đổi là lớn. Chương này trình bày một phương pháp lọc thư rác khá hiệu quả và có thể giảm tải việc tính toán cho máy chủ email rất nhiều. Đó là phương pháp lọc thư rác dựa trên việc tính độ phân cụm của mạng thư điện tử. Đây là một hướng tiếp cận mới và đang được các nhà khoa học trên thế giới quan tâm phát triển. 3.1 Yêu cầu của bài toán đặt ra Cuộc chiến tranh giữa những kẻ gửi thư rác và các bộ lọc thư rác dường như không thể chấm dứt. Những người phát triển phần mềm lọc thư rác thì cố gắng tìm hiểu một đặc điểm riêng nào đó của thư rác và dựa trên những đặc điểm này để lọc thư rác. Nhưng những kẻ phát tán thư rác (spammers) thích nghi rất nhanh với các biện pháp ngăn ngừa thư rác, chỉ một thời gian không lâu sau những kẻ gửi thư rác này lại tìm ra được cách khắc phục những đặc điểm đó. Như vậy, nó sẽ trở thành vòng tròn luẩn quẩn. Một bộ lọc tốt phải là một bộ lọc kết hợp được các phương pháp lọc để các phương pháp này có thể phát huy thế mạnh của mình và khắc phục những nhược điểm của các phương pháp khác. Xu hướng của một công cụ lọc thư rác hiệu quả phải đảm bảo một số yêu cầu tối thiểu như: ™ Bộ lọc có thể lọc được nhiều loại thư rác với độ chính xác cao. ™ Tự động cập nhập thêm danh sách các spam mới mà không cần có sự can thiệp của con người. - 51 - ™ Tự động thiết đặt các quy tắc lọc thư rác cho phù hợp đối với từng người dùng hoặc từng tổ chức. 3.2 Đề xuất phương pháp Với những yêu cầu đặt ra như trên, chương này trình bày phương pháp mới có sử dụng các tính chất của mạng thư điện tử để xây dựng công cụ lọc thư rác. Đây là phương pháp sử dụng lý thuyết đồ thị tự động trong việc xác định mạng ứng mỗi người dùng. Một người dùng thư điện tử tương tự như đang sử dụng mạng thư điện tử của anh ta. Mạng này gồm một node tương ứng với anh ta và những node được nhận thư từ anh ta cũng như những node mà anh ta gửi thư đến. Mạng có hướng, với những thư điện anh ta nhận từ người khác thì sẽ có cung hướng từ những người đó tới anh ta, còn những thư điện tử mà anh ta gửi đi tương ững với những cung hướng từ anh ta đến người đó. Số lượng trao đổi thư giữa hai node bất kì trong mạng chính là trọng số của cung nối giữa hai người đó. Ta ký hiệu đồ thị mạng thư điện tử là G = (E, V), trong đó E là tập các đỉnh (địa chỉ người dùng) và V là tập các cung nối các cặp đỉnh trong đồ thị. Một cách phổ biến [6,11,24,25,29], các tác giả thường dùng cách đánh chỉ số cho các đỉnh của đồ thị, vì vậy E là tập các số tự nhiên không vượt quá N, với N là số địa chỉ người dùng trong mạng điện tử. Tính chất quan trọng trưng quan trọng cho mạng xã hội (nói chung) và mạng thư điện tử nói riêng là scale-free và small-world. Theo [11], độ đo scale-free được tính theo số cung gắn với các đỉnh trong đồ thị, mang ý nghĩa về phân bố cung đối với các đỉnh trong đồ thị. Thông thường, số cung gắn với các đỉnh khác nhau là khác nhau. Độ đo scale-free của mạng thường chịu ảnh hưởng nhiều bởi các đỉnh với số lượng lớn các cung liên kết đến. Theo [24], độ đo small-world thể hiện độ dài liên kết giữa các đỉnh trong đồ thị. Độ đo này được tính tương ứng với chiều dài trung bình của đường dẫn ngắn nhất giữa hai đỉnh bất kì. P.O. Boykin và V. Roychowdhury [6] xuất phát theo hướng tiếp cận dựa theo header có trong Inblox của mỗi người dùng. Các tác giả mô hình hóa sự trao đổi thư điện tử của tập người dùng, một mạng thư điện tử, như một mạng social network. Dựa theo ý nghĩa của hai độ đo đặc trưng trên đây, công thức sau đây để tính độ phân cụm của đỉnh thứ i trong mạng thư điện tử được đề xuất: )1( *2 −= ii i i kk E C (3.1) - 52 - Trong đó, Ci là độ phân cụm của đỉnh i, ki số đỉnh kết nối với đỉnh i, Ei là số lượng cung nối giữa các đỉnh láng giềng của i. Tuy nhiên, để tính độ phân cụm cho các đỉnh trong mạng thư điện tử công thức này có một vài hạn chế. Thứ nhất, nó đã bỏ qua tất cả các đỉnh có k = 1. Thứ hai và là quan trọng hơn, kết quả tính toán không cho phép phân biệt được các đỉnh tuy có cùng giá trị E = 0 nhưng có giá trị k khác nhau (C = 0 khi E = 0). Để khắc phục những nhược điểm trên, công thức để tính toán độ phân cụm C được thay đổi như sau: 1)1( )1(*2 +− += ii i i kk E C (3.2) Tuy nhiên, nhằm hướng tới mục tiêu tính toán độ tin cậy của người dùng, công thức trên vẫn chưa thực sự thuyết phục. Thông thường thì những người nhận được nhiều thư là những người có độ tin cậy cao. Nếu sử dụng công thức (3.2) để tính thì vẫn không phân biệt được trường hợp một người gửi thư cho nhiều người khác và trường hợp một người nhận thư từ nhiều người khác. Vì vậy, cần phải xem xét đồ thị thư điện tử trên phương diện có hướng và có trọng số do đó đề xuất công thức tính độ phân cụm mới như sau: i ii i i RSS E C *2.0 1)1( )1(*2 ++− += (3.3) Trong đó, Ei là số cung nối giữa các node xung quanh node i, Si là số node mà có một cung từ node i đến các node này (số node mà được node i gửi thư đến), Ri là số node mà có cung từ các node này đến i (số node gửi thư cho node i). Công thức đảm bảo nếu một người gửi thư cho nhiều node lân cận mà những node lân cận này có mối quan hệ với nhau thì độ phân cụm cao và nếu người này được nhận thư từ các node lân cận khác nữa thì độ phân cụm của người đó càng lớn. Đối với những spam thường không nhận thư nên Ri = 0. Trong một khoảng thời gian dài, người dùng thường trao đổi qua lại nhiều thư với nhau. Số lượng thư trao đổi càng nhiều càng đánh giá mức độ thân quen của họ. Để có một cái nhìn khái quát, em đưa trọng số cung vào để tính toán độ phân cụm. Trọng số cung w của mỗi cung là số lượng thư được trao đổi giữa hai node người dùng. Công thức mới cho các đại lượng Ei, Si, Ri - 53 - ∑ = −+= Edge j ji wE 1 )05.0*)1(1( (3.4) ∑ = −+= Send j ji wS 1 )05.0*)1(1( (3.5) ∑ = −+= cieve j ji wR Re 1 )05.0*)1(1( (3.6) Trọng số cung chỉ có ý nghĩa khẳng định thêm mức độ quan hệ giữa hai node với nhau. Vì thế, chúng tôi chỉ dùng hệ số 0.05 để tạo ra sự chênh lệch không quá lớn. Công thức độ phân cụm mà đưa ra ở trên thể hiện được cả hai thuộc tính scale-free và small-world.của mạng xã hội. Số hạng thứ nhất của công thức (3.3) thể hiện cho tích chất small-world còn số hạng thứ hai của công thức (3.3) thể hiện cho tính chất scale-free. 3.3 Đặc điểm của phương pháp Phương pháp này có một số ưu điểm sau: ™ Anti-spam phát triển theo hướng không phụ thuộc vào nội dung: Phương pháp mà chúng tôi đưa ra khắc phục được nhược điểm của hướng tiếp cận nội dung đó là không can thiệp vào nội dung thư của người dùng. Hơn thế nữa, bộ lọc có thể áp dụng cho bất cứ loại ngôn ngữ của nước nào hoặc với những thư có kiểu đặc biệt (như chèn hình ảnh, âm thanh, website…) mà không cần phải đưa ra những quy tắc riêng cho từng loại. ™ Tự động thiết lập các quy tắc: Phương pháp này khắc phục được nhược điểm của hướng tiếp cận header đó là khả năng tự động thiết lập các quy tắc để tìm ra spammer. Blacklist sẽ được tự động cập nhật thêm những spammer vào mà không cần sự can thiệp của người quản trị. ™ Anti-spam phát triển theo hướng bản địa hóa các quy tắc: một nhóm các quy tắc chỉ dành cho một nhóm server nhất định, được thiết lập chỉ dựa vào dữ liệu của server đó. ™ Giải quyết được vấn đề cold-start: Thời gian mà hệ thống phải học để lọc được thư rác giảm rất nhiều so với các hướng tiếp cận khác. Hệ thống không cần sự can thiệp của người dùng lúc đầu phân loại đâu là địa chỉ tin cậy, đâu là địa chỉ gửi thư rác. Trong khi đó, một số phương pháp lọc thư rác hiệu - 54 - quả (thí dụ Bayesian) phải cần một tập dữ liệu đủ lớn và cập nhật, người dùng phải phân biệt và cho máy học đâu là thư rác, đâu là thư bình thường. ™ Ngăn được sự tấn công của spammers: Những spammers muốn tấn công được hệ thống nó phải làm cho độ phân cụm của nó cao. Tuy nhiên, muốn có hệ số phân cụm cao ngoài việc phải tạo ra mạng có tính chất social network cho nó, nó còn phải được nhận thư từ những người ở bên trong hệ thống và điều này là không thể với một spammer. ™ Giảm sự truy cập tới máy chủ email: Đối với những máy chủ email lớn (thí dụ Yahoo mail, Gmail…) việc giảm tải sự truy cập đến máy chủ là rất cần thiết. Với hướng tiếp cận dựa trên nội dung phải xử lý nội dung của từng thư để xác định spam nhưng phương pháp của chúng tôi chỉ cần xử lý với log files của máy chủ. Như vậy sẽ giảm rất nhiều thời gian cũng như các tiến trình xử lý ở phía máy chủ. - 55 - Chương 4 THỰC NGHIỆM TRÊN LOG FILES Để chứng minh sự đúng đắn của thuật toán đã đưa ra ở chương 3, chương này trình bày thực nghiệm tiến hành trên log files của máy chủ email của Đại học Quốc Gia Hà Nội trong thời gian một tuần và kết quả thu được từ thực nghiệm. 4.1 Đặc điểm dữ liệu Dữ liệu dùng để xây dựng đồ thị mạng thư điện tử được lấy từ log files của một máy chủ email Đai học Quốc gia Hà Nội trong khoảng thời gian một tuần. Từ log files này cung cấp những thông tin về người gửi, người nhận và thời gian của các thư điện tử được gửi đi, nhận về thông qua máy chủ email này. Log files không ghi nội dung thư, vì vậy không xâm phạm đến tính riêng tư của người dùng. Hình 4.1 Đồ thì thư điện tử của máy chủ email của Đại học Quốc Gia Hà Nội (từ ngày 28/3 đến 03/04 năm 2006) - 56 - Sau khi phân tích dữ liệu thống kê được tổng số 19875 người dùng tương ứng với 19875 địa chỉ email khác nhau. Trong đó có 1150 người dùng bên trong máy chủ email và 18725 người dùng ở bên ngoài. Tổng số thư được trao đổi trong khoảng thời gian này là 88842 thư. Từ dữ liệu thu được em xây dựng được đồ thị mạng thư điện tử với mỗi node là một địa chỉ email, một cung có hướng từ node tương ứng với địa chi gửi tới node tương ứng với địa chỉ nhận. Trọng số của cung là số lượng thư ứng với cung đó ở những thời điểm gửi khác nhau. Hình 4.1 minh họa một đồ thị mạng thư điện tử của máy chủ email của Đại học Quốc gia Hà Nội trong khoảng thời gian một tuần từ ngày 28/03 đến ngày 03/04 năm 2006. Hình 4.2 minh họa đồ thị mạng thư điện tử của máy chủ trong một giờ (từ 18:00 đến 19:00 ngày 28/3). Các node màu xanh tương ứng với những người dùng bên trong máy chủ email, các node màu đỏ tương ứng với những người dùng bên ngoài. Chiều của mũi tên cho biết thư được gửi đi từ người gửi đến người nhận. Hình 4.2 Đồ thì thư điện tử của máy chủ email của Đại học Quốc Gia Hà Nội (từ 18:00 đến 19:00 ngày 28/3/2006) - 57 - 4.2 Kết quả thực nghiệm và phân tích Với dữ liệu trên, sau khi tiến hành tính toán độ phân cụm của người dùng bằng công thức(3) chúng tôi thu được kết quả kết quả rất khả quan. Hình 4.3 Biểu đồ độ phân cụm của người dùng bên trong máy chủ email Hình 4.4 Biểu đồ độ phân cụm của người dùng bên ngoài máy chủ email - 58 - Hình 4.3 biểu đồ độ phân cụm của người dùng bên trong máy chủ email. Biểu đồ hiển thị tổng số người dùng ứng với một độ phân cụm nào đó. Hình 4.4 biểu đồ độ phân cụm của người dùng bên ngoài máy chủ email. Biểu đồ biểu thị tổng số người dùng ứng với một độ phân cụm nào đó. Từ biểu đồ hình 4.3 và hình 4.4 cho thấy người dùng bên trong email server thường có độ phân cụm cao (tập trung từ 0 đến 180) trong khi đó người dùng bên ngoài thì độ phân cụm rất thấp (tập trung từ 0 đến 2.5). Hình 4.4 cho thấy một số lượng không nhỏ những người dùng có độ phân cụm rất thấp (từ 0 đến 0.5) đây rất có thể là những địa chỉ gửi thư rác (xem chi tiết trong bảng 2). Giá trị độ phân cụm Tổng số người dùng Người dùng bên trong Người dùng bên ngoài 1.0≤C 653 0 653 5.01.0 ≤< C 1329 15 1314 0.15.0 ≤< C 1734 28 1706 5.10.1 ≤< C 761 33 728 0.25.1 ≤< C 7560 39 7521 5.20.2 ≤< C 6606 309 6297 0.35.2 ≤< C 583 106 477 0.40.3 ≤< C 184 171 13 0.50.4 ≤< C 100 96 4 0.5>C 366 352 14 Bảng 2 Sự phân bố tổng số địa chỉ của người dùng, người dùng bên ngoài và người dùng bên trong máy chủ email theo khoảng giá trị độ phân cụm. Hình 4.5 là đồ thị mạng thư điện tử của một người dùng ở bên ngoài có độ phân cụm thấp C=0.00055. Từ đồ thị ta có thể thấy rõ người này đã phát tán một lượng thư lớn đến rất nhiều địa chỉ khác mà không nhận được thư từ bất kì người dùng nào. Số liên kết giữa những người dùng bị người này gửi thư đến rất ít, chỉ có một liên kết từ người dùng 420 gửi đến người dùng 430 (đây có thể là sự trùng hợp một cách ngẫu nhiên). Do đó ta có thể khẳng định đây là người dùng có độ tin cậy thấp và là một địa chỉ gửi thư rác. - 59 - Hình 4.5 Đồ thị của người dùng bên ngoài máy chủ có độ phân cụm thấp Hình 4.6 Đồ thị người dùng bên trong máy chủ có độ phân cụm cao. Hình 4.6 là đồ thị mạng thư điện tử của người dùng bên trong máy chủ email có độ phân cụm cao C= 20.887. Nhìn đồ thị này ta có thể thấy người dùng này nhận được rất nhiều thư từ người dùng khác và địa chỉ này cũng gửi nhiều thư đi nhưng giữa những người nhận thư từ địa chỉ này có mỗi quan hệ chằng chịt với nhau. Do vậy, độ phân cụm của người dùng này cao hay nói cách khác đây chính là người dùng có độ tin cậy cao và không phải là địa chỉ gửi thư rác. Hình 4.7 là đồ thị mạng thư điện tử của người dùng bên ngoài máy chủ email có độ phân cụm C= 1.7595. Từ đồ thị ta thấy người dùng này gửi thư cho một lượng người không quá lớn và có sự nhận lại thư từ những người gửi đi. Do đó, đây là một địa chỉ email bình thường và không phải là địa chỉ phát tán thư rác. - 60 - Hình 4.7 Đồ thị người dùng bên ngoài máy chủ có độ phân cụm cao 4.3 Nhận xét Từ các hình vẽ và bảng thống kê 2 cho ta thấy, công thức tính độ phân cụm trên rất hợp lý và hiệu quả trong đánh giá độ tin cậy của người dùng trong một máy chủ email. Những người dùng quan trọng (nhận thư từ nhiều node khác và những người họ gửi thư có mối quan hệ với nhau) mạng thư điện tử của họ có độ phân cụm cao. Ngược lại, mạng của người dùng không quan trọng có độ phân cụm thấp. Đặc biệt, với những node tương ứng với spammers thì mạng thư điện tử có độ phân cụm rất thấp. Kết quả hậu kiểm trực tiếp đã khẳng định tính đúng đắn của đánh giá nhận xét trên đây. Từ kết quả trên có thể xây dựng được một công cụ lọc thư rác hiệu quả bằng cách xác định hai ngưỡng của độ phân cụm C. Ngưỡng thứ nhất gọi là Cspam Nếu node nào có độ phân cụm nhỏ hơn Cspam thì địa chỉ ứng với node ấy chính là địa chỉ gửi thư rác. Ngưỡng thứ hai gọi là Cham. Nếu node nào có độ phân cụm lớn hơn Cham thì địa chỉ ứng với node đó là một địa chỉ tin cậy không phải là địa chỉ gửi thư rác. Những địa chỉ tương ứng với các node có độ phân cụm nhỏ hơn Cspam sẽ bị đưa vào Blacklist. Ngược lại, những địa chỉ tương ứng với các node có độ phân cụm lớn hơn Cham được đưa vào Whitelist. Những địa chỉ tương ứng với những node còn lại ( Cspam < C < Cham) được đưa vào Greylist để theo dõi trong thời gian tiếp theo. - 61 - Kết luận Lọc spam bằng phương pháp dùng mạng thư điện tử là một hướng mới và khắc phục được nhiều nhược điểm cố hữu của các phương pháp trước đây. Hướng tiếp cận này đặc biệt hiệu quả trong việc sử dụng làm bộ lọc cơ sở cho việc giải quyết một cách tổng quát cho vấn đề thư rác trong trường hợp đòi sự chính xác cao nhưng không giải quyết được bằng những bộ lọc dựa trên nội dung. Trên thực tế, hiện tại địa chỉ email có thể được làm giả, có nghĩa là spam có thể giả danh địa chỉ email tin cậy, tuy vậy khi các phương pháp SPF, Domain-keys, CallID được áp dụng rộng rãi (đây là xu hướng phát triển của anti-spam), mọi địa chỉ email của người gửi sẽ là địa chỉ email thật. Vì vậy, để có một công cụ lọc thư rác này thực sự hiệu quả cần kết hợp thêm với các phương pháp khác. Khóa luận đã hệ thống hóa một số vấn đề lý thuyết về thư rác, các hướng tiếp cận trong vấn đề lọc thư rác trước đây đồng thời trình bày một số khái niệm và đặc điểm của các mạng phức hợp, mạng xã hội và mạng thư điện tử. Một cách tính mới cho độ phân cụm của mạng thư điện được đề xuất, quá trình tiến hành thực nghiệm đối với cách tính mới này và đã thu được một số kết quả rất khả quan. Với kết quả thu được, dự định trong thời gian tới sẽ tiến hành thử nghiệm tích hợp chương trình lọc thư rác này vào máy chủ email của Đại học Quốc Gia Hà Nội. Kết quả của khóa luận đóng góp vào đề tài nghiên cứu cơ bản và đề tài cấp nhà nước về lọc nội dung trên Internet. - 62 - Tài liệu tham khảo [1] LA Adamic and BA Huberman. “Power-law distribution of the World Wide Web”. Science, 287:2115a, 2000 [2] R. Albert and A-L. Barabási, “Statistical mechanics of complex networks”, Review of Modern Physics, vol. 74, pp. 47-91, January 2002. [3] R. Albert, H. Jeong and A.-L. Barabási, “Diameter of the World Wide Web,” Nature, vol. 401, pp. 130-131, Sept. 1999. [4] A-L. Barabási and R. Albert, “Emergence of scaling in random networks”, Science, vol. 286, pp. 509-512, Oct. 1999. [5] A-L. Barabási, R. Albert and H. Jeong, “Mean-field theory for scalefree random networks”, Physica A, vol. 272, pp. 173-187, 1999. [6] P.O. Boykin and V. Roychowdhury (2005). Leveraging social networks to fight spam. IEEE Computer, 38(4):61–68, 2005. [7] R. F. i Cancho, C. Janssen and R. V. Sole, “Topology of technology graphs: small world patterns in electronic circuits”, Phys. Rev. E, vol. 64, 046119, Sept. 2001. [8] R. F. i Cancho and R. V. Sole, “The small-world of human language”, Proc. R. Soc. London, Ser. B, vol. 268, no. 1482, pp. 2261 - 2265, 2001 [9] J. Davidsen, H. Ebel, and S. Bornholdt, “Emergence of a small world from local interaction: Modeling acquaintance networks”, Phys. Rev. Lett. 88, 128701 (2002) [10] Deborah Fallows (2003). Spam: How it is hurting email and degrading life on the internet. Technical report, Pew Internet and American Life Project, Oct 2003. [11] H. Ebel, L-I. Mielsch and S. Bornholdt (2002). Scale-free topology of email networks, Phys. Rev. E, 66, 035103 (R), Sept. 2002. [12] P. Erdös and A. Rényi, “On the evolution of random graphs”, Publ. Math. Inst. Hung. Acad. Sci., vol. 5, pp. 17-60, 1959. [13] M. Faloutsos, P. Faloutsos and C. Faloutsos, “On power-law relationships of the Internet topology”, Comput. Commun. Rev., vol. 29, pp. 251- 263, 1999. [14] J. Golbeck and J. Hendler (2004). Reputation Network Analysis for Email Filtering. Proc. of the Conference on Email and Anti-Spam (CEAS), Mountain View, CA, USA, July 2004. [15] A. Gray and M. Haahr. Personalised (2004). Collaborative Spam Filtering. Proc. of the Conference on Email and Anti-Spam (CEAS), Mountain View, CA, USA, July 2004. - 63 - [16] Guanrong Chen “Complex networks: Modelling, control and synchoroniation” , Science, vol. 208, no. 554, pp. 824-827, Oct. 2003. [17] BA Huberman and LA Adamic, "Growth dynamics of the world-wide web," Nature 401, 131 (1999) [18] H. Jeong, B. Tombor, R. Albert, Z. Oltvai, and A.-L. Barabási, “The large-scale organization of metabolic networks,” Nature, vol. 407, pp.651-653, Oct. 2000. [19] Medina, I. Matta, J. Byers, “On the origin of power-laws in Internet topologies”, ACM SIGCOMM Comput. Commun. Rev., vol. 30, no. 2, 18-28, 2000. [20] Mehran Sahami, Susan Dumais, David Heckerman and Eric Horvitz (1998). A Bayesian Approach to Filtering Junk Email. Proceedings of AAAI-98 Workshop on Learning for Text Categorization. [21] S. Milgram, “The small-world problem”, Psychology Today, vol. 2, pp. 60-67, 1967 [22] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U.Alon, “Network motifs: Simple building blocks of complex networks”, Science, vol. 298, no. 5594, pp. 824-827, Oct. 2002. [23] J. M. Montoya and R. V. Solé, “Small-world patterns in food webs”, J.Theor. Biol. vol. 214, 405-412, 2002. [24] M. E. J. Newman and D. J. Watts, “Renormalization group analysis of the small-world network model”, Phys. Lett. A, vol. 263, pp. 341-346, 1999. [25] M. E. J. Newman, S. Forrest, and J. Balthrop (2002), “Email networks and the spread of computer viruses”. Physical Review E 66, 2002. [26] M. E. J. Newman, “Scientific collaboration networks: I. Network construction and fundamental results”, Phys. Rev. E, vol. 62, 016131, 2001. [27] MEJ Newman, SH Strogatz and DJ Watts, “Random graphs with arbitrary degree distributions and their applications”, Phys. Rev. E 64, 026118 (2001) [28] R. Pastor-Satorras and A. Vespignani, “Immunization of complex networks”, Phys. Rev. E65, 036104 (2002) [29] Paul Alexandru Chirita, J¨org Diederich, Wolfgang Nejdl (2005). MailRank: Using Ranking for Spam Detection. CIKM ’05 Bremen, Germany [30] M. Perone (2004). An overview of spam blocking techniques. Technical report, Barracuda Networks, 2004. [31] Kenneth H. Rosen, “Handbook of Discrete and Combinatorial Mathematics”, CRC Prss, Boca Raton, 2000 - 64 - [32] S. H. Strogatz, “Exploring complex networks”, Nature, vol. 410, pp. 268-276, March 2001 [33] S. Valverde, R. Ferrer-Cancho and R. V. Sole, “Scale-Free Networks from optimal design”, arXiv: cond-mat/0204344, April 2002. [34] A. Vazquez, R. Pastor-Satorras and A. Vespignani, “Internet topology at the router and autonomous system level”, arXiv: cond-mat/0206084, June 2002. [35] X. F. Wang, “Complex networks: topology, dynamics and synchronization”, Int. J. Bifurcation & Chaos, vol. 12, no. 5, pp. 885-916, May 2002. [36] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small world’ networks”, Nature, vol. 393, pp. 440-442, June 1998. [37] R. J. Williams, N. D. Martinez, E. L Berlow, J. A. Dunne and A-L. Barabasi, “Two degrees of separation in complex food webs”, Proc. Natl.Acad. Sci, vol 99, no. 20, 12913-12916, Oct. 2002. [38] G.L. Wittel and S.F. Wu (2004). On Attacking Statistical Spam Filters. Proc. of the Conference on Email and Anti-Spam (CEAS), Mountain View, CA, USA, July 2004. [39] Spam Filtering Research