Degré d'un sommet et lemme des poignées de main

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Le degré d'un sommet

Le degré d'un sommet est le nombre d'arêtes qui le touchent. Dans un graphe simple, c'est aussi le nombre de ses voisins. C'est le nombre le plus local d'un graphe : vous pouvez le lire sur un seul sommet sans regarder quoi que ce soit d'autre. Pourtant, une part surprenante de la structure globale est décidée par les seuls degrés, et c'est le sujet de cet article.

La notation est brève. deg(v) désigne le degré de v, δ(G) est le degré minimum sur l'ensemble des sommets et Δ(G) le degré maximum. Un sommet de degré 0 est isolé, un sommet de degré 1 est une feuille ou sommet pendant, et un graphe dont tous les sommets ont le même degré r est r-régulier. Le vocabulaire de base, y compris la raison pour laquelle une boucle ajoute 2 au degré, est présenté dans le guide sur les sommets et les arêtes ; cet article en fait son point de départ et se demande ce que les degrés peuvent vous apprendre.

Un petit réseau d'amitiés porte tout l'article. Huit personnes, de A à H, et douze amitiés :

E = {AB, AC, AD, BC, BD, CD, AE, DE, AF, EF, FG, AH}       12 arêtes

deg:   A 6   B 3   C 3   D 4   E 3   F 3   G 1   H 1
δ = 1 (G et H)       Δ = 6 (A)      degré moyen = 24 / 8 = 3

2. Le lemme des poignées de main

Additionnez les degrés de l'exemple et vous obtenez 24, exactement le double de ses 12 arêtes. Ce n'est pas une coïncidence propre à ce graphe.

Lemme des poignées de main. Dans tout graphe, la somme des degrés de tous les sommets est égale au double du nombre d'arêtes : ∑ deg(v) = 2m.

