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

- 1 - ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Bùi Ngọc Lan NGHIÊN CỨU MẠNG THƯ ĐIỆN TỬ VÀ ỨNG DỤNG TRONG LỌC THƯ RÁC KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUI Ngành: Cơng nghệ thơng tin Hà Nội - 2006 - 2 - ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Bùi Ngọc Lan NGHIÊN CỨU MẠNG THƯ ĐIỆN TỬ VÀ ỨNG DỤNG TRONG LỌC THƯ RÁC KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUI Ngành: Cơng nghệ thơng tin Cán bộ hướng dẫn: Tiến sĩ Trần Quang Anh Cán bộ đồng hướng dẫn: Tiến sĩ Hà Quang Thụy Hà Nội - 2006 - 3 - LỜI CẢM ƠN Đầu tiên, em muốn gửi lời cảm ơn chân thành và biết ơn sâu sắc tới Tiến sĩ Trần Quang Anh (Trường Đại học Thanh Hoa Trung Quốc) và Tiến sĩ Hà Quang Thụy (Trường Đại học Cơng nghệ - Đại học Quốc Gia Hà Nội) đã tận tình chỉ bảo và hướng dẫn em trong suốt quá trình thực hiện khố luận này. Em xin chân thành cám ơn các thầy lãnh đạo Viện CNTT - ĐHQGHN, anh Nguyễn Việt Cường (Trường Đại học Cơng nghệ - ĐHQGHN) và anh Phan Bá Hùng (Viện Cơng nghệ Thơng tin - ĐHQGHN) đã giúp đỡ, tạo điều kiện thuận lợi để em tiến hành cĩ kết quả các thử nghiệm trên mail-server thực. Em xin bày tỏ lời cảm ơn sâu sắc tới các thầy, cơ trong trường Đại học Cơng nghệ đã dạy dỗ và tận tình chỉ bảo cho em trong suốt quá trình học tập tại trường. Em cũng muốn gửi lời cảm ơn tới các thầy cơ, anh chị và các bạn trong nhĩm xê-mi-na “Khai phá dữ liệu và khám phá tri thức” thuộc bộ mơn Các hệ thống thơng tin, Trường Đại học Cơng nghệ đã ủng hộ và khuyến khích em trong quá trình nghiên cứu và thực hiện khố luận này. Và lời cuối cùng, em xin gửi lời cảm ơn chân thành và biết ơn vơ hạn tới bố, mẹ, anh chị những người đã cĩ cơng sinh thành, nuối nấng, dạy dỗ và luơn động viên, khuyến khích em trong cuộc sống, trong học tập và làm việc. Sinh viên Bùi Ngọc Lan - 4 - Tĩm tắt Vấn đề thư rác từ lâu đã gây khơng ít phiền nhiễu cho người sử dụng thư điện tử và là vấn đề đau đầu của những người quản lý mạng. Cĩ rất nhiều giải pháp chống thư rác đã được đưa ra và áp dụng trong thực tế. Tuy nhiên, các phương pháp này đều tỏ ra chưa thực sự hiệu quả và mang những nhược điểm cố hữu của nĩ. Trong luận văn này, trên cơ sở nghiên cứu cấu trúc và các tính chất đặc trương của mạng thư điện tử (Email Networks) từ đĩ đề xuất một phương pháp lọc thư rác mới dựa trên mạng thư điện tử. Khác với phương pháp lọc thư rác dựa trên mạng thư điện tử trước đây [1], phương pháp đưa ra đã khai thác được tính chất cĩ hướng của đồ thị mạng thư điện tử và xem xét đồ thị mạng thư điện tử là đồ thị cĩ trọng số để xây dựng một cơng thức tính độ phân cụm (clustering coefficient) mới. Để kiểm chứng phương pháp đưa ra, khĩa luận thực hiện thí nghiệm trên log files của máy chủ e-mail thực của Đại học Quốc gia Hà Nội. Kết quả thực nghiệm cho thấy được tính đúng đắn của phương pháp và phương pháp này cĩ thể khắc phục được nhiều nhược điểm cố hữu của các giải pháp trước đây. - 5 - Mục lục LỜI CẢM ƠN ............................................................................................3 MỞ ĐẦU.....................................................................................................8 CHƯƠNG 1: TỔNG QUAN VỀ THƯ RÁC .........................................10 1.1 Khái niệm thư rác ............................................................................10 1.1.1 Thư rác là gì ?..............................................................................................10 1.1.2 Các đặc điểm của thư rác. ...........................................................................11 1.1.3 Phân loại thư rác .........................................................................................12 1.1.4 Những thiệt hại do thư rác gây ra................................................................13 1.2 Các giải pháp cho vấn đề lọc thư rác ...............................................16 1.2.1 Ban hành các bộ luật chống thư rác ............................................................16 1.2.2 Các phương pháp lọc thư rác trước đây......................................................16 CHƯƠNG 2: KIẾN THỨC CƠ SỞ .......................................................26 2.1 Mạng phức hợp (Complex Networks) ..............................................26 2.1.1 Độ dài đường dẫn trung bình.......................................................................30 2.1.2 Độ phân cụm ................................................................................................31 2.1.3 Độ phân bố bậc ............................................................................................31 2.2 Các mơ hình của mạng phức hợp ....................................................33 2.2.1 Mạng cặp thơng thường (Regular coupled networks) .................................33 2.2.2 Đồ thị ngẫu nhiên (Random Graphs)...........................................................34 2.2.3 Các mơ hình Small-world ............................................................................36 2.2.4 Các mơ hình Scale-free ................................................................................39 2.3 Mạng xã hội (Social Networks).......................................................41 2.4 Mạng thư điện tử (Email Networks)................................................43 2.4.1 Mạng thư điện tử scale-free. .........................................................................43 2.4.2 Tính chất Small-world của mạng thư điện tử. .............................................44 2.4.3 Mạng thư điện tử là mạng cĩ hướng............................................................46 2.4.4 Sự lan rộng của virus trong mạng thư điện tử .............................................48 2.4.5 Mạng thư điện tử khi bị spam tấn cơng .......................................................49 - 6 - CHƯƠNG 3: ỨNG DỤNG MẠNG THƯ ĐIỆN TỬ TRONG LỌC THƯ RÁC.................................................................................................50 3.2 Đề xuất phương pháp.......................................................................51 3.3 Đặc điểm của phương pháp .............................................................53 CHƯƠNG 4: THỰC NGHIỆM TRÊN LOG FILES............................55 4.1 Đặc điểm dữ liệu..............................................................................55 4.2 Kết quả thực nghiệm và phân tích ...................................................57 4.3 Nhận xét ..........................................................................................60 KếT LUậN...................................................................................................61 - 7 - Bảng từ viết tắt Từ hoặc cụm từ Viết tắt Unsolicited Commercial Email UCE Internet Service Provider ISP Short Message Service SMS Email Service Provider ESP Realtime Black hole List RBL Multiple Address Processing System MAPS eXtensible Markup Language XML Domain Name Server DNS Sender Policy Framework SPF - 8 - MỞ ĐẦU Ngày nay cùng với sự tồn cầu hĩa việc kết nối thơng tin, thư điện tử (Email) đã trở thành một phần quan trọng trong đời sống và trong cả các hoạt động kinh doanh thương mại. Thư điện tử cho phép tiết kiệm thời gian và khắc phục mọi vấn đề về khoảng cách địa lí, về chi phí trong trao đổi thơng tin liên lạc. Chính những thuận tiện trong trao đổi thư điện tử lại tạo ra một số sơ hở để cho các loại thư khơng mong muốn (thư rác: spam mail) hoạt động gây phiền tối cho người dùng. Trong một vài năm gần đây, những thư điện tử khơng mong muốn như vậy phát triển và gây ra khơng ít thiệt hại cho người dùng nĩi riêng và cho nền kinh tế - xã hội nĩi chung. Theo nhiều bản thống kê [10,15], thư rác đã chiếm tới ¾ tổng số thư điện tử lưu thơng trên tồn thế giới. Cĩ khơng ít người dùng đã hạn chế sử dụng thư điện tử như một phương tiện liên lạc, và điều đĩ đã gây ra sự trở ngại đáng kể cho liên lạc giữa các người dùng cũng như hạn chế việc phát sinh lợi nhuận chính đáng của nền kinh tế nhờ phương tiện liên lạc này. Hiện nay, thư rác đang là một trong những vấn đề nhức nhối của xã hội. Nhiều phương pháp, cơng cụ lọc thư rác đã được đề xuất, tuy nhiên nhìn chung các cơng cụ lọc thư rác hiện nay vẫn tỏ ra chưa thực sự hiệu quả. Chính vì lý do đĩ, nhiều hướng tiếp cận lọc thư rác mới đã được đề xuất [39], kể cả các hướng tiếp cận kết hợp các phương pháp khác nhau, trong đĩ hướng tiếp cận theo mạng xã hội là một trong các hướng nổi bật nhất. Ý thức được điều này, hướng nghiên cứu về các phương pháp lọc thư rác, tập trung theo hướng tiếp cận mạng thư điện tử đề tài của khĩa luận với tên gọi "Nghiên cứu mạng thư điện tử và ứng dụng trong lọc thư rác". Khĩa luận được tổ chức thành 4 chương như sau: Chương 1 giới thiệu tổng quan về thư rác và một số hướng tiếp cận điển hình trước đây trong việc lọc thư rác. Chương 2 trình bày về một số tính chất quan trọng của mạng phức hợp, mạng xã hội, mạng thư điện tử. Đây là cơ sở kiến thức để phát triển nội dung của khĩa luận trong các chương sau. Chương 3 trình bày một phương pháp mới ứng dụng các tính chất của mạng thư điện tử vào vấn đề lọc thư rác thơng qua việc tính hạng phân cụm của các địa chỉ thư. Các nội dung đề xuất được trình bày chi tiết trong chương này. - 9 - Chương 4 trình bày về thực nghiệm tiến hành với logs file của máy chủ email tại Đại học Quốc gia Hà Nội. Kết quả thực nghiệm cho thấy địa chỉ thư với độ phân cụm thấp cĩ khả năng cao là địa chỉ thư rác . Phần kết luận tổng kết các kết quả chủ yếu của khĩa luận và phương hướng nghiên cứu tiếp theo để phát triển, cải tiến phương pháp mạng thư điện tử được đề xuất. Cho dù đã cố gắng song khơng thể tránh khỏi những sai sĩt, em rất mong được sự gĩp ý của thầy cơ và các bạn. - 10 - Chương 1 TỔNG QUAN VỀ THƯ RÁC Từ lâu, thư điện tử (Email) đã trở thành một ứng dụng khơng thể thiếu khi Internet và cơng nghệ mạng phát triển. Đây là điều mà thực tế đã chứng minh qua những đĩng gĩp của ứng dụng này trong nhiều lĩnh vực như kinh doanh, thương mại, viễn thơng và các dịch vụ cá nhân. Tuy nhiên trong những năm gần đây, một hình thức mới của thư điện tử đã xuất hiện với số lượng lớn gây phiền hà cho người nhận và những thiệt hại khơng nhỏ cho nền kinh tế gọi là thư rác. Chương này sẽ khái quát các vấn đề về khái niệm thư rác, ảnh hưởng của thư rác trong cuộc sống của chúng ta và các phương pháp ngăn chặn thư rác. 1.1 Khái niệm thư rác 1.1.1 Thư rác là gì ? Thư rác (spam) là một loại thư được gửi với số lượng lớn, theo chủ ý của người gửi, hồn tồn khơng cĩ sự liên hệ gì với người nhận. Đứng trên quan điểm của người gửi, đĩ là một hình thức giửi thư theo số lượng lớn (nên gọi là bulk email) cho một danh sách địa chỉ chọn lọc ra từ các diễn đàn (Usenet discussion group), các danh sách thư (mailing list)… Hiện nay cũng cĩ nhiều cơng ty mà cơng việc kinh doanh chính là nhận gửi thư rác cho khách hàng của họ. Về phía người nhận, đa phần các bức thư này khơng cĩ giá trị và thật sự khơng được mong muốn, chúng bị coi như một thứ rác rưởi, tạp nham (xuất phát từ cụm junk email). Phần lớn các thư này cĩ nội dung quảng cáo thương mại cho một loại sản phẩm hay dịch vụ nào đĩ, những bức thư này được gọi là UCE (Unsolicited Commercial Email). Thư rác hiện nay thường cĩ nội dung: quảng cáo thương mại và dịch vụ, quấy nhiễu, phát tán virus và những nội dung khơng lành mạnh (khiêu dâm, chống phá chính trị…). - 11 - Việc gửi thư rác làm cho người nhận phải mất thời gian và phải trả tiền cho nhà cung cấp dịch vụ Internet ISP (Internet Service Provider) để đọc những bức thư khơng liên quan. Đơi khi những bức thư cĩ chứa virus cĩ thể phá hủy cả hệ thống dữ liệu trong máy tính. Ngồi ra, tài nguyên (đường truyền, máy chủ) của ISP cũng bị chiếm dụng nhiều khi gửi thư rác. 1.1.2 Các đặc điểm của thư rác. Các loại thư rác hiện nay cĩ một số đặc điểm sau: ¾ Thư rác được gửi đi một cách tự động: Mục đích của những kẻ gửi thư rác (spammer) là cĩ thể phát tán lượng thư rác tới người dùng càng nhiều càng tốt. Do vậy, chúng thường viết ra những phần mềm tự động gửi một lượng lớn thư rác trong một khoảng thời gian ngắn. ¾ Thư rác được gửi đến những địa chỉ ngẫu nhiên trên một diện rộng. Địa chỉ email của người bị nhận thư rác rất ngẫu nhiên và dường như giữa họ khơng cĩ mối quan hệ với nhau. Cĩ nhiều phương pháp và thủ thuật khác nhau mà những kẻ gửi thư rác áp dụng trong việc dị tìm địa chỉ email của người dùng như: ƒ Dùng chương trình tự động dị tìm địa chỉ email trên mạng Internet, các trang chủ, Newsgroup, Chat room.... ƒ Mua địa chỉ email từ những cơng ty đã xây dựng danh sách khách hàng của họ nhưng vì lý do nào đĩ phải bán đi hoặc đối tác của cơng ty được phép truy cập danh sách khách hàng của cơng ty này để gửi thơng tin về dịch vụ hay sản phẩm. ƒ Email chuỗi (Chain letter) từ bạn bè và người thân, yêu cầu gửi thư cho càng nhiều người càng tốt vì lý do thương người, ủng hộ một chương trình nào đĩ, hoặc mời chào người dùng nếu gửi cho nhiều người sẽ được nhận nhiều tiền hơn. ƒ Dùng chương trình đốn tên tự động: Những kẻ gửi thư rác dùng chương trình này gửi email liên tục vào một nơi để đốn địa chỉ email qua những phương pháp như E-pending, Dictionary hay Alphabet. Bên cạnh đĩ, những kẻ gửi thư rác cịn cĩ thể cĩ được địa chỉ email của người dùng do: - 12 - ƒ Các nhà cung cấp dịch vụ ISP khơng cĩ chính sách và cơng nghệ bảo mật, dẫn đến các tin tặc (hacker) ăn cắp địa chỉ của khách hàng để buơn bán và quấy nhiễu. Hoặc cĩ thể do chính nhà cung cấp ISP buơn bán địa chỉ email của khách hàng để kiếm lợi nhuận. Nhân viên của các ISP đã tiết lộ thơng tin về khách hàng cho các đối thủ cạnh tranh của chính ISP đĩ, hoặc cho những cơng ty muốn quảng cáo cho những khách hàng riêng biệt. ƒ Chính người dùng cung cấp địa chỉ email của mình qua những lần đăng kí thành viên trên Internet hoặc trên giấy tờ các dịch vụ mà chẳng bao giờ dùng, những cuộc xổ số mà chẳng bao giờ biết quả, hoặc những bản tin điện tử (newsletter) vơ nghĩa. ¾ Nội dung của thư rác thường là những nội dung bất hợp pháp, gây phiền hà cho người dùng. Phần lớn nội dung của thư rác là những thơng tin mời chào về thương mại, quảng cáo sản phẩm. Bên cạnh đĩ, phải kể đến những thư rác cĩ nội dung xấu (như khiêu dâm, chống phá chính trị...) gây tâm lý lo ngại cho người làm cơng nghệ thơng tin. Lượng thư rác phát tán virus cũng khơng nhỏ. Trong những thư này thường được gắn kèm những con virus nguy hiểm cĩ thể làm tê liệt hồn tồn máy tính của người dùng, ăn cắp những thơng tin cá nhân hoặc làm hỏng dữ liệu lưu trên máy. Hiện nay, những thư rác với nội dung hứa hẹn mang đến một khoản tiền lớn cho người đọc thư rác đã tăng nhanh. Những người dùng kém hiểu biết, cả tin thường bị lừa bởi hình thức này. ¾ Địa chỉ của người gửi thư rác thường là những địa chỉ trá hình. Để tránh sự nghi ngờ của người nhận, một số kẻ gửi thư rác thường giả dạng địa chỉ của một người dùng bình thường trong một máy chủ email nào đĩ một cách bất hợp pháp hoặc dùng một địa chỉ ảo nào đĩ để gửi thư rác. 1.1.3 Phân loại thư rác Việc phân loại thư rác rất quan trọng khơng chỉ trong lĩnh vực tạo những bộ lọc thư rác phù hợp cho hiệu quả cao mà cịn giúp cho việc ban hành các bộ luật chống thư rác thích hợp. Cĩ rất nhiều cách phân loại thư rác. Dưới đây là một số loại điển hình nhất. 1> Dựa trên kiểu phát tán thư rác - 13 - Tính tới thời điểm hiện tại, thư rác cĩ thể bị gửi thơng qua những hình thức thư điện tử, nhĩm thảo luận (newsgroups), điện thoại di động (Short Message Service - SMS) và các dịch vụ gửi tin nhắn trên mạng (như Yahoo Messenger, Windows Messenger...). 2> Dựa vào quan hệ với người gửi thư rác Các mối quan hệ với người gửi thư rác bao gồm người lạ mặt, bạn bè, người quen và các dịch vụ quyên gĩp giúp đỡ… 3> Dựa vào nội dung của thư rác. Các kiểu nội dung phổ biến như thư về thương mại, thư về chính trị, thư về cơng nghệ, chuỗi thư (chain email) và các loại khác (như thư phát tán virus...). 4> Dựa trên động lực của người gửi Thơng thường, thư rác được gửi đi cho những mục đích quảng bá thơng tin. Ngồi ra, cịn cĩ một số loại thư rác được gửi tới một người nhận xác định nào đĩ nhằm mục đích phá vỡ và gây cản trở cơng việc của người nhận hay mạng của nhà cung cấp dịch vụ thư điện tử ESP (Email Service Provider) được gọi là “bom thư”. Thư rác cịn được cố ý gửi đi nhằm thơng báo tin sai lệch, làm xáo trộn cơng việc và cuộc sống của người nhận. 1.1.4 Những thiệt hại do thư rác gây ra Các khảo sát cho thấy thư rác hiện chiếm hơn một nửa số email qua lại hàng ngày trên Internet và chính thư rác là nguồn lây lan virus nhanh nhất. Thiệt hại do chúng gây ra rất lớn. Năm 2003, báo cáo của Hội thảo Thương mại và Phát triển của Liên Hiệp Quốc cho thấy thiệt hại do thư rác gây ra khoảng 20,5 tỷ USD. Các hãng diệt virus cũng đưa ra ước tính thiệt hại của các cuộc tấn cơng do virus năm 2001 là 13 tỷ USD, năm 2002 khoảng từ 20 - 30 tỷ USD. Chi phí để khắc phục sự cố do virus gây ra trong các doanh nghiệp được điều tra ngẫu nhiên ở Mỹ năm 2002 là 81.000 USD, đến năm 2003 đã tăng lên 100.000 USD. Trên 3/4 số doanh nghiệp cho rằng sự cố virus đã gây tổn hại nhất định đến năng suất làm việc và 2/3 cho biết ảnh hưởng chủ yếu của mỗi vụ tấn cơng là làm cho máy tính khơng thể truy cập được. Những ảnh hưởng khác của virus là làm hỏng file và khơng thể truy xuất dữ liệu. - 14 - Theo thống kê tồn cầu của hãng nghiên cứu Ferris Research (San Francisco), thư rác gây thiệt hại 50 tỷ USD trong năm 2005. Chỉ tính riêng ở Mỹ, thiệt hại do thư rác gây ra đối với các doanh nghiệp ước tính khoảng 17 tỷ USD/năm. Khơng chỉ gây thiệt hại về tiền bạc, thư rác cịn làm giảm hiệu quả làm việc, gây stress, tiêu tốn thời gian của nhân viên... Những điều này cũng đồng nghĩa với việc, năng suất lao động giảm, ảnh hưởng tới tình hình kinh doanh và doanh thu của cơng ty. Báo cáo mới cơng bố của Tổ chức hợp tác phát triển kinh tế OECD cho thấy thư rác đang là vấn nạn tồn cầu, nhưng ảnh hưởng tới người sử dụng Internet ở thế giới thứ ba (các nước đang pháp triển) nhiều hơn tại các quốc gia phát triển. Theo phân tích của OECD một phần nguyên nhân của việc người sử dụng máy tính ở các nước đang phát triển hay bị virus và thư rác tấn cơng là do họ thường mua hệ điều hành và phần mềm chống virus khơng cĩ bản quyền (do điều kiện kinh tế khơng cho phép) nên khơng thể được cập nhật một cách đầy đủ, khơng đối phĩ với những kỹ thuật liên tục thay đổi của những tên tin tặc (hacker) và những tên gửi thư rác (spammer). Bênh cạnh đĩ phải kể đến nguyên nhân thiếu kiến thức, cơng nghệ và tài chính để đối phĩ với sự gia tăng thư rác trên hệ thống liên lạc trong nước, gây thất thốt đáng kể nguồn lực cơng nghệ vốn đã yếu và thiếu tại những nơi này. Các ISP nội địa thì thiếu những chính sách ngăn chặn và xử lý thư rác, trong khi đĩ, những kênh tiếp vận (relay) và proxy “mở toang” cùng với vơ số máy tính bị nhiễm virus hoặc Trojan trong mạng đã trở thành những nguồn phát tán thư rác lớn. Hậu quả là người sử dụng phải hứng chịu tình trạng bất ổn định dịch vụ, gây cản trở quá trình thu hẹp khoảng cách số tồn cầu. Từ những con số thống kê trên ta cĩ thể thấy, việc thơng qua các chế tài pháp lý quốc tế, đầu tư mạnh vào hệ thống lọc thư rác, thiết lập những trung tâm phản ứng nhanh liên kết các ISP tồn cầu, đồng thời tăng cường các chiến dịch tuyên truyền cộng đồng về sự nguy hại và cách đối phĩ với thư rác là cơng việc rất quan trọng và cần thiết. Ngày nay, spam khơng phải đơn giản chỉ nằm trong thư điện tử mà cịn cĩ cả trong blog1, cịn gọi là spam blogs hay splogs, trên các tin nhắn trực tuyến. Những xu thế này chính là những hình thức mới của spam cĩ thể phát triển nở rộ trong năm 2006. 1 Blog, gọi tắt của weblog (tiếng Anh, "nhật ký web"), là một dạng đàm luận thời sự trực tuyến, bùng nổ từ cuối thập niên 1990. Các bloger(người viết blog), cĩ thể là cá nhân hoặc nhĩm, đưa thơng tin lên mạng với mọi chủ đề, thơng thường cĩ liên quan tới kinh nghiệm hoặc ý kiến cá nhân, chủ yếu cung cấp thơng tin đề cập tới những chủ đề chọn lọc, khơng giống như các báo truyền thống. Một trang blog cĩ thể chứa các siêu liên kết, hình ảnh và liên kết (tới các trang chứa phim và âm nhạc). - 15 - Ngồi ra, luật phịng chống spam và các bộ lọc spam ngày càng chặt chẽ sẽ khiến cho những kẻ gửi thư rác phải thay đổi đối tượng tấn cơng. Để cĩ thể loại bỏ được thư rác, ta khơng thể dùng một phương pháp riêng lẻ nào để loại bỏ tận gốc mà cần áp dụng các phương pháp kết hợp với nhau. Một trong những cách hữu hiệu nhất để chặn spam là giáo dục người dùng cuối. Khi người sử dụng đã cĩ kiến thức thì họ sẽ ít bị rơi vào bẫy do những kẻ phát tán thư rác cố tình giăng ra để khai thác địa chỉ email và duy trì mục đích của chúng. Một số lời khuyên cho người dùng thư điện tử: ƒ Yêu cầu và địi hỏi những nhà chức trách cĩ những luật lệ nghiêm cấm thư rác và cĩ những hình phạt thích đáng cho những kẻ cố tình. ƒ Mỗi người dùng nên dùng nhiều địa chỉ email. Đây là phương pháp khá hiệu quả. Người dùng nên dùng các địa chỉ email khác nhau cho các mục đích khác nhau. Chẳng hạn, tạo một địa chỉ email cho cơng việc, một cho cá nhân, và một để đăng ký các dịch vụ, thơng tin trên internet. Bằng cách này, người dùng cĩ thể suy luận ra được địa chỉ nào bị lộ sau khi đăng ký các dịch vụ và tránh được chúng sau này. ƒ Hạn chế đăng ký các dịch vụ vơ ích. Người dùng nên tìm hiểu và đọc kỹ thơng tin về dịch vụ trước khi cung cấp địa chỉ email của mình, cần chắc chắn là dịch vụ này cho phép lựa chọn “khơng nhận email quảng cáo từ các đối tác của nhà cung cấp dịch vụ”. ƒ Kích hoạt các dịch vụ chống thư rác của ISP. Các ISP thường tích hợp các cơng cụ lọc thư rác cũng như chương trình quét virus. Người dùng nên kích hoạt các dịch vụ này khi dùng Internet. Phương pháp này cũng giúp giảm bớt được phần nào số lượng thư rác phải nhận mỗi ngày. ƒ Cài đặt một số chương trình xử lý thư trong máy tính cá nhân để xĩa thư rác ngay khi chuyển về máy. ƒ Bảo vệ mật khẩu của mình bằng cách chọn mật khẩu lạ, khĩ đốn hoặc khơng thể đốn được, trong đĩ chữ cái xen lẫn con số, chữ hoa xen lẫn chữ thường. ƒ Thường xuyên ghi dự phịng những dữ liệu quan trọng. Đồng thời, cảnh giác với những thư từ người quen biết nhưng khơng được báo trước, bởi cĩ thể chúng được gửi đi mà người kia khơng biết. - 16 - Spam vẫn từng phút gây thiệt hại cho nền kinh tế Internet. Người ta nhận định rằng sẽ khơng bao giờ cĩ đích đến cho cơng cuộc chống spam. Tùy vào ý thức của cư dân Internet và sức mạnh cơng nghệ, chỉ cĩ thể hạn chế phần nào nĩ mà thơi. 1.2 Các giải pháp cho vấn đề lọc thư rác 1.2.1 Ban hành các bộ luật chống thư rác Thư rác đang gia tăng với tốc độ khủng khiếp và địi hỏi cần cĩ những biện pháp cứng rắn phối hợp từ phía chính phủ. Chính vì vậy, việc ban hành các bộ luật chống thư rác là rất cần thiết và xác đáng. Hiện nay, cĩ rất ít quốc gia trên thế giới cĩ luật bảo vệ người dùng dưới sự tấn cơng của thư rác. Về mặt luật pháp đối với thư rác, Mỹ là nước đi đầu với bộ luật quy định về “Email khơng do yêu cầu” (Unsolicited Electronic Mail Act), theo sau đĩ là Khối Cộng đồng chung Châu Âu với bộ luật mẫu về Thương mại Điện tử và Quảng cáo trên Internet. Hai bộ luật này đều dựa trên những luật căn bản như Quyền riêng tư, Bảo vệ Thơng tin cá nhân và Quy định Thư tín/Giấy tờ Điện tử. Cả hai đều cĩ những điểm chung là bắt buộc người gửi email khơng được mời phải nêu rõ mục đích và nội dung trong phần tiêu đề (Subject) để người nhận cĩ thể xác định thơng tin ngay và đồng thời phải cĩ thơng tin cho phép người nhận được quyền rút tên khỏi danh sách email nếu muốn. Thêm vào đĩ, những cơng ty hoặc người gửi thư rác phải hiểu và nắm vững chính sách quản lý thư rác/quảng cáo của mỗi ISP mà họ gặp phải. Ở Việt Nam, chúng ta chỉ mới cơng nhận tính chất pháp lý của thư điện tử trong bộ Luật Hình sự, nhưng chưa cĩ luật quy định và nghiêm cấm các hình thức gửi thư rác. Theo dự kiến, Pháp lệnh Thương mại điện tử và các dịch vụ liên quan đang được xây dựng, dự kiến sẽ trình Quốc hội phê chuẩn trong thời gian tới, trong đĩ sẽ cĩ một số điều khoản quy định về thư rác được đưa ra xem xét. 1.2.2 Các phương pháp lọc thư rác trước đây Vấn đề thư rác là vấn đề gây nhức nhối trong xã hội trong những năm gần đây. Nhiều nhà khoa học và nhiều cơng trình nghiên cứu về phương pháp lọc thư rác đã được đầu tư và tiến hành từ khá lâu. Để đánh giá hiệu quả của một cơng cụ lọc thư rác người ta thường dựa trên hai độ đo sau: o False Positive – Tỷ lệ thư thường bị lọc nhầm thành thư rác. - 17 - o False Negative – Tỷ lệ thư rác bị lọc nhầm thành thư thường. Trong hai lỗi trên thì lỗi False Positive là loại lỗi cần tránh nhất, người dùng thường khơng chấp nhận lỗi này. Các cơng cụ lọc thư rác thường được tính tốn sao cho độ đo False Positives và False Negatives là nhỏ nhất. Tuy nhiên, lỗi False Positives cĩ phần được yêu tiên hơn. Một bộ lọc lý tưởng là sản phẩn cĩ False Positives bằng 0 và False Negatives bằng 0. Điều này dường như là khơng thể. Tất cả những cơng cụ lọc cĩ giá trị ngày nay thường sử dụng một trong số những phương pháp hoặc kết hợp của các phương pháp sau: . Phương pháp lọc theo từ khĩa Phương pháp lọc thư rác theo từ khĩa là một phương pháp truyền thống trong việc lọc thư rác. Người ta dựa vào những từ hay cụm từ cĩ trong đầu đề của thư (subject) và nội dung của thư để lọc. Khi một thư mới được gửi tới hịm thư của bạn, bạn phải tạo một bộ lọc mới đơn giản bằng cách chọn một số từ hoặc cụm từ trong nội dung thư. Các từ hay cụm từ này sẽ xác định đĩ là thư rác hay khơng. Vì mục đích của tất cả spam cơ bản là giống nhau (bán hoặc quảng cáo một sản phẩm hay một dịch vụ) và nội dung của hầu hết spam đều mang các đặc điểm chung. Những cụm từ, câu chữ như “Silk ties” (Cà vạt lụa) hoặc “Eliminate debt” (Xố nợ) xuất hiện thường xuyên trên spam và được coi những cụm từ thường xuyên xuất hiện nhất trong các bức thư khơng mong muốn. Các đặc điểm nội dung khác để nhận diện spam như yêu cầu hành động như “Fin out how, click here” hoặc thơng báo huỷ như “If you want to be removed from our mailing lists…”. Một vài năm gần đây, những kẻ gửi thư rác đã bắt đầu nhận ra rằng thư rác của chúng đã bị chặn bởi bộ lọc theo từ khĩa này. Do vậy những kẻ gửi thư rác này đã thay đổi cách viết nội dung của thư rác nhằm làm cho thư rác của chúng cĩ thể “xuyên qua” các bộ lọc. Điều này cĩ thể giải thích tại sao bạn nhận nhiều thư với những từ như "Vi@gra", "Mort.gage", "L|0|a|n|$" hay những tranh ảnh được nhúng vào trong thư. Phương pháp này cĩ một số ưu điểm và nhược điểm sau: Ưu điểm: ƒ Tính thích nghi: Người dùng cĩ thể dễ dàng biến đổi bộ lọc của mình để nĩ cĩ thể lọc các kiểu thư rác mà người đĩ đang phải nhận và điều quan - 18 - trọng là nĩ khơng cản trở (thích nghi) các từ và các cụm từ được sử dụng hàng ngày trong kinh doanh thương mại với bạn bè hay những người thân quen. Nhược điểm: ƒ Yêu cầu nhiều tiến trình xử lý bằng tay để điều chỉnh và duy trì bộ lọc được hiệu quả. Để cĩ thể đánh lừa các bộ lọc, những kẻ gửi thư rác luơn luơn thay đổi hình thức nội dung của thư rác, do đĩ những bộ lọc mở rộng phải được tạo ra để chống lại điều đĩ. . Phương pháp lọc Bayesian Lọc bằng thống kê Bayesian là đánh giá xem những từ ngữ trong một email sắp được chuyển đến cĩ thường xuyên xuất hiện trên thư rác (spam) hay thư hợp pháp (ham) khơng. Một cách hiệu quả giúp lọc chính xác là người dùng thơng báo cho chương trình lọc bất kỳ thư rác nào mà đã may mắn “thốt” đợt “truy quét” đầu tiên. Lần lọc sau, chắc chắn nĩ sẽ khơng thể trốn thốt qua bộ lọc. Bộ lọc Bayesian phải được học từ những email được xác định trước là thư tốt hay thư khơng tốt. Trong suốt quá trình cho bộ lọc học, nội dung của các thư này được tách các từ tố (token) và lưu vào trong một cơ sở dữ liệu. Dựa vào cơng thức Bayes, mỗi từ tố được tính cho một giá trị phụ thuộc vào một số tiêu chuẩn sau: - Mức độ thường xuyên xuất hiện của từ tố đĩ trong thư rác - Mức độ thường xuyên xuất hiện của từ tố đĩ trong thư bình thường - Số lượng thư rác mà bộ lọc đã được học - Số lượng thư bình thường bộ lọc đã được học. Khi phân tích một thư rác đến, nội dung của thư này cũng được tách ra thành các từ tố, tra giá trị ứng với từ tố này cĩ trong cơ sở dữ liệu từ đĩ tính được xác suất tổng hợp xem thư đĩ cĩ phải là thư rác khơng. Giá trị này thường gọi là “spamicity” Ưu điểm: ƒ Yêu cầu sự duy trì ít hơn các bộ lọc khác. ƒ Bộ lọc cĩ thể tự động thích nghi với các hướng thay đổi của thư rác. Bởi vì, bộ lọc Bayesian luơn tiếp tục học từ những thư mới đến, chúng sẽ tự thích nghi dần dần với các hướng thay đổi. - 19 - ƒ Tự động điều chỉnh phù hợp với hịm thư của những người dùng riêng biệt. Thí dụ, nếu người dùng là nhân viên cho vay lãi thì những thư lặp đi lặp lại yêu cầu cho vay sẽ khơng bị xác định như là thư rác Nhược đỉểm: ƒ Bộ lọc chỉ lọc tốt đối với những kiểu thư mà chúng đã được học. Để cĩ thể đạt tới khả năng là một bộ lọc tốt, nĩ cần cĩ thời gian học khá lâu và một lượng dữ liệu thư đủ phong phú. Các thư rác mới phải thường xuyên được cập nhật. . Phương pháp lọc SpamAssassin Phương pháp lọc SpamAssassin bao gồm một tập các chương trình lọc và các luật để xác định và đánh dấu thư rác. Để xác định một thư mới đến cĩ phải là thư rác hay khơng, nĩ dùng đầu đề (header) và nội dung của thư rồi dựa trên tập các luật được xác định trước và những kí hiệu dấu câu đặc biệt (tell-tale), xem thư cĩ vi phạm các luật này khơng sau đĩ tính điểm đối với từng thư. Từ kết quả thu được, xác định được một thư là thư rác hay thư thường. Ưu điểm: ƒ Tỉ lệ lọc thư rác của phương pháp SpamAssassin rất cao Nhược điểm: ƒ Phương pháp SpamAssassin tiêu tốn khá nhiều tài nguyên (khối điều khiển trung tâm CPU, bộ nhớ, thời gian xử lý) của máy chủ, đặc biệt khi phải xử lý những email cĩ dung lượng lớn. Cấu hình để SpamAssassin hoạt động tốt, đồng thời giảm nhẹ sự tiêu tốn tài nguyên cho máy chủ là một vấn đề quan trọng. . Phương pháp dùng danh sách trắng/đen Đây là phương pháp cơ sở của các bộ lọc thư rác. Tuy nhiên, ngày nay người ta ít khi sử dụng nĩ một cách đơn lập mà được dùng kết hợp với các phương pháp lọc khác như là một phần của hệ thống bộ lọc tích hợp. Bộ lọc danh sách trắng (Whitelist filter) sẽ khơng chấp nhận những email từ bất cứ địa chỉ nào nếu khơng cĩ trong danh sách được chắc chắn là những địa chỉ email (hoặc địa chỉ IP) tốt. - 20 - Bộ lọc danh sách đen (Blacklist filter), ngược lại sẽ cho phép những thư đến từ bất cứ địa chỉ email (hoặc địa chỉ IP) nào trừ những địa chỉ được liệt kê trong danh sách được biết đến như là địa chỉ email (hoặc địa chỉ IP) xấu. Danh sách đen cĩ thể được lưu trữ và được quản lý trên những hệ thống địa phương hoặc ánh xạ thơng qua mạng Internet. Ưu điểm: ƒ Danh sách trắng bảo đảm ngăn những email từ những nguồn khơng mong muốn. ƒ Với bộ lọc thư rác sử dụng danh sách đen được cập nhật thường xuyên sẽ cho giá trị False Positives bằng 0. Nhược điểm: ƒ Bộ lọc sử dụng danh sách trắng là cách loại trừ thư rác mạnh mà khơng cĩ tính mềm mỏng. Bất cứ thư nào tới mà khơng cĩ địa chỉ trong danh sách này thì đều bị loại thành thư rác, do đĩ giá trị False Positives thường cao. ƒ Các danh sách này khơng được tạo tự động mà sẽ do người quản trị thường xuyên cập nhật. Cả Blacklist và Whitelist đều rất khĩ duy trì và phương pháp này đặc biệt trở lên khơng hiệu quả đối với những tấn cơng của những kẻ tấn cơng cố đưa địa chỉ vào Whitelist và chối bỏ địa chỉ khỏi Blacklist. Ngày nay, một hình thức ngăn chặn spam mới kế thừa và pháp trển của phương pháp Blacklist được biết đến đĩ là Realtime Blackhole List (RBL) của Multiple Address Processing System (MAPS). Nĩ cĩ thể nhận biết các máy chủ cĩ nhiều thư rác do đĩ nhà cung cấp dịch vụ cĩ thể chặn những máy chủ này và lọc spam trước khi chúng đến hộp thư khách hàng của họ. Hàng ngàn nhà cung cấp dịch vụ dùng cơ sở dữ liệu của RBL đồng thời kết hợp nhiều ứng dụng bảo mật thư điện tử trong máy chủ. . Phương pháp lọc thư rác dùng chuỗi hỏi đáp (Challenge/Response filters) Đặc trưng của phương pháp này là khả năng tự động gửi thư hồi đáp cho người gửi để yêu cầu một số hành động kiểm tra chắc chắn về việc gửi thư của họ. Chương trình kiểm tra này được đặt tên là “Turing Test” do nhà tốn học người anh tên là Alan Turing nghĩ ra. - 21 - Trong một vài năm gần đây xuất hiện của một vài dịch vụ Internet tự động xử lý hàm Challenge/Response này cho người dùng. Chương trình yêu cầu người gửi thư phải vào website của họ và trả lời một số câu hỏi đơn giản để xác minh về email mà người này đã gửi.Việc này chỉ được yêu cầu trong lần gửi thư đầu tiên. Đáp ứng hàm Challenge/Response này rất đơn giản và khơng cĩ gì khĩ khăn khi một người dùng muốn gửi thư cho một người khác nhưng nĩ khơng mấy dễ dàng cho những kẻ gửi thư rác muốn phát tán một lượng lớn thư rác đi. Ưu điểm: ƒ Đối với một số người dùng cĩ lượng thư trao đổi thấp, hệ thống đơn lẻ này cĩ thể chấp nhận được như một phương pháp hồn hảo để loại trừ hồn tồn thư rác từ hịm thư của họ. Nhược điểm: ƒ Người dùng thường cảm thấy khơng thuận tiện. ƒ Những kẻ gửi thư rác cĩ thể viết những chương trình trả lời tự động những chuỗi hỏi đáp trên. . Phương pháp lọc dựa vào vị trí của các bộ lọc (Filter Placement) Cĩ 3 mơ hình chính cho bộ lọc được sắp đặt: a. Bộ lọc tích hợp với máy trạm email của người dùng: Nhiều bộ lọc thư rác được tích hợp với các máy trạm email chẳng hạn như Outlook hoặc outlool Exprees. Ưu điểm: ƒ Tối thiểu sự ảnh hưởng đối với những thĩi quen đọc thư thơng thường của người dùng. Thư rác thường bị di chuyển tới một thư mục “Junk Mail”. Người dùng cĩ thể xem lại hoặc xĩa spam lưu trong thư mục này đi một cách dễ dàng. Nhược điểm: ƒ Người dùng chỉ cĩ thể sử dụng với máy trạm của email hiện tại của mình. ƒ Khơng mềm dẻo: thường đưa cho người dùng giới hạn để chọn những cảnh báo. Thí dụ, khi người dùng đang chạy Microsoft Outlook với một bộ lọc thư rác tích hợp, bất cứ khi nào một thư rác tới, người dùng vẫn bị cảnh bảo một thư mới tới. Người dùng phải vào chương trình Outlook để - 22 - xác nhận xem thư mới đến đĩ là thư rác và khơng phải là một email quan trọng. Người dùng khơng thể điều chỉnh để tạo một cảnh báo khác cĩ thể nghe thấy giữa những email tốt và xấu hoặc chỉ cảnh báo những email tốt khi những email được gửi tới hịm thư trước khi chúng hoạt đơng chống lại bởi bộ lọc và di chuyển tới một thư mục riêng biệt. b. Các bộ lọc hoạt động như là một “proxy” giữa máy chủ email và máy trạm email của người dùng Bộ lọc này chạy bên trong máy của người dùng, định kì thăm dị máy chủ email, lấy ra những email của người dùng và nĩ được lọc trên máy chủ email trước khi những email này được gửi tới máy trạm email bình thường của người dùng và được lọc một lần nữa. Ưu điểm: ƒ Dễ thay đổi: Các thư trước khi được gửi tới người dùng nĩ cĩ thể đánh dấu, di chuyển hoặc xĩa bởi máy chủ email trước khi chúng được nhìn thấy bởi máy trạm email của người dùng. ƒ Bảo mật: chúng tương ứng như một tầng khác ở giữa Internet và máy trạm email của người dùng. Chúng sẽ khơng chạy bất cứ một ứng dụng nào hay chạy một tập lệnh nào đĩ được tìm thấy trong thư. Nhược điểm: ƒ Sử dụng hiệu quả phương pháp này địi hỏi tắt chế độ tự động kiểm tra trên máy trạn email của người dùng vì thế proxy phải thay đổi để làm việc trên máy chủ đầu tiên. ƒ Thơng tin tài khoản email cần được cài đặt trong bộ lọc cũng như trong máy trạm email của người dùng. c. Bộ lọc dựa trên máy chủ Những bộ lọc này thường chỉ được sử dụng trong một nhĩm hoặc mơi trường làm việc kinh doanh hơn là ở trong gia đình. Tất cả email đến đều thơng qua máy chủ trung tâm. Tại máy chủ trung tâm này, email được lọc bởi bộ lọc dựa trên máy chủ và những người dùng riêng biệt nhận thư của họ trên màn hình nền của máy họ lấy từ máy chủ trung tâm. Ưu điểm: - 23 - ƒ Việc quản lý trung tâm của tất cả các luật lọc thư bảo đảm tính an tồn trong mạng. ƒ Những người dùng riêng biệt khơng phải chịu trách nhiệm cũng như khơng phải lo lắng đến sự quản lý thư rác, giải phĩng họ để họ cĩ thể yên tâm trong cơng việc với trao đổi thư điện tử. Nhược điểm: ƒ Thường yêu cầu nhiều tới sự duy trì và cầm cĩ một người quản trị mạng cĩ khả năng và kinh nghiệm để quản lý bộ lọc thư rác này. ƒ Thường đắt hơn. . Phương pháp lọc dựa trên xác nhận danh tính của người gửi Giả mạo thư điện tử - là việc giả mạo địa chỉ thư điện tử của một cơng ty hoặc của một người khác để khiến người sử dụng tin tưởng và mở thư - đang là một trong những thử thách lớn nhất mà cộng đồng sử dụng Internet và các kỹ thuật viên chống thư rác hiện đang phải đối mặt. Nếu khơng cĩ sự thẩm định quyền, xác nhận và khả năng truy tìm danh tính của người gửi, các hãng cung cấp dịch vụ thư điện tử khơng bao giờ cĩ thể biết chắc một bức thư là hợp pháp hay bị giả mạo. Do đĩ việc xác nhận danh tính của người gửi là rất cần thiết. Để xác nhận danh tính của người gửi người ta đưa ra một số giải pháp sau: a. Phương pháp DomainKeys Phương pháp DomainKeys cĩ thể giúp phân định rõ thư rác và thư thường bằng cách cung cấp cho các hãng cung cấp dịch vụ thư điện tử một cơ chế xác nhận cả tên miền của mỗi người gửi thư điện tử và sự liêm chính của mỗi bức thư được gửi đi (ví dụ như các thư này khơng bị thay thế trong khi được truyền qua mạng). Và, sau khi đã xác nhận được tên miền, người ta cĩ thể so sánh tên miền này với tên miền mà người gửi sử dụng trong ơ “Người gửi” của bức thư để phát hiện các trường hợp giả mạo. Nếu đây là trường hợp giả mạo, thư đĩ sẽ bị coi là thư rác hoặc gian lận, và cĩ thể bị loại bỏ mà khơng ảnh hưởng tới người sử dụng. Nếu đây khơng phải là thư giả mạo, cĩ nghĩa là tên miền được biết đến và tên miền gửi thư đĩ cĩ thể được được đưa vào danh sách những tên miền đáng tin cậy và được đưa vào các hệ thống quy định chống thư rác được sử dụng chung giữa các hãng cung cấp dịch vụ và thậm chí đưa ra cho cả người sử dụng. b. Phương pháp Call-ID - 24 - Caller ID là một tiêu chuẩn đặt ra trong quá trình gửi thư. Tiêu chuẩn này địi hỏi người gửi thư điện tử phải cung cấp địa chỉ IP của máy chủ gửi thư theo dạng XML vào bản ghi DNS trên máy chủ tên miền của họ. Máy chủ nhận thư điện tử và máy khách nhận bức thư đĩ sẽ kiểm tra địa chỉ gửi thư trong tiêu đề bức thư với địa chỉ đã được cơng bố để xác nhận máy chủ gửi thư. Các bức thư khơng khớp với địa chỉ nguồn sẽ bị loại bỏ. DNS là hệ thống diễn dịch các địa chỉ IP số sang các tên miền Internet cĩ thể đọc được. c. Phương pháp SPF (Sender Policy Framework) - dựa trên cơ cấu chính sách người gửi Chuẩn SPF cũng yêu cầu người gửi thư điện tử phải sửa đổi DNS để cho biết máy chủ nào cĩ thể gửi thư từ một tên miền Internet nhất định. Tuy nhiên, SPF chỉ kiểm tra sự giả mạo khi bức thư trong quá trình chuyển thư hay cịn gọi là ở mức “ngồi phong bì”, xác minh địa chỉ “phản hồi” của một bức thư, thường được máy chủ nhận thư gửi trở lại trước khi tiếp nhận phần nội dung thư, sau đĩ sẽ thơng báo tới máy chủ nhận thư để loại bỏ bức thư. Trong đặc tả kỹ thuật kết hợp hai tiêu chuẩn, các cơng ty gửi thư điện tử sẽ cơng bố địa chỉ máy chủ thư điện tử của họ trong bản ghi DNS dưới định dạng Ngơn ngữ đánh dấu mở rộng (XML). Các cơng ty sẽ cĩ thể kiểm tra sự giả mạo ở mức phong bì (cũng giống như trong đề xuất SPF) và trong phần nội dung thư (theo đề xuất của Microsoft). Kỹ thuật này sẽ cho phép các cơng ty sử dụng cách thức của SPF để loại bỏ thư rác trước khi chúng được gửi đi, nếu sự giả mạo bị phát hiện ngay ở mức phong bì. Với những bức thư địi hỏi sự kiểm tra kỹ hơn trong nội dung thư, thì phương pháp Caller ID sẽ được sử dụng. Đề xuất này cũng sẽ hỗ trợ các tên miền đã cĩ sẵn những bản ghi SPF là văn bản, khơng theo định dạng XML. . Phương pháp lọc thư rác mới dựa trên mạng Xã hội Các nghiên cứu gần đây đã bắt đầu khai thác thơng tin từ mạng xã hội cho việc xác định thư rác bằng cách xây dựng một đồ thị (các đỉnh là địa chỉ email, cung được thêm vào giữa 2 node A và B nếu giữa A và B cĩ sự trao đổi thư qua lại). P.O. Boykin và V. Roychowdhury đã sử dụng một số tính chất đặc trưng của mạng xã hội để xây dựng một cơng cụ lọc thư rác [6]. Đầu tiên, người ta phân đồ thị thành các thành phần con rồi tính độ phân cụm cho từng thành phần này. Mỗi thành phần con là một đồ thị mạng xã hội của một node, - 25 - bao gồm tất cả các node hàng xĩm (các node xung quanh cĩ cung liên kết với node này) và những cung liên kết giữa các node hàng xĩm này với nhau. Nếu thành phần nào cĩ độ phân cụm thấp thì node tương ứng với thành phần đĩ là một địa chỉ gửi thư rác. Trong thành phần mạng xã hội của những node gửi thư rác, những node hàng xĩm của nĩ thường là những node rất ngẫu nhiên, khơng cĩ mối quan hệ (khơng cĩ sự trao đổi email qua lại với nhau) nên độ phân cụm của mạng xã hội của những node này rất thấp. Ngược lại, mạng xã hội ứng với những người dùng bình thường các node hàng xĩm của nĩ cĩ mối liên kết cao với nhau nên cĩ độ phân cụm cao hơn. Dựa vào độ phân cụm, người ta tạo được danh sách đen (Blacklist) gồm địa chỉ email tương ứng với những node cĩ độ phân cụm rất thấp, danh sách trắng (Whitelist) ứng với node cĩ độ phân cụm cao, số node cịn lại sẽ được đưa vào danh sách cần xem xét (Greylist). Phương pháp này cĩ thể phân loại được 53% tổng số email một cách chính xác là ham hay spam. Nhược điểm của phương pháp là những spammer cĩ thể xây dựng mạng xã hội của chính họ nên khĩ cĩ thể phát hiện ra. Cho đến nay, một bộ lọc thư rác được xem là hồn hảo vẫn chưa được tạo ra, và việc tạo ra một bộ lọc thư rác hồn hảo cho mọi thời đại 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ế tồ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 đề tố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à tố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 tố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 hồn tồn đã là mạng thơng thường (Regular Networks) cũng khơng hồn tồ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 tố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 tồ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 tồ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 hồn tồ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 hồn tồn. Vì vậy, chúng khơng nên bị coi như là mạng ngẫu nhiên hồn tồ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 hồn tồ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 tố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 tố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 tồ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 để hồ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 hồn tồ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 hồn tồ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 tố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 hồn tồn thơng thường, cũng khơng hồn tồ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 tố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 tố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 tố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 tồ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) ngồ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 ngồ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 ngồi thơng thường bị đánh giá thấp, số mũ này nhỏ hơn so với tồn mạng. Chính vì vậy, cĩ nhiều node cĩ bậc nhỏ trong sự phân bố của tồ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 ngồ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 tố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 ngồi với nhau hay nĩi cách khác mối liên kết giữa các node bên ngồ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 ngồ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 ngồi mà những node bên ngồ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 ngồ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 ngồi này kết nối với các node bên ngồ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 tố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 tố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 ngồi. Do đĩ một lần nữa, việc tính tố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 ngồ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 tồ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 ngồ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 ngồ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. Ngồ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 tố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 tố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 tố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 tố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 tố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 tố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 ngồ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 tố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 ngồ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 ngồ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 tố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 ngồ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 ngồ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 ngồ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 ngồ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 ngồ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 ngồ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