Sử Dụng Thuật Toán Meta-Heuristic Trong Phân Hoạch Mạng Xã Hội Theo Hướng Lưu Trữ

Luận văn thạc sĩ về ứng dụng thuật toán meta heuristic trong phân hoạch mạng xã hội, tối ưu hóa lưu trữ dữ liệu. Nghiên cứu khoa học máy tính chuyên sâu.

• Tác giả: Trần Kiên Nghị
• Người hướng dẫn: Pgs. Ts. Trần Văn Hoài
• Trường học: Trường Đại học Bách Khoa – ĐHQG TP.HCM
• Chuyên ngành: Khoa Học Và Kỹ Thuật Máy Tính
• Đề tài: Sử Dụng Thuật Toán Meta-Heuristic Trong Phân Hoạch Mạng Xã Hội Theo Hướng Lưu Trữ
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Tp. Hồ Chí Minh

Tóm tắt

I. Phân hoạch Mạng Xã Hội Là Gì Tổng Quan Chi Tiết Nhất

Mạng xã hội đã trở thành một phần không thể thiếu trong cuộc sống hiện đại, ảnh hưởng sâu rộng đến nhiều lĩnh vực. Sự phổ biến của các nền tảng như Facebook, Twitter, và LinkedIn tạo ra một lượng dữ liệu khổng lồ, đặt ra những thách thức lớn về lưu trữ, quản lý và truy xuất. Phân hoạch mạng xã hội là một giải pháp quan trọng để giải quyết vấn đề này, bằng cách chia mạng thành các cộng đồng nhỏ hơn, dễ quản lý hơn. Mục tiêu chính là tối ưu hóa lưu trữ và cải thiện hiệu suất truy vấn dữ liệu. Luận văn này trình bày một giải pháp phân hoạch, tạo các bản sao dữ liệu người dùng sao cho dữ liệu liên quan đều nằm trong cùng máy chủ và số lượng bản sao là ít nhất có thể.

1.1. Tổng quan về Mạng Phức Hợp và Mạng Xã Hội

Mạng phức hợp (Complex Networks) đóng vai trò quan trọng trong nhiều lĩnh vực. Mạng xã hội là một trường hợp cụ thể của mạng phức hợp, bao gồm các nút (cá nhân, tổ chức) và các liên kết (quan hệ). Nghiên cứu mạng xã hội đòi hỏi hiểu rõ cấu trúc và các mối quan hệ bên trong nó. Mạng xã hội có thể được biểu diễn bằng đồ thị hoặc ma trận kề để phân tích và khai thác thông tin. "Mạng xã hội là một cấu trúc mang tính xã hội tạo thành từ các nút (tiếng Anh: node) và các liên kết (tiếng Anh: tie), mỗi nút có thể là một cá nhân hay một tổ chức, các liên kết thể hiện mối quan hệ giữa các nút".

1.2. Thách thức Lưu trữ và Quản lý Dữ liệu Mạng Xã Hội

Sự tăng trưởng nhanh chóng của dữ liệu mạng xã hội tạo ra những thách thức về lưu trữ phân tán, quản lý dữ liệu lớn và hiệu suất truy vấn. Các giải pháp lưu trữ truyền thống gặp khó khăn trong việc đáp ứng nhu cầu ngày càng tăng. Việc phân hoạch mạng xã hội và tối ưu hóa lưu trữ là cần thiết để đảm bảo khả năng mở rộng và hiệu quả của hệ thống. Việc phân tích mạng xã hội có khối lượng dữ liệu lớn là một thách thức không chỉ cho giới công nghệ mà còn cho giới nghiên cứu.

II. Vấn Đề Lưu Trữ Mạng Xã Hội Giải Pháp Phân Tán Nào Tối Ưu

