Back to Search
Start Over
Vertex Selection Heuristics in Branch-and-Bound Algorithms for the Maximum k-Plex Problem.
- Source :
- International Journal on Artificial Intelligence Tools; Aug2019, Vol. 28 Issue 5, pN.PAG-N.PAG, 16p
- Publication Year :
- 2019
-
Abstract
- As a relaxation of clique in graph theory, k-plex is a powerful tool for analyzing social networks and identifying cohesive structures in graphs. Recently, more and more researchers have concentrated on the algorithms for the maximum k-plex problem. Among those algorithms, a branch-and-bound algorithm proposed very recently shows a good performance on solving large sparse graphs, but does not work well on social networks. In this paper, we propose two novel vertex selection heuristic strategies for branching. The first one employs historical information of vertex reduction, and the second one is a combination of the first heuristic and the degree-based approach. Intensive experiments on Facebook benchmark show that the algorithm combining our heuristics outperforms the state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPH theory
ALGORITHMS
HEURISTIC
SOCIAL networks
SPARSE graphs
SOCIAL services
Subjects
Details
- Language :
- English
- ISSN :
- 02182130
- Volume :
- 28
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- International Journal on Artificial Intelligence Tools
- Publication Type :
- Academic Journal
- Accession number :
- 138338795
- Full Text :
- https://doi.org/10.1142/S0218213019500155