Triangle-Driven Community Detection in Large Graphs Using Propositional Satisfiability

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 net...

Full description

Saved in:
Bibliographic Details
Main Authors: Jabbour, Said, Mhadbhi, Nizar, Raddaoui, Badran, Sais, Lakhdar
Format: Conference Proceeding
Language:English
Subjects:
Clustering algorithms
Community Detection
Data mining
Image edge detection
Lenses
Measurement
Optimization
Partitioning algorithms
Propositional Satisfiability
Social Networks
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2332-5658
DOI:10.1109/AINA.2018.00072