ỨNG DỤNG PHƯƠNG PHÁP PHÂN CỤM PHỔ  TRONG BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG

Nguyễn Hiền Trinh; Vũ Vinh Quang

ỨNG DỤNG PHƯƠNG PHÁP PHÂN CỤM PHỔ TRONG BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG

Thông tin bài báo

Ngày nhận bài: 21/02/20 Ngày hoàn thiện: 21/05/20 Ngày đăng: 25/05/20

Các tác giả

1. Nguyễn Hiền Trinh, Trường Đại học Công nghệ thông tin và Truyền thông - ĐH Thái Nguyên
2. Vũ Vinh Quang , Trường Đại học Công nghệ thông tin và Truyền thông - ĐH Thái Nguyên

Tóm tắt

Ngày nay, phát hiện cộng đồng trên một mạng xã hội đang là hướng nghiên cứu quan trọng trong lĩnh vực khoa học máy tính. Mạng xã hội thường được biểu diễn dưới dạng cấu trúc dữ liệu đồ thị. Chính vì vậy, phát hiện cộng đồng trên mạng xã hội chủ yếu gắn liền với bài toán phân cụm trên đồ thị. Để giải quyết bài toán, đã có rất nhiều thuật toán được quan tâm nghiên cứu. Trong bài báo này, nhóm tác giả sẽ trình bày các kết quả nghiên cứu mới theo hướng tiếp cận sử dụng khái niệm spectrum (phổ) để đưa bài toán phân cụm đồ thị tổng quát về bài toán phân cụm trên véc tơ riêng số thực nhằm giảm số chiều của tập dữ liệu, đồng thời kết hợp kỹ thuật tối ưu hóa hàm Min-cut nhờ sử dụng ma trận Laplace. Hướng tiếp cận này sẽ giảm độ phức tạp tính toán của thuật toán phát hiện cấu trúc cộng đồng trên mạng xã hội. Các kết quả thực nghiệm chạy trên các bộ số liệu thực tế đã khẳng định tính hữu hiệu của thuật toán đề xuất.

Từ khóa

Khoa học máy tính; mạng xã hội; cấu trúc cộng đồng; khai phá dữ liệu đồ thị; phân cụm đồ thị; phát hiện cộng đồng; phổ.

Toàn văn:

PDF

Tài liệu tham khảo

[1]. R. S. Weiss, and E. Jacobsen, “A Method for the analysis of the strucre of complex organizations,” American Sociological review, vol. 20 , pp. 661-668, 1999.

[2]. G. W. Flake, and W. Lawrence, “Efficient identìication of web communities,” In Proceedings of the sixth ACM SIGKDD, 2000.

[3]. F. Radicchi, and F. Castellano, “Defining and identifying communities in network,” Proceedings of the National Academy of Sciences of the United States of America, 2004.

[4]. F. Radicchi, and S. Fortunato, “Benchmark graphs for testing community detection algorithms,” Physical review E., vol. 78, pp. 046110, 2008.

[5]. M. Girvan M, and M. E. Newman, “Community structure in social and biological networks,” Physical review E., vol. 99, no. 12, pp. 7821-7826, 2002.

[6]. J. R. Tyler, and D. M. Wilkinson, “Automated discovery of community structure within organization,” Physical review E, vol. 15, pp. 723-739, 2003.

[7]. S. Gregory, An algorithm to find overlapping community structure in network. Springer Heidelberg, 2007.

[8]. U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical sociology, vol. 2, pp. 163-177, 2007.

[9]. F. Harary, Graph Theory. Addison Wesley Reading MA, 1996

[10]. S. Fortunato, “Community Detection in Graphs,” Physics Reports, vol. 486, pp. 75-174, 2010

[11]. V. Zografos, and K. Nordberg, “Introduction in Spectral Clustering,” Physics Reports, vol. 17, pp. 321-330, 2012

[12]. D. Hamad, Constrained Spectral embedding for k-way data clusting. LISIC ULCO, 2014.

[13]. U. von Luxburg, A Tutorial on Spectral Clustering. Max Planck Institute for Biological Cybernetics, 2007.

[14]. L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, pp. 35-41, 2007.

[15]. M. Clarles, “Spectral Clustering,” A quick Overview, vol. 22, pp. 115-124, 2012

[16]. H. Abdi, The eigenvector-Decomposition. The University of Texas at Dallas, 2007.

[17]. B. Ruhnau, “Eigenvector-centrality – a node-centrality,” Social Networks, vol. 22, pp. 357-365, 2015

[18]. M. E. Newman, and M. Girvan, “Finding and evaluating community structure in networks,” Phys Rev E Stat Nonlin Soft Matter Phys, vol. 21, pp. 235-251, 2004.

[19]. X. Liu, H. M. Cheng, and Z. Y. Zhang, “Evaluation of community detection methods,” Physics Reports, vol. 10, pp. 251-265, 2019.

[20]. S. M. Wagner, “A simple min cut algorithm,” J.ACM, vol. 44, pp. 585-591, 2007.

[21]. Wagner, “Between min cut and graph bisection,” London Springger, vol. 711, pp. 744-750, 2013.

[22]. J. Leskovec, and Krevl, “A. SNAP Datasets tanford large network dataset collection,” 2014. [Online]. Available: https://snap.stanford.edu. [Accessed Oct. 19, 2019].

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