Luận án 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

1. Tính cấp thiết của luận án

Trong vài thập kỷ gần đây, các mạng xã hội (SN - Social Networks) đã trở nên

phổ biến và thu hút được sự chú ý của các nhà khoa học thuộc các ngành khác nhau,

như xã hội học, dịch tễ học, kinh tế, khoa học máy tính, viễn thông và nhiều ngành

khác. Mạng xã hội đang phát triển mạnh mẽ tại khắp mọi nơi, trên mọi quốc gia và

trở thành phương tiện quan trọng, không thể thiếu trong cuộc sống để kết nối quan hệ

của mọi người trong xã hội. Hiện nay Facebook, Twitter, Youtube, WhatsApp,

Instagram, Google+, Linkedin, là những mạng xã hội phổ biến được nhiều người

sử dụng nhất.

Phân tích mạng xã hội (SNA - Social Network Analysis) là một tập hợp các

phương pháp thu thập và xử lý dữ liệu, các khái niệm, các lý thuyết nhằm mô tả và

phân tích các mối quan hệ giữa các thực thể trong mạng, các quy luật hình thành và

biến đổi của những mối quan hệ đó, và nhất là làm sáng tỏ những ảnh hưởng tương

quan của các mối quan hệ trong xã hội (hay cấu trúc của mạng) đối với hành vi của

các thực thể tham gia. Ví dụ: Phân tích thống kê mạng xã hội, phát hiện cộng đồng

trên mạng xã hội, dự đoán liên kết, phân tích vai trò và phân loại các tác nhân trên

mạng xã hội, Trong lĩnh vực phân tích mạng xã hội, việc phân tích và phát hiện

các cộng đồng (communities detection) trên mạng xã hội mang nhiều ý nghĩa quan

trọng và có nhiều ứng dụng trong các lĩnh vực khác nhau như xã hội học, sinh học,

khoa học máy tính, kinh tế, chính trị, . Cộng đồng mạng xã hội là một nhóm các

thực thể trong mạng xã hội có những tính chất tương tự nhau, liên kết chặt chẽ với

nhau và cùng đóng một vai trò nhất định. Cộng đồng mạng xã hội là những cấu trúc

xã hội được xác định dựa trên những mối quan hệ, có mối quan tâm chung như sở

thích, lĩnh vực mà các thành viên của cộng đồng cùng quan tâm, tham gia hay một

mục tiêu, dự án chung, vị trí địa lý, hoặc nghề nghiệp. Việc phát hiện và phân tích

các cộng đồng mạng xã hội sẽ cung cấp cho chúng ta những thông tin quý giá để hiểu

biết và hình dung được những cấu trúc của mạng.2

Phát hiện cộng đồng trên mạng xã hội cũng là một nhiệm vụ quan trọng hàng

đầu trong phân tích mạng xã hội. Do tầm quan trọng của các cộng đồng mạng xã hội

và khả năng ứng dụng to lớn của chúng trong các lĩnh vực khác nhau đã có nhiều các

thuật toán phát hiện cộng đồng trên mạng xã hội đã được đề xuất. Tuy nhiên, hầu hết

các thuật toán chưa đạt được hiệu quả trong việc phát hiện cộng đồng trên các mạng

xã hội quy mô rất lớn hiện nay. Đồng thời, cùng với sự phát triển mạnh mẽ của công

nghệ thông tin thì việc sử dụng các mạng xã hội của chúng ta đang phát triển theo cấp

số nhân và hệ quả là quy mô của mạng xã hội phát triển nhanh chóng và trở nên khổng

lồ. Điều này dẫn đến việc phát hiện cộng đồng trên các mạng xã hội quy mô rất lớn

không thể giải quyết bằng các thuật toán truyền thống do độ phức tạp về thời gian và

không gian tính toán. Có nghĩa là, hầu hết các thuật toán hiện có không thể được mở

rộng đến kích thước khổng lồ của các mạng xã hội. Để giải quyết được thách thức đặt

ra, cần đề xuất các phương pháp giảm kích thước của mạng xã hội để thực hiện phát

hiện cộng đồng mạng xã hội hiệu quả đồng thời vẫn phải đảm bảo được các tính chất

của cộng đồng mạng xã hội ban đầu là rất ý nghĩa, cần thiết và quan trọng.