La preuve est un double comptage. Comptez les paires (sommet, extrémité d'arête en ce sommet). Compter par sommets donne la somme des degrés. Compter par arêtes donne 2 pour chaque arête, car toute arête a exactement deux extrémités, y compris une boucle, dont les deux extrémités sont sur le même sommet. Les deux comptages décrivent le même ensemble de paires, ils sont donc égaux. L'observation remonte au mémoire d'Euler de 1736 sur les ponts de Königsberg, où elle apparaît dans le langage des ponts et des régions de terre ; le nom « lemme des poignées de main » est moderne et vient de l'image d'une soirée où chaque poignée de main fait intervenir deux mains.

La conséquence la plus utile du lemme est immédiate. La somme de tous les degrés est paire, donc les degrés impairs vont forcément par paires :

Tout graphe a un nombre pair de sommets de degré impair.

Dans l'exemple, les sommets de degré impair sont B, C, E, F, G et H : six au total, un nombre pair, comme promis.

3. Calculer les degrés d'un graphe stocké

Le coût de lecture d'un degré dépend de la façon dont le graphe est stocké, le compromis expliqué dans le guide sur la représentation des graphes. Avec une liste d'adjacence, le degré de v est la longueur de sa liste, disponible en O(1) si la longueur est mémorisée. Avec une matrice d'adjacence, c'est la somme de la ligne v, ce qui coûte O(n). Avec une simple liste d'arêtes, il faut parcourir toutes les m arêtes ; l'habitude est donc de calculer tous les degrés en une seule passe et de garder le résultat. Le programme ci-dessous fait exactement cela, vérifie le lemme des poignées de main et calcule aussi les deux moyennes sur lesquelles repose la section 9.

from collections import Counter

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

deg = {v: len(adj[v]) for v in adj}
print(deg)
# {'A': 6, 'B': 3, 'C': 3, 'D': 4, 'E': 3, 'F': 3, 'G': 1, 'H': 1}

print(sum(deg.values()), 2 * len(edges))     # le lemme des poignées de main
# 24 24
print(sorted(v for v in deg if deg[v] % 2))   # toujours en nombre pair
# ['B', 'C', 'E', 'F', 'G', 'H']

# Le paradoxe de l'amitié : degré moyen contre degré moyen d'un ami.
mean_degree = sum(deg.values()) / len(deg)
mean_friend = sum(deg[v] ** 2 for v in deg) / sum(deg.values())
print(mean_degree, mean_friend)
# 3.0 3.75

# Combien de personnes ont moins d'amis que leurs amis n'en ont, en moyenne ?
fewer = [v for v in adj if deg[v] < sum(deg[w] for w in adj[v]) / deg[v]]
print(sorted(fewer))
# ['B', 'C', 'E', 'F', 'G', 'H']
print(Counter(deg.values()).most_common(1))  # un degré se répète toujours
# [(3, 4)]

Deux lignes de la sortie méritent déjà votre attention. La vérification des poignées de main affiche 24 24. Et la dernière ligne indique que le degré 3 apparaît quatre fois. Un degré se répète toujours, pour une raison qu'explique la section 4.

4. Les énigmes que le lemme résout d'emblée

Le lemme des poignées de main transforme plusieurs questions qui semblent demander une recherche en une seule ligne d'arithmétique.

• Sept personnes peuvent-elles serrer chacune la main d'exactement trois autres ? Non. Il faudrait une somme des degrés égale à 7 × 3 = 21, qui est impaire, alors que toute somme des degrés vaut le double d'un nombre entier de poignées de main.
• Existe-t-il un graphe 3-régulier à 9 sommets ? Non, pour la même raison. Un graphe r-régulier à n sommets possède nr / 2 arêtes, donc lorsque r est impair, n doit être pair.
• Combien d'arêtes possède un graphe à 10 sommets de degré moyen 3 ? Exactement 15, car le degré moyen vaut 2m / n.
• Une marche peut-elle emprunter chaque arête exactement une fois, en partant et en arrivant à des endroits différents, avec un seul sommet de degré impair ? La question ne se pose même pas : un graphe ne peut pas avoir exactement un sommet impair. Le critère d'Euler en demande zéro ou deux, ce qu'explique le guide sur les chemins eulériens en détail, et le lemme exclut tout nombre impair.

Un deuxième classique repose plutôt sur le principe des tiroirs :

Dans tout graphe simple ayant au moins deux sommets, deux sommets ont le même degré.

Avec n sommets, les degrés possibles sont 0, 1, …, n − 1, soit n valeurs pour n sommets ; des degrés tous différents signifieraient donc que chaque valeur sert exactement une fois. Mais 0 et n − 1 ne peuvent pas apparaître tous les deux : un sommet de degré n − 1 est adjacent à tous les autres, donc personne n'a le degré 0. Il reste donc au plus n − 1 valeurs utilisables pour n sommets, et deux d'entre eux doivent en partager une. En termes de tous les jours : dans n'importe quelle soirée, deux personnes ont le même nombre d'amis présents. L'énoncé exige que le graphe soit simple ; avec des arêtes parallèles, il est faux. Il a été vérifié par force brute sur tous les graphes simples d'au plus sept sommets.

5. Suites de degrés : quelles listes peuvent être des graphes ?

Rangez les degrés du plus grand au plus petit et vous obtenez la suite des degrés, (6, 4, 3, 3, 3, 3, 1, 1) de l'exemple. Une suite effectivement réalisée par un graphe simple est dite graphique. Une somme paire est nécessaire, d'après le lemme des poignées de main, mais loin d'être suffisante : (4, 4, 4, 1, 1) a une somme paire mais aucun graphe. Trois sommets de degré 4 parmi cinq seraient chacun adjacents à tous les autres, ce qui donnerait aux deux derniers sommets un degré d'au moins 3.

Deux tests classiques tranchent exactement la question. Le guide sur les sommets et les arêtes les déroule tous deux à la main ; les voici sous forme de code. La méthode de Havel–Hakimi (Havel 1955, Hakimi 1962) relie à plusieurs reprises le sommet de plus grand degré restant aux suivants dans l'ordre, et soit construit un graphe, soit se bloque. Le théorème d'Erdős–Gallai de 1960 est un test explicite : une suite décroissante de somme paire est graphique exactement lorsque, pour tout k, les k plus grands degrés ont une somme d'au plus k(k − 1) plus la somme des min(di, k) sur les autres.

import heapq

def havel_hakimi(seq):
    """Renvoie les arêtes d'un graphe simple ayant ces degrés, ou None s'il n'en existe pas."""
    if sum(seq) % 2:
        return None                           # un total impair viole le lemme des poignées de main
    heap = [(-d, i) for i, d in enumerate(seq) if d > 0]
    heapq.heapify(heap)
    edges = []
    while heap:
        d, v = heapq.heappop(heap)
        d = -d
        if d > len(heap):
            return None                       # il ne reste pas assez d'autres sommets à relier
        taken = [heapq.heappop(heap) for _ in range(d)]
        for dw, w in taken:                   # relier v aux d sommets de plus grand degré
            edges.append((v, w))
            if dw + 1 < 0:
                heapq.heappush(heap, (dw + 1, w))
    return edges

def erdos_gallai(seq):
    """Vrai exactement lorsque la suite est graphique (Erdős et Gallai, 1960)."""
    d = sorted(seq, reverse=True)
    if sum(d) % 2:
        return False
    for k in range(1, len(d) + 1):
        if sum(d[:k]) > k * (k - 1) + sum(min(x, k) for x in d[k:]):
            return False
    return True

print(len(havel_hakimi([6, 4, 3, 3, 3, 3, 1, 1])))
# 12
print(havel_hakimi([4, 4, 4, 1, 1]), erdos_gallai([4, 4, 4, 1, 1]))
# None False
print(havel_hakimi([3, 3, 3, 3, 3]), erdos_gallai([3, 3, 3, 3, 3]))
# None False

Pour (4, 4, 4, 1, 1) l'inégalité d'Erdős–Gallai est violée en k = 3 : les trois plus grands degrés ont pour somme 12, mais la borne vaut 3 × 2 + 1 + 1 = 8. Les deux fonctions ont été vérifiées par force brute sur chacune des 2 353 suites décroissantes de longueur n ≤ 7 dont les termes valent au plus n − 1, et la fonction de Havel–Hakimi a aussi été vérifiée : elle renvoie un véritable graphe simple ayant exactement les degrés demandés. Une suite graphique a en général de nombreuses réalisations différentes ; une suite des degrés décrit donc une famille de graphes, pas un seul graphe.

6. Ce que garantit un grand degré minimum

Imposer à chaque sommet de nombreux voisins impose de la structure. Les arguments derrière les trois premiers faits sont tous des variations sur une même idée : avancer aussi loin que possible et regarder où se trouvent les voisins du dernier sommet.

• δ ≥ 2 impose un cycle. Prenez un plus long chemin. Son dernier sommet a au moins deux voisins, et tous se trouvent sur le chemin, sinon on pourrait prolonger celui-ci. L'un d'eux n'est pas son prédécesseur, et cette arête ferme un cycle.
• δ ≥ k impose un chemin ayant au moins k arêtes. Ce même plus long chemin doit contenir les δ voisins de son dernier sommet ; il a donc au moins δ + 1 sommets.
• δ ≥ (n − 1) / 2 impose que le graphe soit connexe. Deux sommets situés dans des composantes différentes auraient chacun besoin d'au moins (n − 1) / 2 voisins dans leur propre composante, et ces deux composantes contiendraient ensemble plus de n sommets.

Le résultat le plus célèbre de ce type concerne les cycles hamiltoniens, les cycles qui passent une fois par chaque sommet. Décider s'il en existe un est NP-complet en général, mais un grand degré minimum tranche la question.

Théorème de Dirac (1952). Tout graphe simple à n ≥ 3 sommets et de degré minimum au moins n / 2 possède un cycle hamiltonien.

Ore l'a renforcé en 1960 : il suffit que deux sommets non adjacents quelconques aient des degrés dont la somme vaut au moins n. Le seuil n / 2 ne peut pas être abaissé. Le graphe biparti complet K2,3 a cinq sommets et un degré minimum de 2, juste en dessous de 5 / 2, et n'a pas de cycle hamiltonien, car un cycle passant par les cinq sommets devrait alterner entre les deux côtés, qui n'ont pas la même taille.

Le réseau de l'exemple a δ = 1, bien en dessous de 8 / 2, et il n'a pas de cycle hamiltonien : un cycle ne peut jamais passer par une feuille comme G, qui n'a qu'une seule arête. La condition de Dirac est suffisante, pas nécessaire, donc ne pas la remplir ne prouve rien en soi ; ici, ce sont les feuilles qui sont la vraie raison.

7. Ce que borne le degré maximum

Le degré maximum contrôle la coloration. Coloriez les sommets un par un dans n'importe quel ordre, en donnant à chacun la plus petite couleur qu'aucun de ses voisins déjà coloriés n'utilise. Un sommet a au plus Δ voisins, donc au plus Δ couleurs sont bloquées et l'une des Δ + 1 premières est toujours libre.

Tout graphe peut être proprement colorié avec au plus Δ + 1 couleurs, et l'algorithme glouton y parvient quel que soit l'ordre des sommets.

Brooks a prouvé en 1941 qu'une couleur de moins suffit, avec exactement deux types d'exception : un graphe connexe n'a besoin de Δ + 1 couleurs que s'il est un graphe complet ou un cycle impair. Un cycle impair a Δ = 2 et nécessite 3 couleurs, et Kn a Δ = n − 1 et en nécessite n. Pour la coloration des arêtes, la réponse est encore plus serrée : Vizing a montré en 1964 que les arêtes de tout graphe simple peuvent être coloriées avec Δ ou Δ + 1 couleurs.

Dans l'exemple, Δ = 6, donc la coloration gloutonne est assurée d'utiliser au plus 7 couleurs et le théorème de Brooks abaisse la borne à 6. La vraie valeur est 4, car l'exemple contient le graphe complet sur A, B, C et D, qui en exige 4, et 4 suffisent. Le degré maximum est une borne grossière lorsqu'un sommet est bien plus sollicité que les autres. L'heuristique de Welsh et Powell de 1967, qui colorie les sommets par degré décroissant, est une réponse ; la section suivante en donne une plus fine.

8. Dégénérescence et k-cœurs

Le hub A gonfle Δ sans rendre le graphe difficile à colorier. Une meilleure mesure examine à quel point le graphe est creux partout, et non son seul sommet le plus chargé. Supprimez à répétition un sommet de plus petit degré restant. Le plus grand degré auquel vous avez dû supprimer un sommet est la dégénérescence du graphe. De manière équivalente, le k-cœur est le plus grand sous-graphe dans lequel chaque sommet a au moins k voisins en son sein, une notion introduite par Seidman en 1983, et la dégénérescence est le plus grand k dont le k-cœur est non vide.

L'épluchage s'exécute en temps linéaire si les sommets sont rangés dans des seaux selon leur degré courant. Matula et Beck ont donné en 1983 un tel ordre « smallest-last » en temps linéaire, et l'algorithme à seaux de Batagelj et Zaveršnik calcule le nombre de cœur de chaque sommet en O(m) :

def core_numbers(adj):
    """Nombre de cœur de chaque sommet : retirer à répétition un sommet de plus petit degré restant."""
    deg = {v: len(adj[v]) for v in adj}
    buckets = [set() for _ in range(max(deg.values(), default=0) + 1)]
    for v, d in deg.items():
        buckets[d].add(v)
    core, k = {}, 0
    for _ in range(len(adj)):
        d = next(i for i, b in enumerate(buckets) if b)   # plus petit seau non vide
        k = max(k, d)                         # le nombre de cœur ne redescend jamais
        v = buckets[d].pop()
        core[v] = k
        for w in adj[v]:
            if w not in core:                 # w perd un voisin : le descendre d'un seau
                buckets[deg[w]].remove(w)
                deg[w] -= 1
                buckets[deg[w]].add(w)
    return core

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

core = core_numbers(adj)
print(dict(sorted(core.items())))
# {'A': 3, 'B': 3, 'C': 3, 'D': 3, 'E': 2, 'F': 2, 'G': 1, 'H': 1}
print(max(core.values()))                     # la dégénérescence du graphe
# 3

La dégénérescence de l'exemple vaut 3, bien en dessous de son Δ de 6. Cela compte pour la coloration, car colorier de façon gloutonne dans l'ordre inverse de l'épluchage donne à chaque sommet au plus dégénérescence voisins déjà coloriés ; la coloration utilise donc au plus dégénérescence + 1 couleurs : 4 ici, ce qui est optimal. La dégénérescence borne aussi le travail de l'énumération des cliques, où traiter les sommets dans l'ordre de dégénérescence est l'accélération standard, et les k-cœurs offrent un premier regard courant sur les grands réseaux : les cœurs internes forment le centre densément maillé, les couches externes la périphérie.

9. Le paradoxe de l'amitié

En 1991, le sociologue Scott Feld a relevé quelque chose qui ressemble à une insulte : en moyenne, vos amis ont plus d'amis que vous. Ce n'est pas un fait sur les gens mais sur les degrés, et le programme de la section 3 l'a déjà calculé pour l'exemple. Le degré moyen vaut 3, mais le degré moyen d'un ami vaut 3,75.

La raison est un biais d'échantillonnage. Quand vous faites la moyenne sur les personnes, chacune compte une fois. Quand vous faites la moyenne sur les amis, vous parcourez chaque amitié et regardez la personne à l'autre bout, si bien qu'une personne ayant d amis est comptée d fois. Les personnes populaires sont surreprésentées dans les listes d'amis des autres précisément parce qu'elles sont populaires. En formules, le degré moyen vaut ∑ d / n, tandis que le degré moyen d'un ami vaut ∑ d² / ∑ d, et l'inégalité de Cauchy–Schwarz montre que le second n'est jamais plus petit que le premier, avec égalité seulement lorsque tous les sommets ont le même degré.

La figure montre une version voisine, personne par personne : six des huit personnes ont moins d'amis que leurs propres amis n'en ont en moyenne, et seuls A et D s'en sortent gagnants. Le cas extrême est l'étoile : dans une étoile à neuf feuilles, le degré moyen vaut 1,8 mais le degré moyen d'un ami vaut 5, et chaque feuille a moins d'amis que son unique ami. Prudence toutefois avec la version personne par personne. L'inégalité ci-dessus porte sur des moyennes et ne garantit rien sur le nombre d'individus situés en dessous. Dans les réseaux réels, l'effet reste pourtant fort : dans l'étude du graphe de Facebook menée en 2011 par Ugander et ses collègues, 92,7 % des utilisateurs avaient moins d'amis que le nombre moyen d'amis de leurs amis.

Le paradoxe a des usages pratiques. Un ami d'une personne choisie au hasard est un meilleur moyen que le hasard pur de trouver une personne bien connectée ; c'est pourquoi on a proposé d'échantillonner les amis de personnes tirées au hasard pour détecter une épidémie tôt, et pourquoi vacciner des connaissances peut protéger plus de personnes que vacciner au hasard.

10. Distributions des degrés dans les réseaux réels

Pour un grand réseau, la liste des degrés est trop longue à lire ; on la résume donc par la distribution des degrés : la proportion de sommets de degré k, pour chaque k. Sa forme en dit long sur la manière dont le réseau s'est formé.

• Les graphes aléatoires du modèle d'Erdős–Rényi, où chaque paire est reliée indépendamment, ont des degrés étroitement concentrés autour de la moyenne, presque aucun sommet n'en étant éloigné.
• De nombreux réseaux réels sont très différents : la plupart des sommets ont un petit degré, et quelques hubs un degré énorme. Barabási et Albert ont proposé en 1999 que l'attachement préférentiel, par lequel les nouveaux sommets se relient de préférence à ceux qui sont déjà populaires, produit une distribution en loi de puissance, et le terme « réseau sans échelle » s'est répandu à partir de là.
• La fréquence réelle des lois de puissance est contestée. Broido et Clauset ont testé 927 jeux de données de réseaux en 2019 et n'ont trouvé de preuves solides d'une structure sans échelle que dans une petite minorité d'entre eux. Les distributions des degrés à queue lourde sont courantes ; une loi de puissance nette ne l'est pas.

Deux mesures fondées sur le degré reviennent sans cesse en analyse de réseaux. La centralité de degré classe les sommets simplement par degré, la réponse la moins coûteuse à « qui est important ? ». Et l'assortativité, introduite par Newman en 2002, mesure si les sommets de fort degré ont tendance à se relier à d'autres sommets de fort degré. Newman a constaté que les réseaux sociaux sont assortatifs et que de nombreux réseaux technologiques et biologiques sont disassortatifs, leurs hubs se reliant surtout à des sommets de faible degré. Le réseau de l'exemple est lui aussi disassortatif : son hub A est le seul ami des deux feuilles.

11. Graphes orientés : degré entrant et degré sortant

Dans un graphe orienté, chaque arc a une origine et une extrémité ; un sommet a donc un degré entrant, le nombre d'arcs qui arrivent, et un degré sortant, le nombre d'arcs qui partent. Le lemme des poignées de main se dédouble en conséquence : chaque arc ajoute un à un degré sortant et un à un degré entrant, donc

∑ in-deg(v)  =  ∑ out-deg(v)  =  m          le nombre d'arcs

Remarquez l'absence du facteur 2, une erreur fréquente quand on passe des graphes non orientés aux graphes orientés. Les degrés orientés ont leurs propres significations. Un sommet de degré entrant 0 est une source et un sommet de degré sortant 0 un puits ; le tri topologique par l'algorithme de Kahn part des sources et procède en abaissant les degrés entrants. Un graphe orienté connexe possède un circuit empruntant chaque arc exactement une fois exactement lorsque chaque sommet a un degré entrant égal à son degré sortant. Et dans un graphe du Web, le degré entrant est une première mesure de popularité, la quantité que PageRank affine en pondérant chaque lien entrant par l'importance de sa source.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (publié en 1741), 128 à 140. L'observation à l'origine du lemme des poignées de main, énoncée pour des ponts et des régions de terre.
2. Brooks, R. L. (1941). "On Colouring the Nodes of a Network." Proceedings of the Cambridge Philosophical Society 37(2), 194 à 197.
3. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1), 69 à 81.
4. Havel, V. (1955). "Poznámka o existenci konečných grafů." Časopis pro pěstování matematiky 80(4), 477 à 480. Une remarque sur l'existence des graphes finis.
5. Erdős, P. et Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal." Matematikai Lapok 11, 264 à 274. Graphes à degrés des sommets prescrits.
6. Ore, O. (1960). "Note on Hamilton Circuits." American Mathematical Monthly 67(1), 55.
7. Hakimi, S. L. (1962). "On the Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I." Journal of the Society for Industrial and Applied Mathematics 10(3), 496 à 506.
8. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3, 25 à 30.
9. Welsh, D. J. A. et Powell, M. B. (1967). "An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems." The Computer Journal 10(1), 85 à 86.
10. Matula, D. W. et Beck, L. L. (1983). "Smallest-Last Ordering and Clustering and Graph Coloring Algorithms." Journal of the ACM 30(3), 417 à 427.
11. Seidman, S. B. (1983). "Network Structure and Minimum Degree." Social Networks 5(3), 269 à 287. Le k-cœur.
12. Feld, S. L. (1991). "Why Your Friends Have More Friends Than You Do." American Journal of Sociology 96(6), 1464 à 1477.
13. Barabási, A.-L. et Albert, R. (1999). "Emergence of Scaling in Random Networks." Science 286(5439), 509 à 512.
14. Newman, M. E. J. (2002). "Assortative Mixing in Networks." Physical Review Letters 89(20), 208701.
15. Ugander, J., Karrer, B., Backstrom, L. et Marlow, C. (2011). "The Anatomy of the Facebook Social Graph." arXiv:1111.4503.
16. Batagelj, V. et Zaveršnik, M. (2011). "Fast Algorithms for Determining (Generalized) Core Groups in Social Networks." Advances in Data Analysis and Classification 5(2), 129 à 145. Diffusé d'abord en 2003 sous le titre « An O(m) Algorithm for Cores Decomposition of Networks ».
17. Broido, A. D. et Clauset, A. (2019). "Scale-Free Networks Are Rare." Nature Communications 10, 1017.
18. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.