Dégénérescence (théorie des graphes)
En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k. La dégénérescence d'un graphe est le plus petit k tel qu'il soit k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage.
Il est possible de calculer l'ordre de dégénérescence en temps linéaire[1]. L'algorithme consiste à retirer itérativement les nœuds de plus faible degré, en maintenant à jour une file de paquets indexés par leur degré courant. Les composantes connexes obtenues lorsque tous les sommets de degré inférieur à k ont été retirés sont appelés k-cœur du graphe, et la dégénérescence k est alors donnée par la plus grande valeur k associée à un k-cœur non-vide.
La dégénérescence est une mesure de la non-densité du graphe (c'est-à-dire d'à quel point le graphe est creux). On l'utilise notamment dans les problèmes de coloration de graphes[2].
Deux définitions historiques équivalentes
modifier![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/08/2-degenerate_graph_2-core.svg/400px-2-degenerate_graph_2-core.svg.png)
Historiquement, la première définition proposée (sous le nom de coloring number) est due à Paul Erdős et András Hajnal en 1966[3]. Elle dit qu'un graphe a un coloring number de k s'il existe un ordre[pas clair] sur les sommets tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k.
Don Lick et Arthur White proposent une définition équivalente (en employant le terme de k-degenerate graph) en 1970[4]: un graphe est dit k-dégénéré si tout sous-graphe induit contient un nœud de degré inférieur ou égal à k. On appelle dégénérescence d'un graphe le plus petit entier k tel que le graphe est k-dégénéré.
En français, on emploie également le terme nombre de marquage[2]. En anglais, les termes degeneracy et coloring number sont tous deux employés. Il ne faut pas confondre le coloring number avec le chromatic number (ou nombre chromatique).
Notion de k-cœur d'un graphe
modifierLe k-cœur (k-core en anglais) d'un graphe G est le sous-graphe induit maximum de G dont tous les nœuds sont de degré au moins égal k. De manière équivalente, c'est le sous-graphe induit de G obtenu lorsque l'on supprime de manière répétée tous les sommets de degré plus petit que k. La dégénérescence de G sera la plus grande valeur de k pour laquelle G admet un k-cœur non-vide.
Le concept de k-cœur a été introduit pour étudier la structure des réseaux sociaux[5],[6] et pour décrire l'évolution de graphes aléatoires[7],[8],[9]. On l'a aussi utilisé dans différents domaines de la science des réseaux, par exemple en bio-informatique[10],[11],[12], en visualisation de graphes[13],[14], ou encore en écologie pour étudier la robustesse des réseaux[15].
Aspects algorithmiques
modifierL'algorithme de Matula et Beck calcule l'ordre de dégénérescence en temps linéaire[1]. Le principe de l'algorithme est de retirer itérativement les nœuds de plus faible degré, en maintenant à jour une file de paquets indexés par leur degré courant. Pour un graphe dont l'ensemble des sommets est V et l'ensemble des liens E, la procédure de Matula et Beck a une complexité temporelle en et spatiale en .
On peut le décrire de la manière suivante :
- Initialiser la liste de sortie L à la liste vide.
- Calculer une valeur dv pour chaque sommet v de G, qui est le nombre de voisins de v qui n'est pas déjà dans L (initialement, il s'agit donc du degré des sommets dans G).
- Initialiser un tableau D tel que D[i] contienne la liste des sommets v qui ne sont pas déjà dans L pour lesquels dv = i.
- Initialiser la valeur k à 0.
- Répéter n fois:
- Parcourir les cellules du tableau D[0], D[1], ... jusqu'à trouver un i pour lequel D[i] est non-vide.
- Mettre k à max(k,i).
- Sélectionner un sommet v de D[i], ajouter v en tête de L et le retirer de D[i].
- Pour chaque voisin w de v qui n'est pas déjà dans L, retirer une unité de dw et déplacer w de la cellule de D correspondant à la nouvelle valeur de dw.
À la fin de l'algorithme, tout sommet aura au plus k liens vers les sommets de . Les l-cœurs de G sont les , sous-graphes induits par les sommets , où i est le premier sommet de degré au moment où il est ajouté à L.
Propriétés
modifierUn graphe k-dégénéré a un nombre chromatique d'au plus k+1. On peut le prouver par une récurrence simple sur le nombre de sommets du graphe. Un algorithme de coloriage glouton sur un graphe qui parcourt les nœuds dans un ordre de dégénérescence permet de colorier les sommets avec au plus k+1 couleurs[16]. Par ailleurs, comme le nombre chromatique est une borne supérieure à la taille de la clique maximum du graphe, celle-ci est au plus la dégénérescence du graphe +1.
La dégénérescence k d'un graphe est liée à son arboricité a par l'encadrement suivant: a ≤ k < 2a. En effet, si on oriente les arêtes du graphe selon l'ordre de dégénérescence de manière que l'orientation aille des sommets d'indice les plus élevés vers ceux d'indices plus petits, on obtient un graphe orienté acyclique de degré sortant maximum k; les arêtes peuvent alors être partitionnées en k forêts en choisissant pour chaque lien sortant de chaque sommet de l'affecter à une des forêts; par définition de l'arborescence, on a alors a ≤ k.
La dégénérescence peut aussi être liée à d'autres caractéristiques du graphe telle que la largeur arborescente.
On dit qu'un graphe est k-sommet-connexe s'il ne peut être partitionné par la suppression de moins de k sommets, ou, de manière équivalente, si toute paire de sommets est connectée par k il existe est k chaînes indépendantes reliant ces sommets. Comme ces chaînes doivent relier les deux sommets de la paire par des liens distincts, un graphe k-sommet connexe doit être au moins k-dégénéré. Des concepts basés sur la sommet-connexité ont été étudié dans le domaine de l'analyse de réseaux sociaux sous le nom de cohésion structurelle[17].
La conjecture d'Erdős-Burr dit que pour tout entier k, il existe une constante c telle que tout graphe k-dégénéré à n sommets ait son nombre de Ramsey majoré par c.n, autrement dit, le nombre de Ramsey croît linéairement avec le nombre de sommets du graphe. Cette conjecture a été démontrée par Choongbum Lee en 2017[18].
Voir également
modifierNotes et références
modifier- (en) D.W. Matula et L.L. Beck, « Smallest-last ordering and clustering and graph coloring algorithms », Journal of the ACM, vol. 30, no 3, , p. 417-427 (DOI 10.1145/2402.322385, MR 0709826).
- C. Charpentier, « Colorations de graphes : Marquage et dégénérescence », dans Jeux de coloration de graphes et problèmes de coloration (Thèse de doctorat), Université de Bordeaux (lire en ligne), p. 17.
- (en) P. Erdős et A. Hajnal, « On chromatic number of graphs and set-systems », Acta Math. Acad. Sci. Hungar., vol. 17, , p. 61-99 (lire en ligne).
- (en) D.R. Lick et A.T. White, « k-degenerate graphs », Canadian Journal of Mathematics, vol. 22, no 5, , p. 1082–1096 (DOI 10.4153/CJM-1970-125-1) .
- (en) C. Giatsidis, Graph Mining and Community evaluation with degeneracy (thèse de doctorat), École polytechnique, Palaiseau, (lire en ligne).
- (en) S.B. Seidman, « Network structure and minimum degree », Social Networks, vol. 5, no 3, , p. 269–287 (DOI 10.1016/0378-8733(83)90028-X)
- (en) B. Bollobás, « The evolution of sparse graphs », dans Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdős, Academic Press, , p. 35–57.
- (en) T. Łuczak, « Size and connectivity of the k-core of a random graph », Discrete Mathematics, vol. 91, no 1, , p. 61–68 (DOI 10.1016/0012-365X(91)90162-U, lire en ligne).
- (en) S.N. Dorogovtsev, A.V. Goltsev et J.F.F. Mendes, « k-core organization of complex networks », Physical Review Letters, vol. 96, no 4, , p. 040601 (PMID 16486798, DOI 10.1103/PhysRevLett.96.040601, Bibcode 2006PhRvL..96d0601D, arXiv cond-mat/0509102, S2CID 2035).
- (en) G.D. Bader et C.W.V. Hogue, « An automated method for finding molecular complexes in large protein interaction networks », BMC Bioinformatics, vol. 4, no 1, , p. 2 (PMID 12525261, PMCID 149346, DOI 10.1186/1471-2105-4-2).
- (en) M. Altaf-Ul-Amin, K. Nishikata, T. Koma, T. Miyasato, Y. Shinbo, M. Arifuzzaman, C. Wada, M. Maeda et T. Oshima, « Prediction of protein functions based on k-cores of protein-protein interaction networks and amino acid sequences », Genome Informatics, vol. 14, , p. 498–499 (lire en ligne [archive du ]).
- (en) S. Wuchty et E. Almaas, « Peeling the yeast protein network », Proteomics, vol. 5, , p. 444–449 (PMID 15627958, DOI 10.1002/pmic.200400962, S2CID 17659720)
- (en) M. Gaertler et M. Patrignani, « Dynamic analysis of the autonomous system graph », dans Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004), (CiteSeerx 10.1.1.81.6841), p. 13–24
- (en) J.I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat et A. Vespignani, « k-core decomposition: a tool for the visualization of large scale networks », dans Advances in Neural Information Processing Systems 18: Proceedings of the 2005 Conference, vol. 18, The MIT Press, (ISBN 0262232537, arXiv cs/0504107), p. 41
- (en) J. Garcia-Algarra, J.M. Pastor, J.M. Iriondo et J. Galeano, « Ranking of critical species to preserve the functionality of mutualistic networks using the k-core decomposition », PeerJ, vol. 5, , e3321 (PMID 28533969, PMCID 5438587, DOI 10.7717/peerj.3321)
- (en) G.K. Szekeres et H. Wilf , « An inequality for the chromatic number of a graph », Journal of Combinatorial Theory, vol. 4, , p. 1–3 (DOI 10.1016/S0021-9800(68)80081-X).
- (en) J. Moody et D.R. White, « Structural cohesion and embeddedness: a hierarchical conception of social groups », American Sociological Review, vol. 68, no 1, , p. 1–25 (DOI 10.2307/3088904, JSTOR 3088904, lire en ligne).
- (en) C. Lee, « Ramsey numbers of degenerate graphs », Annals of Mathematics, vol. 185, no 3, , p. 791–829 (DOI 10.4007/annals.2017.185.3.2, arXiv 1505.04773, S2CID 7974973).