Trong những năm gần đây, việc phân tích và phát hiện cộng đồng mạng xã hội

là một trong những lĩnh vực nghiên cứu chính trong khai thác, phân tích mạng xã hội.

Các thuật toán phát hiện cộng đồng trên mạng xã hội được nhiều người tập trung quan

tâm nghiên cứu và phát triển ứng dụng [8], [9], [28], [42], [102], [118], [119], [120],

. Về cơ bản, các thuật toán phát hiện cộng đồng mạng xã hội được chia thành 4

nhóm. Nhóm thuật toán phát hiện cộng đồng truyền thống, nhóm thuật toán phát hiện

cộng đồng dựa trên tối ưu hóa độ đo đơn thể, nhóm thuật toán phát hiện cộng đồng

dựa vào độ đo trung tâm trung gian, và nhóm thuật toán phát hiện cộng đồng dựa trên

nguyên lý lan truyền nhãn. Trong đó, nhóm thuật toán phát hiện cộng đồng truyền

thống bao gồm các thuật toán phân cụm đồ thị, phân cụm phân cấp, phân cụm phân

hoạch, phân cụm theo phổ [31], [76], [115]. Nhóm thuật toán phát hiện cộng đồng

dựa trên tối ưu hóa độ đo đơn thể bao gồm thuật toán tìm kiếm tham lam, mô phỏng

luyện kim, tối ưu hoá mở rộng và các thuật toán tiến hoá [15], [78], [91]. Nhóm thuật

toán phát hiện cộng đồng dựa vào độ đo trung tâm trung gian bao gồm họ thuật toán3

Girvan-Newman theo độ đo trung tâm trung gian của cạnh, phân chia đỉnh [33], [34],

[38], [75]. Và cuối cùng là nhóm thuật toán dựa trên nguyên lý lan truyền nhãn bao

gồm họ các thuật toán dựa vào nguyên lý lan truyền nhãn [13], [59], [81], [109],

[110].

pdf 130 trang chauphong 16/08/2022 14920
Bạn đang xem 20 trang mẫu của tài liệu "Luận án 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Luận án 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

Luận án 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
BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
NGUYỄN XUÂN DŨNG 
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 
LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN 
HÀ NỘI - 2021 
BỘ THÔNG TIN VÀ TRUYỀN THÔNG 
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG 
NGUYỄN XUÂN DŨNG 
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 
LUẬN ÁN TIẾN SĨ KỸ THUẬT 
NGƯỜI HƯỚNG DẪN KHOA HỌC: 
 1. PGS.TS Đoàn Văn Ban 
 2. TS. Đỗ Thị Bích Ngọc 
HÀ NỘI - 2021 
 LỜI CAM ĐOAN 
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. 
Các số liệu, kết quả nêu trong luận án là trung thực và chưa từng được 
công bố trong bất cứ công trình nào. 
TÁC GIẢ 
Nguyễn Xuân Dũng 
 LỜI CẢM ƠN 
