Skip to Main content Skip to Navigation
New interface
Conference papers

Triangle-Driven Community Detection in Large Graphs Using Propositional Satisfiability

Abstract : Discovering the latent community structure is crucial to understanding the features of networks. Several approaches have been proposed to solve this challenging problem using different measures or data structures. Among them, detecting overlapping communities in a network is an usual way towards network structure discovery. It presents nice algorithmic issues, and plays an important role in complex network analysis. In this paper, we propose a new approach to detect overlapping communities in large complex networks. First, we introduce a novel subgraph concept based on triangles to capture the cohesion in social interactions, and propose an efficient approach to discover clusters in networks. Next, we show how the problem of detecting overlapping communities can be expressed as a Partial Max-SAT optimization problem. Our comprehensive experimental evaluation on publicly available real-life networks with ground-truth communities demonstrates the effectiveness and efficiency of our proposed method.
Document type :
Conference papers
Complete list of metadata
Contributor : Said Jabbour Connect in order to contact the contributor
Submitted on : Monday, June 20, 2022 - 7:11:03 PM
Last modification on : Friday, June 24, 2022 - 4:04:14 AM
Long-term archiving on: : Thursday, September 22, 2022 - 10:44:53 AM


Files produced by the author(s)




Said Jabbour, Nizar Mhadhbi, Badran Radaoui, Lakhdar Sais. Triangle-Driven Community Detection in Large Graphs Using Propositional Satisfiability. 2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA), May 2018, Krakow, France. pp.437-444, ⟨10.1109/AINA.2018.00072⟩. ⟨hal-03700076⟩



Record views


Files downloads