David Chalupa
Computational methods for finding long simple cycles in complex networks
Chalupa, David; Balaghan, Phininder; Hawick, Ken A.; Gordon, Neil A.
Abstract
© 2017 Elsevier B.V. Detection of long simple cycles in real-world complex networks finds many applications in layout algorithms, information flow modelling, as well as in bioinformatics. In this paper, we propose two computational methods for finding long cycles in real-world networks. The first method is an exact approach based on our own integer linear programming formulation of the problem and a data mining pipeline. This pipeline ensures that the problem is solved as a sequence of integer linear programs. The second method is a multi-start local search heuristic, which combines an initial construction of a long cycle using depth-first search with four different perturbation operators. Our experimental results are presented for social network samples, graphs studied in the network science field, graphs from DIMACS series, and protein-protein interaction networks. These results show that our formulation leads to a significantly more efficient exact approach to solve the problem than a previous formulation. For 14 out of 22 networks, we have found the optimal solutions. The potential of heuristics in this problem is also demonstrated, especially in the context of large-scale problem instances.
Citation
Chalupa, D., Balaghan, P., Hawick, K. A., & Gordon, N. A. (2017). Computational methods for finding long simple cycles in complex networks. Knowledge-Based Systems, 125, 96-107. https://doi.org/10.1016/j.knosys.2017.03.022
Acceptance Date | Mar 29, 2017 |
---|---|
Online Publication Date | Mar 30, 2017 |
Publication Date | 2017-06 |
Deposit Date | May 30, 2017 |
Publicly Available Date | Apr 3, 2018 |
Journal | Knowledge-based systems |
Print ISSN | 0950-7051 |
Electronic ISSN | 1872-7409 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 125 |
Pages | 96-107 |
DOI | https://doi.org/10.1016/j.knosys.2017.03.022 |
Keywords | Long simple cycles; Long cycles; Complex networks; Integer linear programming; Graph algorithms; Local search; Hamiltonian cycles |
Public URL | https://hull-repository.worktribe.com/output/451741 |
Publisher URL | http://www.sciencedirect.com/science/article/pii/S0950705117301491 |
Additional Information | This is the accepted manuscript of an article published in Knowledge-based systems, 2017. The version of record is available at the DOI link in this record |
Files
Article
(2.1 Mb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
©2018, Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Analysis of an iterated greedy heuristic for vertex clique covering
(2018)
Journal Article
Construction of near-optimal vertex clique covering for real-world networks
(2015)
Journal Article
Partitioning networks into cliques: a randomized heuristic approach
(2014)
Journal Article
Downloadable Citations
About Repository@Hull
Administrator e-mail: repository@hull.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search