Qua luận án này tôi xin chân thành cảm ơn PGS.TS Đoàn Văn Ban và 
TS. Đỗ Thị Bích Ngọc đã tận tình giúp đỡ, động viên, định hướng, hướng dẫn 
tôi nghiên cứu và hoàn thành luận án này. 
Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong Học viện Công nghệ 
Bưu chính Viễn thông đã tận tình giảng dạy và giúp đỡ tôi trong suốt khóa học. 
Tôi cũng xin cảm ơn PGS.TS Lê Nhật Thăng - Trưởng Khoa Đào tạo Sau Đại 
học của Học viện công nghệ bưu chính viễn thông, TS. Nguyễn Duy Phương - 
Trưởng Khoa Công nghệ thông tin của Học viện công nghệ bưu chính viễn 
thông và PGS.TS Phạm Thọ Hoàn - Giám đốc Trung tâm Khoa học Tính toán 
của Trường Đại học Sư phạm Hà Nội đã giúp đỡ tôi trong quá trình thực hiện 
luận án. 
Tác giả chân thành mong nhận được những ý kiến đóng góp từ các Thầy, 
Cô giáo, các nhà khoa học và bạn bè đồng nghiệp. 
Trân trọng cám ơn. 
i 
MỤC LỤC 
MỤC MỤC............................................................................................................................................... i 
DANH MỤC CÁC CHỮ VIẾT TẮT................................................................................................. iv 
DANH MỤC CÁC KÍ HIỆU TOÁN HỌC ........................................................................................ v 
DANH MỤC CÁC THUẬT NGỮ ..................................................................................................... vi 
DANH MỤC HÌNH VẼ ..................................................................................................................... viii 
DANH MỤC CÁC BẢNG .................................................................................................................. ix 
MỞ ĐẦU ................................................................................................................................................. 1 
1. Tính cấp thiết của luận án .................................................................................................................... 1 
2. Mục tiêu của luận án ............................................................................................................................ 4 
3. Đối tượng nghiên cứu của luận án ...................................................................................................... 5 
4. Phạm vi nghiên cứu của luận án ......................................................................................................... 5 
5. Phương pháp nghiên cứu của luận án ................................................................................................ 5 
6. Các đóng góp của luận án ................................................................................................................... 6 
7. Bố cục của luận án ............................................................................................................................... 6 
CHƯƠNG 1. TỔNG QUAN RÚT GỌN ĐỒ THỊ VÀ PHÁT HIỆN CỘNG ĐỒNG TRÊN 
MẠNG XÃ HỘI ................................................................................................................................... 8 
1.1. Mạng xã hội .......................................................................................................................8 
1.2. Một số hệ số đo quan trọng trên đồ thị mạng xã hội .............................................. 10 
1.2.1. Hệ số cố kết mạng ............................................................................... 12 
1.2.2. Các hệ số đo tính trung tâm của tác nhân ............................................ 12 
1.3. Bài toán phát hiện cộng đồng mạng xã hội .............................................................. 18 
1.3.1. Cộng đồng mạng xã hội ...................................................................... 18 
1.3.2. Các thuật toán phát hiện cộng đồng mạng xã hội............................. 21 
1.4. Bài toán rút gọn đồ thị .................................................................................................. 34 
1.4.1. Sự cần thiết phải rút gọn đồ thị mạng xã hội ....................................... 34 
1.4.2. Các thuật toán rút gọn đồ thị ............................................................... 35 
1.5. Các độ đo đánh giá thuật toán phát hiện cộng đồng mạng xã hội  38 
ii 
1.5.1. Độ đo đơn thể mô đun Q ..................................................................... 38 
1.5.2. Độ đo F-measure................................................................................. 39 
1.5.3. Độ đo dựa trên lý thuyết thông tin ....................................................... 40 
1.6. Kết luận chương 1 ......................................................................................................... 41 
CHƯƠNG 2. THUẬT TOÁN RÚT GỌN ĐỒ THỊ MẠNG XÃ HỘI DỰA VÀO ĐỘ 
ĐO TRUNG TÂM TRUNG GIAN VÀ NGUYÊN LÝ LAN TRUYỀN NHÃN 43 
2.1. Giới thiệu ...................................................................................................................... 44 
2.2. Các tính chất của độ đo trung tâm trung gian trên đồ thị mạng xã hội ...................... 45 
2.2.1. Các lớp đỉnh treo tương đương............................................................ 45 
2.2.2. Các lớp đỉnh sườn tương đương .......................................................... 50 
2.2.3. Các lớp đỉnh đồng nhất tương đương .................................................. 56 
2.3. Thuật toán rút gọn đồ thị dựa vào độ đo trung tâm trung gian ................................... 59 
2.4. Thuật toán rút gọn đồ thị dựa vào nguyên lý lan truyền nhãn .................................. 64 
2.4.1. Thuật toán lan truyền nhãn .................................................................. 64 
2.4.2. Thuật toán rút gọn đồ thị dựa vào nguyên lý lan truyền nhãn ...... 67 
2.5. Thực nghiệm và đánh giá .......................................................................................... 73 
2.5.1. Bộ dữ liệu ........................................................................................... 73 
2.5.2. Cài đặt thực nghiệm ............................................................................ 74 
2.5.3. Kết quả thực nghiệm ........................................................................... 75 
2.6. Kết luận chương 2 ....................................................................................................... 77 
CHƯƠNG 3. ÁP DỤNG THUẬT TOÁN RÚT GỌN ĐỒ THỊ ĐỂ PHÁT HIỆN 
CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI ............................................................................ 78 
3.1. Giới thiệu........................................................................................................................ 79 
3.2. Thuật toán tính nhanh độ đo trung tâm trung gian trên đồ thị mạng xã hội rút gọn . 79 
3.2.1. Duyệt đồ thị theo chiều rộng ............................................................... 79 
3.2.2. Thuật toán tính nhanh độ đo trung tâm trung gian ............................... 80 
3.3. Thuật toán phát hiện cộng đồng mạng xã hội trên đồ thị rút gọn dựa vào độ đo trung 
tâm trung gian. ..................................................................................................................... 84 
3.4. Thuật toán lan truyền nhãn phát hiện cộng đồng trên đồ thị mạng xã hội rút gọn .... 86 
iii 
3.5. Thực nghiệm và đánh giá .............................................................................................. 88 
3.5.1. Cài đặt thực nghiệm ............................................................................ 89 
3.5.2. Đánh giá thực nghiệm ......................................................................... 92 
3.6. Kết luận chương 3 ....................................................................................................... 101 
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ...................................................................................... 102 
DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN .................................. 104 
TÀI LIỆU THAM KHẢO ................................................................................................................. 105 
iv 
DANH MỤC CÁC CHỮ VIẾT TẮT 
TỪ VIẾT TẮT DẠNG ĐẦY ĐỦ 
BIRCH Balanced iterative regucing and clustering using hierarchies 
BFS Breadth first search 
CDAB Community detection algorithm based on betweenness 
DAG Directed acyclic graph 
EBC Edge betweenness centrality 
EAGLE Agglomerative hierarchical clustering based on maximal clique 
ELPA Edge label propagation algorithm 
EMLPA Balanced multi labed propagation 
FBC Fast algorithm for betweenness centrality 
FFS Forest Fire Sampling 
GN Girvan-Newman 
HLPA Hybrid label propagation algorithm 
LREN Label based reduce equivalence nodes 
LPA Label propagation algorithm 
LPAA Label propagation algorithm on abridged graph 
MAA Majid Arasteh and Alizadeh 
NMI Normal mutual information 
OLP Optimized label propagation 
RE Random Edge Sampling 
RNE Random Node - Edge Sampling 
REG Reduce equivalence graph 
SES Snowball Expansion Sampling 
SN Social network 
SNA Social network analysis 
SNAP Stanford large network dataset collection 
v 
DANH MỤC CÁC KÝ HIỆU TOÁN HỌC 
KÝ HIỆU Ý NGHĨA A"# Ma trận liền kề 
d(x, y) Khoảng cách giữa đỉnh x và y 
G Đồ thị 
V Tập đỉnh 
E Tập cạnh D% Hệ số cố kết của đồ thị G 
CD(v) Hệ số trung tâm trực tiếp của đỉnh v 
deg(v) Số bậc của đỉnh v 
R Tập số nguyên 
CCl(v) Hệ số trung tâm lân cận của đỉnh v σ'( Số đường đi ngắn nhất đi v đến t 
CB(v) Độ đo trung tâm trung gian của đỉnh v d" Bậc của đỉnh i d# Bậc của đỉnh j 
G(u) Tập các đỉnh liền kề với u và kể cả u 
DAGX Đồ thị định hướng, phi chu trình gốc X 
n Số đỉnh của đồ thị 
k Bậc của đỉnh 
L(u) Nhãn của đỉnh u 
L(v) Nhãn của đỉnh v 
vi 
DANH MỤC CÁC THUẬT NGỮ 
THUẬT NGỮ TIẾNG ANH THUẬT NGỮ TIẾNG VIỆT 
Betweenness centrality Độ đo trung tâm trung gian 
Breadth first search Duyệt theo chiều rộng 
Closeness centrality Hệ số trung tâm lân cận 
Computer vision Thị giác máy tính 
Communication network Mạng truyền thông 
Communities detection Phát hiện cộng đồng 
Community social Cộng đồng mạng xã hội 
Cyclic workflow graph  ... Krevl A.: SNAP Datasets: Stanford large network dataset 
collection, Avaiable: https://snap.stanford.edu (2014). 
[61]. Leskovec, J., Faloutsos, C.: Sampling from large graphs. In Proc. of the 20th 
ACM SIGKĐ Intl. Conf. On Knowledge Discovery and Data Mining, pages 631-636, 
(2006). 
[62]. Li, W., Kang, Q., Kong, H., Liu, C. and Kang, Y.: A novel iterated greedy 
algorithm for detecting communities in complex network, Social Network Analysis 
and Mining, pp.10-29, (2020). 
[63] Lin, H., Zhap, Z., Li, H. and Chen, Z.: A novel graph reduction algorithm to 
identify structural conflicts, in Proc. 35th Hawaii Int. Conf. Syst. Sci., vol. 9, p. 289, 
(2002). 
[64]. Linhares, Claudio D. G., Bruno A. N. Travençolo, Jose Gustavo S. Paiva, 
and Luis E C Rocha.: Visual analysis for evaluation of community detection 
algorithms. Multimedia Tools and Applications, volume 79, pages 17645-17667 
(2020). 
[65]. Liu, W., Jiang, X., Pellegrini, M.: Discovering communities in complex 
networks by edge label propagation. Sci Rep, 6: 22470. (2016). 
[66]. Liu, X, and Murata, T.: Advanced modularity-specialized label propagation 
algorithm for detecting communities in networks. Physica A. 389(7):1493-1500, 
(2010). 
111 
[67]. Luo, W., Lu, L., Ni, L., Zhu, W. and Ding, W.: Local community detection by 
the nearest nodes with greater centrality, Information Sciences, 517:377-392, (2020). 
[68]. Lusseau, D., Newman, M. E.: Identifying the role that animals play in their 
social networks, Proceedings of the Royal Society of London B: Biological Sciences 
271 (Suppl 6) S477-S481 (2004). 
[69]. MacQueen, J.: Some methods for classification and analysis of multivariate 
observations. In Proceedings of the fifth Berkeley symposium on mathematical 
statistics and probability, (Vol. 1, pp. 281-297, Vol. 14): Oakland, CA, USA (1967). 
[70]. Maiya AS, Berger-Wolf TY.: Sampling community structure. In: Proceedings 
of the 19th international conference on World wide web, WWW’10, pp 701-710, 
(2010). 
[71]. Mislove, A. E.: Online social networks: measurement, analysis, andapplication 
stodistributed information systems. ProQuest, Rice University, Ann Arbor, United 
States (2009). 
[72] Moosavi, S. A., Jalali, M., Misaghian, N., Shamshirband, S., & Anisi, M. H.: 
Community detection in social networks using user frequent pattern mining. 
Knowledge and Information Systems, 51(1), 159-186, (2017). 
[73]. Mudduri, K., Ediger, D., Jiang, K., Bader, D. A., Chavarria-Miranda, D. G.: A 
faster paralel algorithm and effcient multithreaded implementations for evaluating 
Betweenness centrality on massive datasets. In IPDPS. (2009). 
[74] Nakajima, K. and Shudo. K.: Estimating Properties of Social Networks via 
Random Walk considering Private Nodes. KDD 2020: 720-730 (2020). 
[75] Nam, P. Nguyen., Thang, N. Dinh., Ying, Xuan., and My T. Thai.: Adaptive 
algorithms for detecting community structure in dynamic social networks, in 
INFOCOM, 2011 Proceedings IEEE, pp. 2282 - 2290, (2011). 
[76]. Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in 
networks. Physical Review E: Statistical, Nonlinear, and Soft Matter 
Physics. 69(2)026113 (2004). 
112 
[77]. Newman, M. E. J.: Finding community structure in networks using the 
eigenvectors of matrices. Physical Review E Vol.74, Article ID 036104. (2006). 
[78]. Newman, M. E. J.: Modularity and community structure in networks. 
Proceedings of the National Academy of Sciences of the United States of 
America. 103(23):8577-8582, (2006). 
[79]. Newman, M. E. J.: Scientific collaboration networks: II. Shortest paths, 
weighted networks, and centrality. Phys. Rev. E 64, 016132 (2001). 
[80]. Newman, M. E.: Fast algorithm for detecting community structure in networks. 
Physical review E, 69(6), 066133 (2004). 
[81]. Newman, M.: A measure of betweenness centrality based on random walks. 
Social Networks, 27(1):39-54, (2005). 
[82]. Pirouz M., Zhan. J.: Optimized Label Propagation Community Detection on Big 
Data Networks, Association for Computing Machinery, ACM ISBN 978-1-4503-
6358-7/18/03, (2018). 
[83]. Potterat, J., Phillips-Plummer, L., Muth, S., Rothenberg, R., Woodhouse, D., 
Maldonado-Long, T., Zimmerman, H., and Muth, J.: Risk network structure in the 
early epidemic phase of HIV transmission in Colorado Springs, Sexually Transmitted 
Infections, 78, pp. 159-163, (2002). 
[84]. Puzis, R., Zilberman, P., Elovici, Y., Dolev, S, Brandes, U.: Heuristics for 
Speeding up Betweenness centrality Computation, ASE/IEEE International 
Conference on Privacy, Security, Risk and Trust. (2012). 
[85]. Raghavan, U. N., Albert, R., and Kumara S.: Nearlinear time algorithm to detect 
community structures in large-scale networks. Physical Review E, 76(3):036106, 
(2007). 
[86]. Rand, W. M.: Objective Criteria for the Evaluation of Clustering Methods. 
Journal of the American Statistical Association 66, 846 (1971). 
[87]. Riondato, M., Kornaropoulos, E. M.: Fast approximation of Betweenness 
centrality through sampling WSDM’14, pages 413-422. (2014). 
113 
[88]. Rossetti G., Pappalardo L., Rinzivillo S.: A novel approach to evaluate 
community detection algorithms on ground truth. Complex Networks VII, 133-144, 
(2016). 
[89] Sadiq, W. and Orlowska, M. E.: Analyzing Process Models Using Graph 
Reduction Techniques, Information Systems, 25(2): 117-134, (2000). 
[90] Sadiq, W. and Orlowska, M. E.: Applying Graph Reduction Techniques for 
Identifying Structural Conflicts in Process Models, Springer-Verlag Berlin 
Heidelberg (1999). 
[91]. Sariyuce, A. E., Saule, E., Kaya, K., Catalyurek, U. V.: Shattering and 
compressing networks for Betweenness centrality. In SDM, (2013). 
[92]. Satuluri, V. and Parthasarathy, S.: Scalable graph clustering using stochastic 
flows: applications to community discovery. SIGKDD, pages 737-746, (2009). 
[93] Scheuermann, B. and Rosenhahn, B.: SlimCuts: GraphCuts for High Resolution 
Images Using Graph Reduction, Energy Minimization Methods in Computer Vision 
and Pattern Recognition (EMMCVPR), July (2011). 
[94]. Schuetz, P., and Caflisch, A.: Efficient modularity optimization by multistep 
greedy algorithm and vertex mover refinement. Physical Review E. 77(4)046112, 
(2008). 
[95]. Scott, J.: Social network analysis: a Handbook. London: SAGE publications, 
(1991). 
[96]. Shamma, D. A., Kennedy, L., Churchill, E. F.: Tweet the Debates: 
Understanding Community Annotation of Uncollected Sources, In Proceedings 
of the first SIGMM workshop on Social media, ACM, USA, (2009). 
[97]. Shi, J., and J. Malik: Normalized cuts and image segmentation. IEEE 
Transactions on Pattern Analysis and Machine Intelligence, 22(8): 888 - 905 (2000). 
[98]. Staudt, C. L., Sazonovs, A., Meyerhenke, H.: NetworKit: A tool suite for large-
scale complex network analysis. Network Science, 4(4), 508-530, (2016). 
114 
[99]. Steinhaeuser, K., Chawla, N. V.: Identifying and evaluating community 
structure in complex networks. Pattern Recognition Letters, 31(5): pp. 413-421, 
(2010). 
 [100]. Stumpf, M. P., Wiuf C., and May, R. M.: Subnets of scale-free networks are 