Khi mạng xã hội phát triển, việc lưu trữ dữ liệu trở thành một vấn đề cấp bách. Các giải pháp lưu trữ phân tán như phân hoạch dựa trên địa lý, phân hoạch ngẫu nhiên, phân hoạch theo đồ thị, và phân hoạch tối ưu theo khối được sử dụng để giải quyết vấn đề này. Tuy nhiên, mỗi phương pháp đều có những ưu và nhược điểm riêng. Việc lựa chọn giải pháp phù hợp phụ thuộc vào đặc điểm của mạng xã hội và yêu cầu về hiệu suất và chi phí. "Khi lượng người tham gia mạng xã hội tăng cao, lượng dữ liệu lưu trữ cũng tăng, băng thông, bộ nhớ,. đều đòi hỏi nhiều hơn dẫn tới việc quá tải các trung tâm dữ liệu và làm gia tăng độ trễ trong quá trình truyền nhận dữ liệu".

2.1. Các Giải Pháp Lưu Trữ Phân Tán Phổ Biến Hiện Nay

Các giải pháp lưu trữ phân tán bao gồm: Phân hoạch dựa trên địa lý (dữ liệu được lưu trữ gần người dùng), Phân hoạch ngẫu nhiên (dữ liệu được phân phối ngẫu nhiên trên các máy chủ), Phân hoạch theo đồ thị (dữ liệu được phân hoạch dựa trên cấu trúc liên kết của mạng xã hội), và Phân hoạch tối ưu theo khối (dữ liệu được chia thành các khối và phân phối trên các máy chủ). Mỗi giải pháp có ưu và nhược điểm riêng, phù hợp với các yêu cầu khác nhau. Cần phân tích, so sánh để chọn ra giải pháp tốt nhất.

2.2. Bài Toán Phân Hoạch Đồ Thị và Độ Phức Tạp Tính Toán

Bài toán phân hoạch đồ thị (Graph partitioning) là một bài toán kinh điển trong lý thuyết đồ thị, thuộc nhóm bài toán NP-Hard. Việc tìm kiếm giải pháp tối ưu cho bài toán này đòi hỏi chi phí tính toán lớn. Các thuật toán heuristic được sử dụng để tìm kiếm các giải pháp gần tối ưu trong thời gian hợp lý. Thuật toán Meta-Heuristic là một lựa chọn hiệu quả để giải quyết bài toán phân hoạch đồ thị trong mạng xã hội. "Xét dưới khía cạnh đồ thị thuần túy thì bài toán phân hoạch đồ thị là rất kinh điển, và thuộc nhóm bài toán NP-Hard".

III. Thuật Toán Meta Heuristic Bí Quyết Phân Hoạch Hiệu Quả Nhất

Thuật toán Meta-Heuristic cung cấp một phương pháp hiệu quả để giải quyết bài toán phân hoạch mạng xã hội và tối ưu hóa lưu trữ. Các thuật toán như Thuật toán di truyền (Genetic Algorithm), Thuật toán tối ưu hóa đàn kiến (Ant Colony Optimization), và Thuật toán tối ưu hóa bầy đàn chim (Particle Swarm Optimization) được sử dụng để tìm kiếm các giải pháp gần tối ưu. Ưu điểm của các thuật toán này là khả năng xử lý các bài toán lớn và phức tạp, đồng thời tìm kiếm các giải pháp trong không gian rộng.

3.1. Giới Thiệu Các Thuật Toán Meta Heuristic Phổ Biến

Thuật toán di truyền (Genetic Algorithm) mô phỏng quá trình tiến hóa tự nhiên để tìm kiếm giải pháp tối ưu. Thuật toán tối ưu hóa đàn kiến (Ant Colony Optimization) mô phỏng hành vi của đàn kiến để tìm đường đi ngắn nhất. Thuật toán tối ưu hóa bầy đàn chim (Particle Swarm Optimization) mô phỏng hành vi của bầy đàn chim để tìm kiếm thức ăn. Các thuật toán này có thể được áp dụng để giải quyết bài toán phân hoạch mạng xã hội.

3.2. Ứng Dụng Thuật Toán Meta Heuristic vào Bài Toán Phân Hoạch

Việc áp dụng Thuật toán Meta-Heuristic vào bài toán phân hoạch mạng xã hội đòi hỏi việc xây dựng mô hình toán học phù hợp và thiết kế các hàm mục tiêu để tối ưu hóa. Hàm mục tiêu có thể bao gồm các yếu tố như giảm số lượng bản sao dữ liệu, cân bằng tải giữa các máy chủ, và giảm chi phí lưu trữ. Cần lựa chọn thuật toán phù hợp và tinh chỉnh các tham số để đạt được hiệu quả tốt nhất.

