[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

SAT-based models for overlapping community detection in networks

  • Special Issue Article
  • Published:
Computing Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Algorithm 1 can be slightly modified to deal with edge centered k-linked community detection problem.

  2. http://maxsat.ia.udl.cat/introduction/ [3].

  3. Notice that it is easy to extend our approach to other metrics as conductance, expansion, etc.

References

  1. Adamcsek B, Palla G, Farkas IJ, Derényi I, Vicsek T (2006) Cfinder: locating cliques and overlapping modules in biological networks. Bioinformatics 22(8):1021–1023

    Article  Google Scholar 

  2. Ahn YY, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466:761–764

    Article  Google Scholar 

  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 (2017) WPM3: an (in)complete algorithm for weighted partial MaxSAT. Artif Intell 250:37–57

    Article  MathSciNet  Google Scholar 

  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

  6. Dickinson B, Valyou B, Hu W (2013) A genetic algorithm for identifying overlapping communities in social networks using an optimized search space. Soc Netw 2(4):1–9

    Google Scholar 

  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 (2014) Active semi-supervised community detection based on must-link and cannot-link constraints. PLoS 9(10):1–18

    Google Scholar 

  9. Comellas F, Ozón J, Peters JG (2000) Deterministic small-world communication networks. Inf Process Lett 76(1):83–90

    Article  MathSciNet  Google Scholar 

  10. Evans TS (2010) Clique graphs and overlapping communities. J Stat Mech Theory Exp 12:P12037

    Article  Google Scholar 

  11. Farkas IJ, Abel D, Palla G, Vicsek T (2007) Weighted network modules. New J Phys 9:180

    Article  Google Scholar 

  12. Fortunato S (2010) Community detection in graphs. Phys Rep 486:75–174

    Article  MathSciNet  Google Scholar 

  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 (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99:7821

    Article  MathSciNet  Google Scholar 

  17. Gleiser P, Danon L (2003) Community structure in jazz. Adv Complex Syst 6:565

    Article  Google Scholar 

  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 (2011) Itemset mining: a constraint programming perspective. Artif Intell 175(12–13):1951–1983

    Article  MathSciNet  Google Scholar 

  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 (2011) A Markov random walk under constraint for discovering overlapping communities in complex networks. New J Phys 5:P05031

    Google Scholar 

  25. Kloumann IM, Kleinberg JM (2014) Community membership identification from small seed sets. In: KDD, pp 1366–1375

  26. Knuth DE (1993) The Stanford GraphBase: a platform for combinatorial computing. ACM, New York

    MATH  Google Scholar 

  27. Kumpula JM, Kivela M, Kaski K, Saramaki J (2008) Sequential algorithm for fast clique percolation. Phys Rev E 78:026109

    Article  Google Scholar 

  28. Lancichinetti A, Fortunato S, Kertesz J (2009) Community detection algorithms: a comparative analysis. New J Phys 11:33015

    Article  Google Scholar 

  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 (2003) The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav Ecol Sociol 54(4):396–405

    Article  Google Scholar 

  34. Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74:036104

    Article  MathSciNet  Google Scholar 

  35. Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113

    Article  Google Scholar 

  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 (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435:814–818

    Article  Google Scholar 

  38. Shen H, Cheng X, Cai K, Hu M (2009) Detect overlapping and hierarchical community structure in networks. Phys A 388(8):1706–1712

    Article  Google Scholar 

  39. Shi C, Cai Y, Fu D, Dong Y, Wu B (2013) A link clustering based overlapping community detection algorithm. Data Knowl Eng 87:394–404

    Article  Google Scholar 

  40. Watts DJ, Dodds PS, Newman MEJ (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442

    Article  Google Scholar 

  41. Watts DJ, Strogatz SH (1998) Collective dynamics of small-world networks. Nature 393(6684):440–442

    Article  Google Scholar 

  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 (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33:452–473

    Article  Google Scholar 

  47. Zhang H, King I, Lyu MR (2015) Incorporating implicit link preference into overlapping community detection. In: AAAI, pp 396–402

Download references

Author information

Authors and Affiliations

  1. CRIL CNRS, Université d’Artois, Lens, France

    Said Jabbour, Nizar Mhadhbi & Lakhdar Sais

  2. SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris, Évry, France

    Badran Raddaoui

Authors
  1. Said Jabbour
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nizar Mhadhbi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Badran Raddaoui
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lakhdar Sais
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Badran Raddaoui.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jabbour, S., Mhadhbi, N., Raddaoui, B. et al. SAT-based models for overlapping community detection in networks. Computing 102, 1275–1299 (2020). https://doi.org/10.1007/s00607-020-00803-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-020-00803-y

Keywords

Mathematics Subject Classification

Search

Navigation