nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

A SAT-Based Framework for Overlapping Community Detection in Networks

verfasst von : Said Jabbour, Nizar Mhadhbi, Badran Raddaoui, Lakhdar Sais

Erschienen in: Advances in Knowledge Discovery and Data Mining

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we propose a new approach to detect overlapping communities in large complex networks. We first introduce a parametrized notion of a community, called k -linked community, allowing us to characterize node/edge centered k-linked community with bounded diameter. Such community admits a node or an edge with a distance at most \(\frac{k}{2}\) from any other node of that community. Next, we show how the problem of detecting node/edge centered k-linked overlapping communities can be expressed as a Partial Max-SAT optimization problem. Then, we propose a post-processing strategy to limit the overlaps between communities. An extensive experimental evaluation on real-world networks shows that our approach outperforms several popular algorithms in detecting relevant communities.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Mining Cohesive Clusters with Interpretations in Labeled Graphs

Nächstes Kapitel Denoising Autoencoder as an Effective Dimensionality Reduction and Clustering of Text Data

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

http://maxsat.ia.udl.cat/introduction/.

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

Ansótegui, C., Didier, F., Gabàs, J.: Exploiting the structure of unsatisfiable cores in MaxSAT. In: IJCAI, pp. 283–289 (2015)

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

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)

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

Fortunato, S.: Community detection in graphs. CoRR, abs/0906.0612 (2009)

Gilpin, S., Davidson, I.N.: Incorporating SAT solvers into hierarchical clustering algorithms: an efficient and flexible approach. In: KDD, pp. 1136–1144 (2011)

Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99, 7821 (2002)MathSciNetCrossRefMATH

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

10.

Guns, T., Nijssen, S., Raedt, L.D.: Itemset mining: a constraint programming perspective. Artif. Intell. 175(12–13), 1951–1983 (2011)MathSciNetCrossRefMATH

11.

Knuth, D.E.: The Stanford GraphBase - A Platform for Combinatorial Computing. ACM, New York (1993)MATH

12.

Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: Advances in Neural Information Processing Systems, vol. 13, pp. 556–562 (2001)

13.

Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Predicting positive and negative links in online social networks. In: WWW, pp. 641–650 (2010)

14.

Leskovec, J., Krevl, A., Datasets, S.: Stanford large network dataset collection, June 2014. http://snap.stanford.edu/data

15.

Leskovec, J., Lang, K.J., Mahoney, M.W.: Empirical comparison of algorithms for network community detection. In: WWW, pp. 631–640 (2010)

16.

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. Sociobiol. 54(4), 396–405 (2003)CrossRef

17.

Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104 (2006)MathSciNetCrossRef

18.

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

19.

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

20.

Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(6684), 440–442 (1998)CrossRef

21.

Whang, J.J., Gleich, D.F., Dhillon, I.S.: Overlapping community detection using neighborhood-inflated seed expansion. TKDE 28(5), 1272–1284 (2016)

22.

Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 452–473 (1977)CrossRef

23.

Yang, J., Leskovec, J.: Community-affiliation graph model for overlapping network community detection. In: ICDM, pp. 1170–1175 (2012)

24.

Yang, J., Leskovec, J.: Overlapping community detection at scale: a nonnegative matrix factorization approach. In: WSDM, pp. 587–596 (2013)

25.

Yang, J., McAuley, J.J., Leskovec, J.: Community detection in networks with node attributes. In: ICDM, pp. 1151–1156 (2013)

Titel: A SAT-Based Framework for Overlapping Community Detection in Networks
verfasst von: Said Jabbour
Nizar Mhadhbi
Badran Raddaoui
Lakhdar Sais
Verlag: Springer International Publishing
Buch: Advances in Knowledge Discovery and Data Mining
Print ISBN: 978-3-319-57528-5

Electronic ISBN: 978-3-319-57529-2

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-57529-2_61

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"