Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Relabelling vertices according to the network structure by minimizing the cyclic bandwidth sum

Ronan Hamon 1 Pierre Borgnat 1 Patrick Flandrin 1 Céline Robardet 2 
2 DM2L - Data Mining and Machine Learning
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : Getting a labelling of vertices close to the structure of the graph has been proved to be of interest in many applications, e.g. to follow signals indexed by the vertices of the network. This question can be related to a graph labelling problem known as the cyclic bandwidth sum problem (CBSP). It consists of finding a labelling of the vertices of an undirected and unweighted graph with distinct integers such that the sum of (cyclic) difference of labels of adjacent vertices is minimized. In this paper, we introduce a new heuristic to follow the structure of the graph, by finding an approximate solution for the CBSP. Although theoretical results exist that give optimal value of cyclic bandwidth sum (CBS) for standard graphs, there are neither results for real-world complex networks, nor explicit methods to reach this optimal result. Furthermore, only a few methods have been proposed to approximately solve this problem. The heuristic we propose is a two-step algorithm: the first step consists of traversing the graph to find a set of paths which follow the structure of the graph, using a similarity criterion based on the Jaccard index to jump from one vertex to the next one. The second step is the merging of all obtained paths, based on a greedy approach that extends a partial solution by inserting a new path at the position that minimizes the CBS. The effectiveness of the proposed heuristic is shown through experiments on graphs whose optimal value of CBS is known, as well as on complex networks, where the consistency between labelling and topology is highlighted.
Complete list of metadata
Contributor : Pierre Borgnat Connect in order to contact the contributor
Submitted on : Tuesday, July 4, 2017 - 4:31:41 PM
Last modification on : Tuesday, June 1, 2021 - 2:08:09 PM



Ronan Hamon, Pierre Borgnat, Patrick Flandrin, Céline Robardet. Relabelling vertices according to the network structure by minimizing the cyclic bandwidth sum. Journal of Complex Networks, Oxford University Press, 2016, 4 (4), pp. 534-560. ⟨10.1093/comnet/cnw006⟩. ⟨ensl-01556074⟩



Record views