Title | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/AINA.2018.00072 | 2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA) |
Keywords | Field | DocType |
Social Networks,Community Detection,Propositional Satisfiability | Cohesion (chemistry),Data structure,Graph,Community structure,Computer science,Satisfiability,Theoretical computer science,Complex network,Cluster analysis,Optimization problem,Distributed computing | Conference |
ISSN | ISBN | Citations |
1550-445X | 978-1-5386-2196-7 | 0 |
PageRank | References | Authors |
0.34 | 21 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Saïd Jabbour | 1 | 35 | 5.00 |
Nizar Mhadhbi | 2 | 0 | 2.70 |
Badran Raddaoui | 3 | 93 | 15.31 |
Lakhdar Sais | 4 | 859 | 65.57 |