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).