not scale-free: sampling properties of networks. Proc.Natl.Acad. Sci.U.S.A, 102(12): 
4221-4224, (2005). 
[101]. Tan, G., Tu, D., Sum, N.: A parallel algorithm for computing Betweenness 
centrality. In ICPP. (2009). 
[102]. Tang, L. and Liu, H.: Community detection and mining in social media. 
Synthesis Lecftures on Data Mining and Knowledge Discovery, 2(1), pages 1-137, 
(2010). 
[103] Tripathy, A., Yelick, K., Buluc, A.: Reducing Communication in Graph Neural 
Network Training, SC20, IEEE (2020). 
[104]. Wang, T., Qian, X., Wang, X.: HLPA: A hybrid label propagation algorithm 
to find communities in large-scale networks// IEEE, International Conference on 
Awareness Science and Technology. IEEE, :135-140. (2015). 
[105]. Wasserman, S., Faust, K.: Social network analysis: methods and applications, 
volume 8 of structural analysis in the social sciences. Cambridge University Press, 
Cambridge (1994). 
[106]. Wellman, Barry and Berkowitz S. D.: Social Structures: A Network Approach. 
Cambridge: Cambridge University Press (1988). 
[107]. Whang JJ, Sui X, Dhillon IS.: Scalable and memory-efcient clustering of large-
scale social networks. In: 2012 IEEE 12th international conference on data mining, 
ICDM’12, pp 705-714, (2012). 
[108]. Wilson, R. J.: Introduction to Graph Theory. Pearson Publisher, 5 ed (2010). 
[109]. Wu, Z. H., Lin, Y. F., Gregory, S.: Balanced multi-label propagation for 
overlapping community detection in social networks. Journal of Computer Science 
and Technology, 27 (3): 468 - 479. (2012). 
115 
[110]. Xie, J., Szymanski, B. K.: Towards linear time overlapping community 
detection in social network, Pacific-Asia Conference on Knowledge Discovery and 
Data Mining. Springer, Berlin, Heidelberg,: 25 - 36. (2012). 
[111] Xu, Y, Salapaka, S. M., and Beck, C. L.: On reduction of graphs and Markov 
chain models, in Proc. CDC-ECE, pp.2317-2322, (2011). 
[112]. Yang Z, Algesheimer R, Tessone CJ.: A comparative analysis of community 
detection algorithms on artificial networks. Scientific Reports, 6, (2016). 
[113]. Yang, J., Leskovec, J.: Overlapping community detection at scale: a 
nonnegative matrix factorization approarch. In proceedings of the sixth ACM 
international conference on Web search and data mining. Pages 587-596. ACM, 
(2013). 
[114]. Yin C, Zhu S, Chen H, Zhang B, David B,: A method for community detection 
of complex networks based on hierarchical clustering. IJDSN 2015, 849140:1-
849140:9, (2015). 
[115]. Zachary W.: “An information flow model for conflict and fission in small 
groups”, Journal of Anthropological Research, vol.33, pages 452-473. (1977). 
[116]. Zhang, A. P. , Ren, G., Jia, B. Z., Cao, H., Zhang, S.B.: Generalization of label 
propagation algorithm in complex networks. Proceedings of the 25th IEEE Chinese 
Control and Decision Conference; Guiyang, China. pp. 1306-1309, (2013). 
[117]. Zhang, A., Ren, G., Lin, Y., Jia, B., Cao, H., Zhang, J., and Zhang. 
S.: Detecting Community Structures in Networks by Label Propagation with 
PREGiction of Percolation Transition, Hindawi Publishing Corporation, the 
Scientific World Journal Volume 2014, Article ID 148686, 14 pages, (2014). 
[118]. Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: an efficient data clustering 
method for very large databases, Proceedings of the 1996 ACM SIGMOD 
international conference on Management of data - SIGMOD'96. pp. 103-
114. doi:10.1145/233269.233324, (1996). 
116 
[119]. Zhao, F. and Tung, A. K.: Large scale cohesive subgraphs discovery for social 
network visual analysis. VLDB, pages 85-96, (2012). 
[120]. Zhu, X., Ghahramani, Z.: Learning from labeled and unlabeled data with label 
propagation. CMU CALD tech report CMU-CALD-02-107, (2002). 

File đính kèm:

  • pdfluan_an_nghien_cuu_cac_thuat_toan_rut_gon_do_thi_va_ung_dung.pdf
  • pdfLA_Nguyễn Xuân Dũng_TT.pdf
  • pdfNguyễn Xuân Dũng_E.pdf
  • pdfNguyễn Xuân Dũng_V.pdf