Luận văn ThS: Một số thuật toán tìm core và ứng dụng trong phân tích mạng xã hội

146 lượt xem
Share

Luận văn Một số thuật toán tìm core và ứng dụng trong phân tích mạng xã hội trình bày một số kiến thức tổng quan; tìm hiểu một số thuật toán tìm Cores trong phân tích mạng xã hội, mô tả thuật toán, đánh giá độ phức tạp của thuật toán; tìm hiểu một số ứng dụng của core trong phân tích mạng xã hội và xây dựng chương trình ứng dụng.

Mục lục nội dung

Luận văn ThS: Một số thuật toán tìm core và ứng dụng trong phân tích mạng xã hội

1. Mở đầu

Mạng xã hội là một mô hình mạng có tính chất xã hội được cấu tạo bởi các đỉnh và các cung, các đỉnh liên kết với nhau bởi một hoặc nhiều cung, thể hiện mối quan hệ cụ thể. Mỗi đỉnh là một thực thể trong mạng, thực thể này có thể là một cá nhân, một tổ chức hay một quốc gia bất kỳ… Các thực thể trong mạng tương tác với nhau thông qua các liên kết. Các liên kết này có thể là quan hệ bạn bè, đồng nghiệp, cũng có thể là các quan hệ đối đầu thù địch hay các trao đổi tài chính, giao dịch… Nhu cầu phân tích mạng xã hội đã được bắt đầu từ rất sớm từ những năm 1930 và ngày càng trở thành chủ đề quan trọng. Đặc biệt với sự phát triển hiện nay của mạng xã hội đã sản sinh ra một khối lượng dữ liệu khổng lồ, vì vậy bài toán phân tích mạng xã hội trở thành bài toán phân tích mạng trong miền dữ liệu lớn. Đây là một bài toán khó và nhận được nhiều sự quan tâm của các nhà khoa học hiện nay.

2. Nội dung

2.1 Cơ sở lý thuyết đồ thị và mạng xã hội

Một số khái niệm liên quan đến đồ thị 

  • Định nghĩa đồ thị
  • Các loại đồ thị
  • Các khái niệm liên quan

Một số khái niệm liên quan về mạng xã hội 

  • Phân tích cấu trúc mạng xã hội
  • Biểu diễn độ phân rã về mạng xã hội trên đồ thị 

Một số khái niệm về Core 

  • Khái niệm về Core, k-core
  • Tính chất của Core

2.2 Một số thuật toán nhanh

Thuật toán tìm Cores

  • Mô tả thuật toán 
  • Đánh giá độ phức tạp của thuật toán

Thuật toán tìm p-core 

  • Hàm đơn điệu p và core 
  • Một số ví dụ về hàm đơn điệu p 
  • Core tổng quát và tính chất. 
  • Thuật toán tìm p-core

Thuật toán tìm k-core địa phương 

  • Mô tả thuật toán
  • Thuật toán k-core địa phương

2.3 Ứng dụng trong phân tích mạng xã hội

Mô tả bài toán phân tích mạng mạng xã hội

Phân tích mạng xã hội bằng thuật toán k-core địa phương

  • Đặt bài toán
  • So sánh giữa thuật toán địa phương với core và core lân cận 

So sánh hệ số phân nhóm trong thuật toán k-core

3. Kết luận

Luận văn đã đạt được một số kết quả sau:

  • Tìm hiểu các kiến thức cơ bản về Lý thuyết đồ thị, mạng xã hội.
  • Học hỏi và nắm bắt được một số thuật toán xử lý trong đồ thị, đặc biệt là các thuật toán phân rã đồ thị, tìm k-core, p-core với thời gian đa thức.
  • Nghiên cứu cài đặt được các thuật toán đã tìm hiểu, phát biểu và giải quyết được một số bài toán thực tế áp dụng những kiến thức đã nghiên cứu. 
  • Lý thuyết và các thí nghiệm về k-core địa phương chỉ tập trung vào dữ liệu mạng thực; đối với nghiên cứu, chẳng hạn như mạng ngẫu nhiên hoặc giới hạn thấp cho sự xuất hiện của k-core địa phương, không được đề cập trong luận án. Tốt nhất là nên xây dựng cơ sở mạng k-core cục bộ ngẫu nhiên trên các tham số như k và hệ số phân cụm. Một lĩnh vực khác là, thay vì tập trung vào mức độ cộng đồng địa phương (kích cỡ của các thành phần kết nối trong đồ thị lân cận), số lượng các thành phần được kết nối có thể là một cuộc tranh luận cho các nghiên cứu sâu hơn; k-core cũng liên quan đến cấu trúc cộng đồng và có thể là một phương pháp lân cận tốt cho đồ thị. Nếu một đồ thị lân cận của đỉnh có nhiều thành phần kết nối, nó có thể có nghĩa là đỉnh có thể là một điểm nóng, thay vì một thành viên của cộng đồng

4. Tài liệu tham khảo

Nguyễn Cam, Chu Đức Khánh, Lý thuyết đồ thị, NXB Thành phố Hồ Chí Minh, 1999

Trần Minh Đức, Nghiên cứu, thiết kế, thử nghiệm mạng xã hội phục vụ phát triển nông thôn, Học viện Công nghệ bưu chính viễn thông Hà Nội, 2012

Kayhan Erciyes, Complex Networks: An Algorithmic Perspective Sep 6, 2014

Niklaus Wirth, Algorithms + Data Structures = Programs (Prentice-Hall Series in Automatic Computation) Feb 1976

Nasrullah Memon and Reda Alhajj (Editor), From Sociology to Computing in Social Networks: Theory, Foundations and Applications (Lecture Notes in Social Networks) 2010 th Edition...

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn Thạc sĩ trên ---

146 lượt xem
Share
Ngày:28/08/2020 Chia sẻ bởi:
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM