Discovering the structure of complex networks: Implementation and Complexity of the heuristic MACH

Abstract : Getting a labeling of vertices close to the structure of the graph has been proven 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 labeling problem known as the cyclic bandwidth sum problem. It consists in finding a labeling 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. Although theoretical results exist that give optimal value of cyclic bandwidth sum for standard graphs, there are neither results in the general case, nor explicit methods to reach this optimal result. In addition to this lack of theoretical knowledge, only a few methods have been proposed to approximately solve this problem. This report describes the implementation and the complexity of the heuristic MACH, developed to find an approximate solution for the cyclic bandwidth sum problem, by following the structure of the graph. The heuristic 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 cyclic bandwidth sum. 1 Description of the heuristic MACH The aim of the heuristic, introduced in [1], is to build a labeling by traversing the graph to discover its structure. The heuristic we propose consists of a two-step algorithm. The first step performs local searches in order to find a collection of independent paths with respect to the local structure of the graph, while the second step determines the best way to arrange the paths such that the objective function of the Cyclic Bandwidth Sum is minimized.
Type de document :
Rapport
[Technical Report] Laboratoire de Physique, CNRS 5672; LIRIS UMR CNRS 5205. 2015
Liste complète des métadonnées


https://hal-ens-lyon.archives-ouvertes.fr/ensl-01160737
Contributeur : Ronan Hamon <>
Soumis le : dimanche 7 juin 2015 - 00:08:12
Dernière modification le : vendredi 16 septembre 2016 - 15:17:26
Document(s) archivé(s) le : mardi 25 avril 2017 - 04:11:34

Fichier

report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-01160737, version 1

Collections

Citation

Ronan Hamon, Pierre Borgnat, Patrick Flandrin, Céline Robardet. Discovering the structure of complex networks: Implementation and Complexity of the heuristic MACH. [Technical Report] Laboratoire de Physique, CNRS 5672; LIRIS UMR CNRS 5205. 2015. <ensl-01160737>

Partager

Métriques

Consultations de
la notice

104

Téléchargements du document

55