IV. Mô Hình Hóa Bài Toán Hướng Dẫn Chi Tiết và Ứng Dụng Thực Tế

Để giải quyết bài toán phân hoạch mạng xã hội bằng Thuật toán Meta-Heuristic, cần xây dựng một mô hình toán học phù hợp. Mô hình này cần định nghĩa rõ các yếu tố như nút, cạnh, quan hệ, và các ràng buộc. Hàm mục tiêu cần được xác định để đánh giá chất lượng của các giải pháp. Các thuật toán hiện có như Gossip-based partitioning và giải thuật đề xuất – KSOLVE có thể được sử dụng để giải quyết bài toán.

4.1. Định Nghĩa Bài Toán và Xây Dựng Mô Hình Toán Học

Bài toán phân hoạch mạng xã hội có thể được định nghĩa là việc chia mạng xã hội thành các cộng đồng nhỏ hơn sao cho các thành viên trong cùng một cộng đồng có mối quan hệ chặt chẽ với nhau. Mô hình toán học cần bao gồm các yếu tố như nút (thành viên), cạnh (quan hệ), và các ràng buộc (ví dụ: giới hạn về kích thước của các cộng đồng). Hàm mục tiêu cần được xác định để đánh giá chất lượng của các giải pháp.

4.2. Các Giải Thuật Hiện Có và Giải Pháp Đề Xuất KSOLVE

Các giải thuật hiện có như Gossip-based partitioning và giải thuật đề xuất – KSOLVE có thể được sử dụng để giải quyết bài toán phân hoạch mạng xã hội. Giải thuật KSOLVE được thiết kế để tìm kiếm các giải pháp tối ưu dựa trên việc phân tích các sự kiện liên tục trong mạng xã hội. Cần so sánh và đánh giá hiệu quả của các giải thuật khác nhau.

V. Kết Quả Thực Nghiệm Đánh Giá Hiệu Quả Tối Ưu Lưu Trữ

Kết quả thực nghiệm cho thấy việc sử dụng Thuật toán Meta-Heuristic trong phân hoạch mạng xã hội có thể giúp giảm đáng kể số lượng bản sao dữ liệu so với các giải pháp lưu trữ thông thường. Chương trình thử nghiệm được xây dựng trên tập dữ liệu thực tế để đánh giá hiệu quả của giải pháp. Kết quả so sánh với giải thuật SPAR cho thấy giải pháp đề xuất có hiệu quả tốt hơn trong việc tối ưu hóa lưu trữ.

5.1. Xây Dựng Chương Trình Thử Nghiệm và So Sánh Kết Quả

Chương trình thử nghiệm được xây dựng để mô phỏng quá trình phân hoạch mạng xã hội trên tập dữ liệu thực tế. Kết quả được so sánh với các giải pháp khác như SPAR để đánh giá hiệu quả của giải pháp đề xuất. Các chỉ số đánh giá bao gồm số lượng bản sao dữ liệu, thời gian thực hiện, và chi phí lưu trữ.

5.2. Đánh Giá Ưu Nhược Điểm Của Giải Pháp Đề Xuất

Giải pháp đề xuất có ưu điểm là giảm số lượng bản sao dữ liệu và tối ưu hóa lưu trữ. Tuy nhiên, giải pháp cũng có nhược điểm là đòi hỏi chi phí tính toán lớn và cần tinh chỉnh các tham số để đạt được hiệu quả tốt nhất. Cần phân tích và đánh giá kỹ lưỡng để áp dụng giải pháp vào thực tế.

VI. Tương Lai Phân Hoạch Mạng Xã Hội Hướng Phát Triển Đầy Tiềm Năng

Trong tương lai, việc phân hoạch mạng xã hội và tối ưu hóa lưu trữ sẽ tiếp tục là một lĩnh vực nghiên cứu quan trọng. Các hướng phát triển tiềm năng bao gồm việc sử dụng các thuật toán Meta-Heuristic tiên tiến hơn, tích hợp các kỹ thuật học máy, và phát triển các giải pháp lưu trữ phân tán linh hoạt và hiệu quả hơn. Việc bảo mật và quyền riêng tư cũng cần được quan tâm trong quá trình phân hoạch và lưu trữ dữ liệu mạng xã hội.

