Jabbour, Said; Mhadhbi, Nizar; Raddaoui, Badran; Sais, Lakhdar SAT-based models for overlapping community detection in networks. (English) Zbl 1445.68201 Computing 102, No. 5, 1275-1299 (2020). Summary: Communities in social networks or graphs are sets of well-connected, overlapping vertices. Network community detection is a hot research topic in social, biological and information networks analysis. The effectiveness of a community detection algorithm is determined by accuracy in finding the ground-truth communities. In this article, we present two models to detect overlapping communities in large complex networks. In the first model, we introduce a parametrized notion of community, called \(k\)-linked community, that allows us to characterize a vertex/edge centered \(k\)-linked community with bounded diameter. Such community possesses a vertex/edge with a distance at most \(\frac{k}{2}\) from any other vertex of that community. Next, we show how the problem of detecting vertex/edge centered \(k\)-linked communities can be expressed as a Partial Max-SAT optimization problem. Then, we propose a post-processing strategy to further enhance the overlaps between the final communities. Our second model called preference-based centroid model aims to constrain the choice of centroids communities in the first model. This new framework allows to integrate more easily the user preferences in order to discover high quality communities by selecting the most central vertices. For this, we exploit Weighted Partial Max-SAT to solve the underlying optimization problem. We evaluate the proposed frameworks empirically against several high-performing methods, with respect to three evaluation metrics and scalability, on a number of real-life datasets. The experimental results show that our algorithms outperform existing state-of-the-art methods in detecting relevant communities. MSC: 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 05C82 Small world graphs, complex networks (graph-theoretic aspects) 91D30 Social networks; opinion dynamics Keywords:social network; overlapping community detection; artificial intelligence; Max-SAT; weighted partial Max-SAT; preferences Software:SNAP; GraphBase; WPM3; CFinder PDFBibTeX XMLCite \textit{S. Jabbour} et al., Computing 102, No. 5, 1275--1299 (2020; Zbl 1445.68201) Full Text: DOI References: [1] Adamcsek, B.; Palla, G.; Farkas, IJ; Derényi, I.; Vicsek, T., Cfinder: locating cliques and overlapping modules in biological networks, Bioinformatics, 22, 8, 1021-1023 (2006) [2] Ahn, YY; Bagrow, JP; Lehmann, S., Link communities reveal multiscale complexity in networks, Nature, 466, 761-764 (2010) [3] Ansótegui C, Didier F, Gabàs J (2015) Exploiting the structure of unsatisfiable cores in MaxSAT. In: IJCAI, pp. 283-289 [4] Ansótegui, C.; Gabàs, J., WPM3: an (in)complete algorithm for weighted partial MaxSAT, Artif Intell, 250, 37-57 (2017) · Zbl 1419.68090 [5] Biere A, Heule M, van Maaren H, Walsh T (2009) Frontiers in Artificial Intelligence and Applications. In: Handbook of satisfiability, vol 185. ISBN: 978-1-60750-376-7 · Zbl 1183.68568 [6] Dickinson, B.; Valyou, B.; Hu, W., A genetic algorithm for identifying overlapping communities in social networks using an optimized search space, Soc Netw, 2, 4, 1-9 (2013) [7] Chen W, Liu Z, Sun X, Wang Y (2011) Community detection in social networks through community formation games. In: IJCAI, pp 2576-2581 [8] Cheng, J.; Leng, M.; Li, L.; Zhou, H.; Chen, X., Active semi-supervised community detection based on must-link and cannot-link constraints, PLoS, 9, 10, 1-18 (2014) [9] Comellas, F.; Ozón, J.; Peters, JG, Deterministic small-world communication networks, Inf Process Lett, 76, 1, 83-90 (2000) · Zbl 1338.68012 [10] Evans, TS, Clique graphs and overlapping communities, J Stat Mech Theory Exp, 12, P12037 (2010) [11] Farkas, IJ; Abel, D.; Palla, G.; Vicsek, T., Weighted network modules, New J Phys, 9, 180 (2007) [12] Fortunato, S., Community detection in graphs, Phys Rep, 486, 75-174 (2010) [13] Ganji M, Bailey J, Stuckey PJ (2017) A declarative approach to constrained community detection. In: CP, pp 477-494 [14] Ghoshal AK, Das N (2017) On diameter based community structure identification in networks. In: ICDCN, p 41 [15] Gilpin S, Davidson IN (2011) Incorporating SAT solvers into hierarchical clustering algorithms: an efficient and flexible approach. In: KDD, pp 1136-1144 [16] Girvan, M.; Newman, MEJ, Community structure in social and biological networks, Proc Natl Acad Sci, 99, 7821 (2002) · Zbl 1032.91716 [17] Gleiser, P.; Danon, L., Community structure in jazz, Adv Complex Syst, 6, 565 (2003) [18] Gregory S (2009) Finding overlapping communities using disjoint community detection algorithms. In: International workshop on complex networks, pp 47-61 [19] Guns, T.; Nijssen, S.; Raedt, LD, Itemset mining: a constraint programming perspective, Artif Intell, 175, 12-13, 1951-1983 (2011) · Zbl 1353.68233 [20] Jabbour S, Mhadhbi N, Raddaoui B, Sais L (2017) A sat-based framework for overlapping community detection in networks. In: PAKDD, pp 786-798 [21] Jabbour S, Mhadhbi N, Raddaoui B, Sais L (2018) Detecting highly overlapping community structure by model-based maximal clique expansion. In: IEEE big data, pp 1031-1036 [22] Jabbour S, Mhadhbi N, Raddaoui B, Sais L (2018) Pushing the envelope in overlapping communities detection. In: IDA, pp 151-163 [23] Jabbour S, Mhadhbi N, Raddaoui B, Sais L (2018) Triangle-driven community detection in large graphs using propositional satisfiability. In: AINA, pp 437-444 [24] Jin, D.; Yang, B.; Baquero, C.; Liu, D.; He, D.; Liu, J., A Markov random walk under constraint for discovering overlapping communities in complex networks, New J Phys, 5, P05031 (2011) [25] Kloumann IM, Kleinberg JM (2014) Community membership identification from small seed sets. In: KDD, pp 1366-1375 [26] Knuth, DE, The Stanford GraphBase: a platform for combinatorial computing (1993), New York: ACM, New York [27] Kumpula, JM; Kivela, M.; Kaski, K.; Saramaki, J., Sequential algorithm for fast clique percolation, Phys Rev E, 78, 026109 (2008) [28] Lancichinetti, A.; Fortunato, S.; Kertesz, J., Community detection algorithms: a comparative analysis, New J Phys, 11, 33015 (2009) [29] Lee DD, Seung HS (2001) Algorithms for non-negative matrix factorization. In: Leen TK, Dietterich TG, Tresp V (eds) NIPS, pp 556-562 [30] Leskovec J, Huttenlocher DP, Kleinberg JM (2010) Predicting positive and negative links in online social networks. In: WWW, pp 641-650 [31] Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. http://snap.stanford.edu/data [32] Leskovec J, Lang KJ, Mahoney MW (2010) Empirical comparison of algorithms for network community detection. In: WWW, pp 631-640 [33] Lusseau, D.; Schneider, K.; Boisseau, O.; Haase, P.; Slooten, E.; Dawson, S., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behav Ecol Sociol, 54, 4, 396-405 (2003) [34] Newman, MEJ, Finding community structure in networks using the eigenvectors of matrices, Phys Rev E, 74, 036104 (2006) [35] Newman, MEJ; Girvan, M., Finding and evaluating community structure in networks, Phys Rev E, 69, 2, 026113 (2004) [36] Padrol-Sureda A, Perarnau-Llobet G, Pfeifle J, Muntés-Mulero V (2010) Overlapping community search for social networks. In: ICDE, pp 992-995 [37] Palla, G.; Derényi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 814-818 (2005) [38] Shen, H.; Cheng, X.; Cai, K.; Hu, M., Detect overlapping and hierarchical community structure in networks, Phys A, 388, 8, 1706-1712 (2009) [39] Shi, C.; Cai, Y.; Fu, D.; Dong, Y.; Wu, B., A link clustering based overlapping community detection algorithm, Data Knowl Eng, 87, 394-404 (2013) [40] Watts, DJ; Dodds, PS; Newman, MEJ, Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 [41] Watts, DJ; Strogatz, SH, Collective dynamics of small-world networks., Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139 [42] Xie J, Szymanski BK, Liu X (2011) SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: ICDM, pp 344-349 [43] Yang J, Leskovec J (2012) Community-affiliation graph model for overlapping network community detection. In: ICDM, pp 1170-1175 [44] Yang J, Leskovec J (2013) Overlapping community detection at scale: a nonnegative matrix factorization approach. In: WSDM, pp 587-596 [45] Yang J, McAuley JJ, Leskovec J (2013) Community detection in networks with node attributes. In: ICDM, pp 1151-1156 [46] Zachary, WW, An information flow model for conflict and fission in small groups, J Anthropol Res, 33, 452-473 (1977) [47] Zhang H, King I, Lyu MR (2015) Incorporating implicit link preference into overlapping community detection. In: AAAI, pp 396-402 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.