University of Hull CSI

Technical Report CSI-0055

Computational Methods for Finding Long Cycles in Complex Networks

D. Chalupa and P. Balaghan and K. A. Hawick and N. A. Gordon

Archived: 2016

Abstract

Detection of long 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 an 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. 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.

Keywords: long cycles, complex networks, integer linear programming, graph algorithms, local search, Hamiltonian cycles.

Full Document Text: Not yet available.

Citation Information: BiBTeX database for CSI Notes.

BiBTeX reference:

@TechReport{CSI-0055,
        Title = {Computational Methods for Finding Long Cycles in Complex Networks},
        Author = {D. Chalupa and P. Balaghan and K. A. Hawick and N. A. Gordon},
        Institution = {Computer Science, University of Hull},
        Year = {2016},
        Address = {Cottingham Road, HU6 7RX, Hull, UK},
        Month = {August},
        Number = {CSI-0055},
        Type = {CSI},
        Keywords = {long cycles, complex networks, integer linear programming, graph algorithms, local search, Hamiltonian cycles.},
        Owner = {kahawick},
        Timestamp = {2016.10.29}
}


[ CSI Index | CSI BiBTeX ]