×

Mixed-case community detection problem in social networks: algorithms and analysis. (English) Zbl 1477.68541

Summary: The problem of detecting communities is one of the essential problems in the study of social networks. To devise the algorithms of community detection, one should first define high-quality communities. In fact, there are no agreed methods to measure the quality of the community. In this paper, we consider a novel objective function of this problem. Our goal is to maximize not only the average of the sum of edge weights within communities (i.e., average-case) but also the sum of edge weights within the minimum community (i.e., worst-case). To balance both the average-case and worst-case problems, we introduce a parameter into our objective function and call it the mixed-cased community detection problem. For the worst-case, we devise several approximation algorithms, such as the Greedy, Semi-Sandwich Approximation, and Local Search algorithms. For the average-case, an efficient Terminal-based algorithm is proposed. We prove that the best solution between the average-case and worst-case problems still can provide an approximate guarantee for any mixed-case community detection problem. Moreover, we devise a heuristic algorithm for our problem. Finally, we conduct the experiments in three networks. The experimental results indicate that our proposed methods can form a high-quality community partition.

MSC:

68W25 Approximation algorithms
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhang, W. Y. Yapu; Guo, Jianxiong; Wu, W., Mixed-case community detection problem in social networks, (The 14th Annual International Conference on Combinatorial Optimization and Applications. The 14th Annual International Conference on Combinatorial Optimization and Applications, COCOA, 2020 (2020))
[2] Weiss, R. S.; Jacobson, E., A method for the analysis of the structure of complex organizations, Am. Sociol. Rev., 20, 6, 661-668 (1955)
[3] Newman, M. E.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 2, Article 026113 pp. (2004)
[4] Mancoridis, S.; Mitchell, B. S.; Rorres, C.; Chen, Y.; Gansner, E. R., Using automatic clustering to produce high-level system organizations of source code, (Proceedings. 6th International Workshop on Program Comprehension. IWPC’98 (Cat. No. 98TB100242) (1998), IEEE), 45-52
[5] Kannan, R.; Vempala, S.; Vetta, A., On clusterings: good, bad and spectral, J. ACM, 51, 3, 497-515 (2004) · Zbl 1192.05160
[6] Von Luxburg, U., A tutorial on spectral clustering, Stat. Comput., 17, 4, 395-416 (2007)
[7] Hagen, L.; Kahng, A. B., New spectral methods for ratio cut partitioning and clustering, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 11, 9, 1074-1085 (1992)
[8] Tong, G.; Cui, L.; Wu, W.; Liu, C.; Du, D.-Z., Terminal-set-enhanced community detection in social networks, (IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications (2016), IEEE), 1-9
[9] Lu, W.; Chen, W.; Lakshmanan, L. V., From competition to complementarity: comparative influence diffusion and maximization, Proc. VLDB Endow., 9, 2, 60-71 (2015)
[10] Abbe, E., Community detection and stochastic block models: recent developments, J. Mach. Learn. Res., 18, 1, 6446-6531 (2017) · Zbl 1403.62110
[11] De Bacco, C.; Power, E. A.; Larremore, D. B.; Moore, C., Community detection, link prediction, and layer interdependence in multilayer networks, Phys. Rev. E, 95, 4, Article 042317 pp. (2017)
[12] Zeng, X.; Wang, W.; Chen, C.; Yen, G. G., A consensus community-based particle swarm optimization for dynamic community detection, IEEE Trans. Cybern., 50, 6, 2502-2513 (2019)
[13] Zhe, C.; Sun, A.; Xiao, X., Community detection on large complex attribute network, (Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2019)), 2041-2049
[14] Leskovec, J.; Lang, K. J.; Mahoney, M., Empirical comparison of algorithms for network community detection, (Proceedings of the 19th International Conference on World Wide Web (2010)), 631-640
[15] Taha, K., Disjoint community detection in networks based on the relative association of members, IEEE Trans. Comput. Soc.l Syst., 5, 2, 493-507 (2018)
[16] Chakraborty, T.; Ghosh, S.; Park, N., Ensemble-based overlapping community detection using disjoint community structures, Knowl.-Based Syst., 163, 241-251 (2019)
[17] Kelley, S.; Goldberg, M.; Magdon-Ismail, M.; Mertsalov, K.; Wallace, A., Defining and discovering communities in social networks, (Handbook of Optimization in Complex Networks (2012), Springer), 139-168 · Zbl 1248.91085
[18] Xie, J.; Kelley, S.; Szymanski, B. K., Overlapping community detection in networks: the state-of-the-art and comparative study, ACM Comput. Surv., 45, 4, 1-35 (2013) · Zbl 1288.68191
[19] Fortunato, S.; Hric, D., Community detection in networks: a user guide, Phys. Rep., 659, 1-44 (2016)
[20] Lu, Z.; Zhu, Y.; Li, W.; Wu, W.; Cheng, X., Influence-based community partition for social networks, Comput. Soc. Netw., 1, 1, 1-18 (2014)
[21] Wei, K.; Iyer, R. K.; Wang, S.; Bai, W.; Bilmes, J. A., Mixed robust/average submodular partitioning: fast algorithms, guarantees, and applications, (Advances in Neural Information Processing Systems (2015)), 2233-2241
[22] Goldschmidt, O.; Hochbaum, D. S., A polynomial algorithm for the k-cut problem for fixed k, Math. Oper. Res., 19, 1, 24-37 (1994) · Zbl 0809.90125
[23] Buchbinder, N.; Schwartz, R.; Weizman, B., Simplex transformations and the multiway cut problem, (Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (2017), SIAM), 2400-2410 · Zbl 1410.05193
[24] Călinescu, G.; Karloff, H.; Rabani, Y., An improved approximation algorithm for multiway cut, (Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (1998)), 48-52 · Zbl 1028.68220
[25] Chekuri, C.; Ene, A., Approximation algorithms for submodular multiway partition, (2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (2011), IEEE), 807-816 · Zbl 1292.68163
[26] Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M., The complexity of multiway cuts, (Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (1992)), 241-251
[27] Zachary, W. W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33, 4, 452-473 (1977)
[28] Girvan, M.; Newman, M. E., Community structure in social and biological networks, Proc. Natl. Acad. Sci., 99, 12, 7821-7826 (2002) · Zbl 1032.91716
[29] Newman, M. E., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 3, Article 036104 pp. (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.