TRANG THÔNG TIN LUẬN ÁN TIẾN SĨ

Tên đề tài luận án tiến sĩ: NGHIÊN CỨU CÁC THUẬT TOÁN RÚT GỌN ĐỒ THỊ VÀ ỨNG DỤNG ĐỂ PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI

Chuyên ngành:      Hệ thống thông tin           Mã số:       9.48.01.04

Họ và tên NCS: Nguyễn Xuân Dũng

Cán bộ hướng dẫn:

1.   PGS.TS Đoàn Văn Ban

2.  TS Đỗ Thị Bích Ngọc

Đơn vị đào tạo: Học viện Công nghệ Bưu chính Viễn thông

Cơ sở đào tạo: Học viện Công nghệ Bưu chính Viễn thông

NHỮNG KẾT QUẢ MỚI CỦA LUẬN ÁN


  • Đề xuất thuật toán REG (Reduce Equivalence Graph) rút gọn đồ thị dựa vào lớp tương đương của các đỉnh theo độ đo trung tâm trung gian. Thực hiện các thực nghiệm đánh giá tính hiệu quả và thời gian thực hiện của thuật toán đề xuất so với thuật toán gốc điển hình sử dụng độ đo trung tâm trung

  • Đề xuất thuật toán FBC (Fast algorithm for Betweenness Centrality) cải tiến thời gian tính độ đo trung tâm trung gian và đề xuất thuật toán CDAB (Community Detection Algorithm based on Betweenness centrality) cải tiến thời gian phát hiện các cộng đồng trên đồ thị mạng xã hội rút gọn dựa vào độ đo trung tâm trung gian. Thực hiện các thực nghiệm đánh giá tính hiệu quả và thời gian thực hiện của thuật toán đề xuất CDAB so với thuật toán gốc điển hình Girvan-Newman (GN) sử dụng độ đo trung tâm trung

  • Đề xuất thuật toán LREN (Label based Reduce Equivalence Nodes) rút gọn đồ thị dựa vào lớp đỉnh tương đương theo nguyên lý lan truyền nhãn và phát triển thuật toán LPAA (Label Propagation Algorithm on Abridged graph) cải tiến thời gian phát hiện các cộng đồng dựa vào nguyên lý lan truyền nhãn. Thực hiện các thực nghiệm đánh giá tính hiệu quả và thời gian thực hiện của thuật toán LPAA so với các thuật toán gốc điển hình LPA (Label Propagation Algorithm).

CÁC ỨNG DỤNG, KHẢ NĂNG ỨNG DỤNG TRONG THỰC TIỄN HOẶC NHỮNG VẤN ĐỀ CÒN BỎ NGỎ CẦN TIẾP TỤC NGHIÊN CỨU

Kết quả nghiên cứu của luận án là bài toán rút gọn đồ thị nhằm giảm thiểu không gian, thời gian phân tích những đồ thị mạng xã hội lớn, phức tạp, là một hướng nghiên cứu quan trọng được nhiều người nghiên cứu và ứng dụng trong nhiều các lĩnh vực khác nhau. Áp dụng bài toán rút gọn đồ thị để phát hiện cộng đồng trên mạng xã hội nhanh và hiệu quả hơn.

Do thời gian thực hiện của đề tài còn hạn hẹp, đề tài còn các vấn đề liên quan cần

được tiếp tục nghiên cứu như:


  • Tiếp tục thực hiện các nghiên cứu những công nghệ tiên tiến xử lý dữ liệu lớn (Big Data) và áp dụng để phân tích những mạng xã hội siêu lớn.

  • Tiếp tục thực hiện các nghiên cứu phát triển những thuật toán tìm các cấu trúc cộng

đồng chồng chéo trên đồ thị mạng xã hội sử dụng độ đo trung tâm trung gian cục bộ.


  • Tiếp tục phát triển các thuật toán song song để thực hiện đồng thời công việc phát hiện các cộng đồng trên mạng xã hội nhằm giảm thiểu thời gian tính toán trên các mạng xã hội quy mô siêu lớn.

XÁC NHẬN CỦA TẬP THỂ NGƯỜI HƯỚNG DẪN 

PGS.TS. Đoàn Văn Ban 

TS. Đỗ Thị Bích Ngọc 

NGHIÊN CỨU SINH

Nguyễn Xuân Dũng

INFORMATION ON DOCTORAL DISSERTATION

Title of the thesis:  STUDY ON GRAPH REDUCTION ALGORITHMS AND ITS APPLICATIONS IN SOCIAL NETWORK COMMUNITY DETECTION

Specified field of study: Information System  Code of specialty:                                       9.48.01.04

Name of PhD candidate:     Nguyen Xuan Dung Name of the research supervisors:

1.   Assoc. Prof. PhD. Doan Van Ban

2.  Do Thi Bich Ngoc

Academic Institution: Posts and Telecommunications Institute of Technology

THE SCIENTIFIC CONTRIBUTIONS

The scientific contributions of the thesis are as follows:


  • Proposing the REG (Reduce Equivalence Graph) algorithm to reduce the graph based on the equivalence class of the peak betweenness centrality methods. Perform experiments to evaluate the efficiency and execution time of the proposed algorithm against the original algorithm dictionary using the betweenness

  • Proposing the FBC (Fast algorithm for Betweenness Centrality) algorithm to improve the time to calculate the betweenness centrality measure and proposing the CDAB (Community Detection Algorithm based on Betweenness centrality) algorithm to improve the time to detect communities on the graph shortened social network based on the betweenness centrality. Perform experiments to evaluate the efficiency and execution time of the proposed CDAB algorithm compared with the typical original Girvan-Newman (GN) algorithm using the betweenness

  • Propose the LREN (Label based Reduce Equivalence Nodes) algorithm to reduce the graph based on the equivalence vertex layer according to the principle of label propagation and develop the LPAA (Label Propagation Algorithm on Abridged graph) algorithm to improve the community detection time of the based on the principle of label

propagation. Perform experiments to evaluate the efficiency and execution time of the

LPAA algorithm compared with the typical original algorithms LPA (Label Propagation Algorithm).

APPLICATIONS, PRACTICAL APPLICABILITY AND FURTHER STUDIES

The research result of the thesis is the problem of graph reduction to reduce the space and time to analyze large and complex social network graphs, which is an important research direction that many people research and apply in many different fields. Apply the graph reduction problem to detect communities on social networks faster and more efficiently.

Due to the limited implementation time of the project, the topic still has many related issues that need to be further studied such as:


  • Continuing to conduct research on advanced technologies for processing big data (Big Data) and applying them to analyze super large social

  • Continue to carry out studies to develop algorithms to find overlapping community structures on social network graphs using local betweenness centrality

  • Continue to develop parallel algorithms to simultaneously detect social networks to reduce computation time on large-scale social

Research supervisors

Assoc. Prof. PhD. Doan Van Ban

Dr. Do Thi Bich Ngoc 

Ph.D candidate

Nguyen Xuan Dung


 Luận án tiến sĩ

Tóm tắt Luận án tiến sĩ

Trang Thông tin Luận án tiếng việt 

Trang Thông tin Luận án Tiếng Anh