6.1. Các Hướng Nghiên Cứu Tiềm Năng Trong Tương Lai

Các hướng nghiên cứu tiềm năng bao gồm việc sử dụng các thuật toán Meta-Heuristic tiên tiến hơn, tích hợp các kỹ thuật học máy để tự động hóa quá trình phân hoạch, và phát triển các giải pháp lưu trữ phân tán linh hoạt và hiệu quả hơn. Cần tập trung vào việc giải quyết các thách thức về dữ liệu lớn, bảo mật, và quyền riêng tư.

6.2. Bảo Mật và Quyền Riêng Tư Trong Phân Hoạch Mạng Xã Hội

Việc bảo mật và quyền riêng tư cần được quan tâm trong quá trình phân hoạch mạng xã hội. Các giải pháp cần đảm bảo rằng dữ liệu cá nhân được bảo vệ và không bị lộ lọt trong quá trình phân hoạch và lưu trữ. Cần tuân thủ các quy định về bảo vệ dữ liệu và áp dụng các biện pháp bảo mật phù hợp.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI 1.1 Lý do chọn đề tài Mạng xã hội, hay gọi là mạng xã hội ảo (tiếng Anh: Social Network) là dịch vụ nối kết các thành viên cùng sở thích trên Internet lại với nhiều mục đích khác nhau không phân biệt không gian và thời gian. Mạng xã hội xuất hiện lần đầu tiên vào năm 1995 với sự ra đời của mạng Classmate có mục đích kết nối các bạn học. Sau đó, có khá nhiều mạng xã hội xuất hiện và trở thành một trào lưu mới như Friendster, MySpace, Facebook,…[22], [28]. Ngoài việc chia sẻ cảm nghĩ, sở thích,các mạng xã hội còn hướng tới lưu trữ, xử lý dữ liệu hình ảnh, âm thanh, video và nhiều loại dữ liệu khác ngày càng phong phú, đa dạng.

Các mạng xã hội đều thu hút một lượng rất lớn người dùng, có thể lên tới hang trăm triệu thành viên. Từ đó đặt ra nhu cầu rất lớn về cơ sở hạ tầng mạng, sức mạnh tính toán và dung lượng lưu trữ dữ liệu. Ngoài ra, do người sử dụng ở khắp nơi trên thế giới nên mạng xã hội cũng mang tính phân bố rộng khắp để đáp ứng nhu cầu ngày một gia tăng của người dùng. Khi lượng người tham gia mạng xã hội tăng cao, lượng dữ liệu lưu trữ cũng tăng, băng thông, bộ nhớ,.

đều đòi hỏi nhiều hơn dẫn tới việc quá tải các trung tâm dữ liệu và làm gia tăng độ trễ trong quá trình truyền nhận dữ liệu. Điều nghiêm trọng hơn là sẽ làm tăng thời gian đáp ứng của hệ thống khi nhận tương tác từ người dùng. Ngày nay, với tiến bộ vượt bậc của công nghệ lưu trữ, việc chế tạo các bảng mạch nhớ (RAM) và các thiết bị lưu trữ phát triển rất nhanh nhưng giá thành vẫn còn rất cao, và quan trọng hơn là không có khả năng lưu trữ hết toàn bộ người dung trên đó. Vì vậy, nhu cầu giảm số lượng lưu trữ mà cụ thể là giảm số lượng bản sao khi phân hoạch mạng xã hội là mục tiêu quan trọng được hướng đến.

Xu hướng phát triển ngày càng mạnh của mạng xã hội và nhu cầu đặt ra cho việc lưu trữ, truy xuất, xửlý lượng lớn dữ liệu ngày càng cấp thiết. Đề tài: “Sử dụng thuật toán meta-heuristic trong phân hoạch mạng xã hội hướng lưu trữ” là cần thiết đểhướng đến việc cung cấp dịch vụ tốt hơn cho cộng đồng, mang lại trải nghiệm tốt hơn cho người dùng; đồng thời cũng tiết kiệm chi phí cho các nhà cung cấp dich vụ mạng xã hội.2 Tình hình nghiên cứu trong và ngoài nước Hiện tại đã có nhiều công trình nghiên cứu liên quan đến việc phân hoạch dữ liệu mạng xã hội. Một số hướng nghiên cứu phổ biến như: phân hoạch dữ liệu theo nhận thức xã hội để phân phối việc lưu trữ dữ liệu xã hội (Socially aware data partitioning for distributed storage of social data) [7]; nhân bản (replication) dữ liệu trong mạng xã hội [3]; chiến lược phân vùng cơ sở dữ liệu cho dữ liệu mạng xã hội [8]; nhân rộng các mạng xã hội trực tuyến [4]… Với hướng nghiên cứu phân hoạch dữ liệu theo nhận thức xã hội [7], tác giả Duc A.Tran dùng giải pháp triển khai thêm nhiều server để đối phó với sự tăng trưởng nhanh chóng của số lượng user và các hoạt động. Tác giả nhấn manh tầm quan trọng của việc phân vùng dữ liệu trên các server sao cho hiệu quả và tối đa hóa cân bằng tải giữa chúng.

Đồng thời bài báo cũng nêu ra một trở ngại trong việc lưu trữ xã hội vì đa số các truy cập mang tính cục bộ. Tác giả đã tìm ra cách phân vùng dữ liệu hiệu quả theo mối quan tâm của user (sở thích đọc ghi dữ liệu trên mạng, thường xuyên đọc dữ liệu của ai). Thuật toán mới có hiệu xuất cao và cân bằng phân vùng tốt. Tiếp theo nghiên cứu trên, tác giả Duc A.Tran tiếp tục với hướng nghiên cứu nhân bản dữ liệu trong mạng xã hội [3] vào năm 2013.

Tác giả quan tâm tới việc xác định nơi tốt nhất để lưu dữ liệu. Nhu cầu nhân bản dữ liệu để đặt ở nhiều server xuất hiện. Toàn bộ bài báo chú trọng vào việc nhân bản: khi nào, ở đâu, cách thực hiện. Phương pháp S-CLONE [3] được đề xuất để giải quyết vấn đề.

Sự xuất hiện của các trở ngại trong việc thiết kế hệ thống có khối lượng lưu trữ và lưu thông cực lớn dẫn tới việc tốn nhiều chi phí để tái cấu trúc như Facebook, Twitter vẫn thường mắc phải.Với hướng nghiên cứu Scaling Online Social Networks [4], tác giả đề xuất phương pháp SPAR nhằm giảm chi phí khi tái kiến trúc dữ liệu. Việc tái kiến trúc phân vùng dữ liệu không ảnh hưởng tới ứng dụng bên trên. Một hướng nghiên cứu khác, tác giả Oscar Ricardo Moll Thomae [8] cung cấp một số chiến lược thiết kế database nhằm tối ưu hóa chi phí lưu trữ, truy vấn, cập nhật dữ liệu mạng xã hội. Với lượng dữ liệu lớn và các hoạt động phong phú của mạng xã hội, đề tài chỉ tập trung vào một hoạt động đơn lẻ là hoạt động kết bạn giữa các thành viên đã tham gia vào mạng xã hội.

Nội dung chính của đề tài liên quan đến bài toán phân hoạch đồ 2     thị mạng xã hội, hướng đến giảm số lượng bản sao khi mạng xã hội tăng trưởng nhanh. Đề tài không tập trung vào bản chất dữ liệu của người dùng và mặc định xem như dữ liệu của mọi người dùng là như nhau về độ phức tạp và lưu trữ. Ngoài ra, xét dưới khía cạnh đồ thị thuần túy thì bài toán phân hoạch đồ thị là rất kinh điển, và thuộc nhóm bài toán NP-Hard.3 Mục tiêu của đề tài 1.1 Về lý thuyết Hiểu rõ các giải thuật lưu trữ phân tán đang sử dụng cho mạng xã hội, đề xuất giải pháp tái phân hoạch mạng xã hội và tạo các bản sao dữ liệu người dùng sao cho các dữ liệu liên quan đều nằm trên cùng một phân hoạch và số lượng bản sao của mạng là ít nhất có thể.2 Về thực nghiệm Xây dựng một chương trình thử nghiệm có thể phân hoạch mạng xã hội giảlập (dựa trên tập dữ liệu thực tế) cho số lượng bản sao ít hơn so với các giải pháp phân tán đang được sử dụng. So sánh và đánh giá kết quả thực nghiệm của giải pháp với giải thuật SPAR.4 Nội dung nghiên cứu Các giải thuật lưu trữ phân tán: Phân hoạch dựa trên địa lý, Phân hoạch ngẫu nhiên, Phân hoạch theo đồ thị, Phân hoạch tối ưu theo khối.

Giải thuật tối ưu SPAR do Josep M.Pujol và các đồng sự phát triển. Đề xuất giải pháp cải tiến.5 Phương pháp nghiên cứu Nghiên cứu các giải thuật lưu trữ phân tán đã được trình bày trong các tài liệu như: luận văn thạc sĩ, các bài báo khoa học. Nghiên cứu các giải pháp đang thực hiện trên các mạng xã hội phổ biến. Sử dụng tập dữ liệu thực từ internet [40] để giả lập mạng xã hội theo giải thuật SPAR và giải thuật đề xuất.

3     Sử dụng các phần mềm, gói phần mềm, thư viện mã nguồn mở hỗ trợ tốt cho việc phân hoạch đồ thị dùng heuristic(Chaco, Metis. Cụ thể trong luận văn này tôi sẽ dùng Metis (gpmetis). Những thư viên này có thể giúp ta thực nghiệm các thuật toán đã có trước khi tổng hợp được phương pháp tốt cho phân hoạch đồ thị mạng xã hội. Đề xuất sử dụng mô hình quy hoạch nguyên, đưa bài toán về bài toán quy hoạch nguyên thuần túy và lập trình bằng ngôn ngữ C# kết hợp với công cụ lpsolve để giải quyết bài toán.

So sánh và đánh giá kết quả thu được từ thực nghiệm của chương trình với kết quả thu được từ phương pháp random, phần mềm gpmetis, giải thuật SPAR. 4     CHƯƠNG 2: TỔNG QUAN VỀ MẠNG XÃ HỘI 2.1 Mạng phức hợp (Complex network) Trong những 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. 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 nút (node) gắn với nhau thành một mạng bởi các liên kết (tie) [3], [13], [17], [20], [21]. Thí dụ như: mạng Internet là mạng của các router hoặc các domain [18]; mạng World Wide Web (WWW) là mạng của những trang web [14]; một tổ chức là mạng của những thành viên trong tổ chức; nền kinh tế toàn cầu là mạng 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ụ; mạng của các chất hóa học (liên kết với nhau bởi các phản ứng hóa học); mạng ngôn ngữ (thí dụ như mạng đồng âm khác nghĩa, mạng đồng nghĩa); các mạng lưới điện cao thế (Electrical Power Grid); các chủ đề của một buổi nói chuyện và thậm chí việc vạch kế hoạch cho xử lý một vấn đề toán học nào đó cũng có thể mô hình bằng một mạng 2.2 Mạng xã hội Mạng xã hội là một trường hợp cụ thể của mạng phức hợp.

Mạng xã hội, hay còn gọi là mạng xã hội ảo (tiếng Anh: social network) là một cấu trúc mang tính xã hội tạo thành từ các nút (tiếng Anh: node) và các liên kết (tiếng Anh: tie), mỗi nút có thể là 5     một cá nhân hay một tổ chức, các liên kết thể hiện mối quan hệ giữa các nút (bạn bè, sự trao đổi thông tin,…) [22]. Trường hợp đơn giản nhất, mạng bao gồm 2 node và một liên kết giữa chúng. Bối cảnh có thể là hai người cùng học cứu tại một trường đại học. Ví dụ, A và B có một mối quan hệ bởi vì cả hai cùng học tập tại lớp Cao học khoa Khoa học và ky thuật máy tính, đại học Bách Khoa, ta biểu diễn một liên kết giữa hai nút A và B.

học cùng lớp A B Hình 2.1: Mối quan hệ đối xứng Mạng ở Hình 2.