<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Algo - graphes aléatoires
Comment générer un graphe aléatoire... Générer une séquence de nombres aléatoires indépendants est un problème connu et plutôt bien résolu. Générer une structure aléatoire comme une graphe est aussi facile. En revanche, générer un graphe aléatoire vérifiant une propriété - la distribution des degrés - n'est pas aussi simple qu'anticipé.
Step1:  Graphe aléatoire - matrice d'adjacence aléatoire
L'existence de chaque arc est défini par une variable binomiale de paramètre $p$.
Step2:  En le visualisant...
Step3:  Vocabulaire lié aux graphes
arc (ou edge en anglais) 
Step4:  D'après les remarques précédentes, $\sum A_{pq} > 0$ s'il existe un chemin reliant les noeuds $p, q$, donc s'il font partie de la même composante connexe. Et 0 si les deux noeuds font partie de deux composantes connexes distinctes.
Trouver le nombre de composantes connexes
On s'inspire d'un algorithme de coloriage. Au début, chaque noeud appartient à sa propre composante connexe noté $c_i$. Pour chaque arc reliant deux noeuds i et j, on associe aux deux noeuds à la composante $\min(c_i, c_j)$. On continue tant qu'un noeud change de composante connexe.
Step5:  Génération d'un graphe aléatoire
Les graphes issues de réseaux sociaux ont souvent des propriétés statistiques particulières. La distribution des degrés des noeuds suit souvent une loi à queue épaisse. C'est dans cette catégorie qu'on range les lois qui admettent une espérance mais pas de variance.
Donc on ne veut pas générer n'importe quel graphe aléatoire, on veut générer un graphe aléatoire dont la distribution des degrés des noeuds est connue.
On s'inspire de algorithme graphe aléatoire.
Etape 1 
Step6:  Etape 2 
Step7:  On remarque que la somme des degrés ne peut être impaire car chaque arc est connecté à deux noeuds.
Step8:  On regarde la distribution des degrés 
Step9:  L'algorithme ne semble pas aboutir à un graphe qui répond au critère souhaité. Il existe deux cas pour lesquels l'algorithme reste bloqué. On note $A_t$ l'ensemble des noeuds à l'itération t dont les degrés sont inférieurs au degré souhaité.
Tous les noeuds dans l'ensemble $A_t$ sont déjà reliés entre eux.
La seule option possible est de créer un arc entre un noeud et lui-même.
Pour éviter cela, on choisit après 5 tirages ne donnant lieu à aucune création d'arc d'en supprimer quelques-uns. L'algorithme qui suit n'est pas le plus efficace mais voyons déjà s'il marche avant de nous pencher sur un autre.
Version 2
Step10:  Il est possible que cet algorithme aboutisse au résultat souhaité même avec beaucoup de temps. Est-ce la stratégie ou le fait que la distribution des noeuds ne soit pas réalisable.
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
%matplotlib inline
Explanation: Algo - graphes aléatoires
Comment générer un graphe aléatoire... Générer une séquence de nombres aléatoires indépendants est un problème connu et plutôt bien résolu. Générer une structure aléatoire comme une graphe est aussi facile. En revanche, générer un graphe aléatoire vérifiant une propriété - la distribution des degrés - n'est pas aussi simple qu'anticipé.
End of explanation
import numpy
mat = numpy.random.random((15, 15))
mat = mat + mat.T
adja = (mat >= 1.4).astype(int)
for i in range(adja.shape[0]):
    adja[i ,i] = 0
adja
Explanation: Graphe aléatoire - matrice d'adjacence aléatoire
L'existence de chaque arc est défini par une variable binomiale de paramètre $p$.
End of explanation
import networkx
import matplotlib.pyplot as plt
fix, ax = plt.subplots(1, 1,figsize=(4,4))
G = networkx.from_numpy_matrix(adja)  
networkx.draw(G, with_labels=True, ax=ax) 
degres = adja.sum(axis=1)
degres
distrib = {}
for d in degres:
    if d in distrib:
        distrib[d] += 1
    else:
        distrib[d] = 1
distrib
Explanation: En le visualisant...
End of explanation
adjan = adja.copy()
conne = numpy.zeros(adja.shape)
for i in range(1, adja.shape[0]):
    conne += adjan
    adjan = adjan @ adja
(conne > 0).astype(int)
Explanation: Vocabulaire lié aux graphes
arc (ou edge en anglais) : lien liant deux noeuds, il peut être orienté ou non, s'il est orienté, les deux extrémités ne jouent pas le même rôle, l'arc ne peut être "parcouru" que de la première extrémité vers la seconde.
noeud (vertex en anglais) : élément du graphe
graphe : un graphe est défini par un ensemble de noeuds et un ensemble d'arcs
matrice d'adjacence : matrice binaire de dimension $N \times N$, $A=(a_{ij}){ij}$ et $a{ij} = 1$ s'il existe un arc reliant le noeud i à j, 0 sinon.
chemin : séquence de noeuds et d'arcs appartenant au graphe
prédécesseur et successeur : si un arc orienté relie les noeuds i à j, i est le prédecesseur de j, j est le successeur de i. Par extension, si i apparaît toujours avec j dans tous les chemins possibles du graphes, i est un prédecesseur de j.
arbre : cas particulier des graphes orientés, il existe un unique prédecesseur à tous les noeuds nommés la racine, un noeud sans successeur est appelé feuille (ou leaf en anglais). Dans un arbre binaire, chaque noeud n'a que deux successeurs directs.
degré d'un noeud : nombre d'arcs connectés à un noeud, on peut distinguer pour les graphes orientés le fait que les arcs partent ou arrivent à un noeud
Composante connexe : au sein d'une composante connexe, il existe toujours un chemin reliant n'importe quelle paire de noeuds.
Quelques propriétés de la matrice d'adjacence :
Pour un graphe non orienté, la matrice d'adjacence est symétrique.
La somme sur la ligne i est égale au degré du noeud i.
La matrice d'adjacence est triangulaire supérieue dans le cas d'un arbre dont les noeuds sont numérotés en largeur d'abord (un noeud a toujours un numéro supérieur à tous des niveaux moins profonds).
Aparté : matrice d'adjacence à la puissance n
Si $A$ est une matrice d'adjacence, $a^2_{ik}$ et un coefficient de cette matrice. $a^2_{ik} \sum_j a_{ij} a_{jk}$. Comme $a_{pq} \in {0, 1}$, $a^2_{ik} > 0$ s'il existe un $j$ tel que $ a_{ij} = a_{jk} = 1$. Autrement dit, les noeuds $i j, k$ sont reliés. Si $a^2_{ik} > 0$, alors il existe un chemin de longueur 2 entre les noeuds $i, k$. Par récurrent, $A^3_{pq}$ est positif s'il existe un chemin de longueur 3 reliant les noeuds $p, q$.
On calcule $\sum{A}=A + A^2 + A^3 + ... + A^n$ où n est la dimension de la matrice.
End of explanation
mat = numpy.random.random((15, 15))
mat = mat + mat.T
adja = (mat >= 1.45).astype(int)
for i in range(adja.shape[0]):
    adja[i ,i] = 0
fix, ax = plt.subplots(1, 1, figsize=(4, 4))
G = networkx.from_numpy_matrix(adja)  
networkx.draw(G, with_labels=True, ax=ax) 
C = numpy.arange(adja.shape[0])
maj = 1
while maj > 0:
    maj = 0
    for i in range(adja.shape[0]):
        for j in range(i + 1, adja.shape[1]):
            if adja[i, j] > 0 and C[i] != C[j]:
                maj += 1
                C[i] = C[j] = min(C[i], C[j])
                
C
set(C)
print("Il y a %r composantes connexes." % len(set(C)))
Explanation: D'après les remarques précédentes, $\sum A_{pq} > 0$ s'il existe un chemin reliant les noeuds $p, q$, donc s'il font partie de la même composante connexe. Et 0 si les deux noeuds font partie de deux composantes connexes distinctes.
Trouver le nombre de composantes connexes
On s'inspire d'un algorithme de coloriage. Au début, chaque noeud appartient à sa propre composante connexe noté $c_i$. Pour chaque arc reliant deux noeuds i et j, on associe aux deux noeuds à la composante $\min(c_i, c_j)$. On continue tant qu'un noeud change de composante connexe.
End of explanation
def distribution_to_degree_list(hist):
    N = int(hist.sum())
    deg = numpy.zeros(N, dtype=numpy.int32)
    p = 0
    for i, nh in enumerate(hist):
        for n in range(nh):
            deg[p] = i
            p += 1
    return deg
        
dist = numpy.array(numpy.array([0, 4, 3, 2]))
distribution_to_degree_list(dist)
Explanation: Génération d'un graphe aléatoire
Les graphes issues de réseaux sociaux ont souvent des propriétés statistiques particulières. La distribution des degrés des noeuds suit souvent une loi à queue épaisse. C'est dans cette catégorie qu'on range les lois qui admettent une espérance mais pas de variance.
Donc on ne veut pas générer n'importe quel graphe aléatoire, on veut générer un graphe aléatoire dont la distribution des degrés des noeuds est connue.
On s'inspire de algorithme graphe aléatoire.
Etape 1 : transformer une distribution des degrés des noeuds en une liste de degré souhaité pour chaque noeud.
End of explanation
import warnings
from tqdm import tqdm  # pour visualiser la progression de l'algorithme
def random_graph(distribution_degree):
    degrees = distribution_to_degree_list(distribution_degree)
    current = numpy.zeros(degrees.shape[0], dtype=numpy.int32)
    expected = degrees.sum()
    adja = numpy.zeros((degrees.shape[0], degrees.shape[0]), dtype=numpy.int32)
    nb = 0
    
    # tqdm: une boucle qui affiche l'avancement dans un notebook
    # on évite la boucle infinie en limitant le nombre d'itération 
    loop = tqdm(range(expected * 5))
    for n_iter in loop:
        loop.set_description("sum=%r expected=%r" % (nb, expected))
        nodes = [i for i, (c, d) in enumerate(zip(current, degrees)) 
                 if c < d]
        if len(nodes) == 1:
            i, j = 0, 0
        elif len(nodes) == 2:
            di, dj = 0, 0
            i, j = nodes[di], nodes[dj]
        else:
            di, dj = numpy.random.randint(0, len(nodes), 2)
            i, j = nodes[di], nodes[dj]
        if i == j or adja[i, j] == 1:
            # arc déjà créé ou impossible
            continue
        current[i] += 1
        current[j] += 1
        adja[i, j] = 1
        adja[j, i] = 1
        nb += 2
        
        if nb >= expected:
            # Tous les noeuds ont le degré souhaité.
            loop.set_description("sum=%r expected=%r" % (nb, expected))
            break
    if nb < expected:
        warnings.warn("Graphe incomplet\ndegrees=%r\ncurrent=%r" % (degrees, current))
    return adja
adja = random_graph(numpy.array([0, 5, 3, 2]))
adja
Explanation: Etape 2 : on part d'un tableau de même dimension qui représente les degrés du graphe en cours de construction. Il est nul au départ. On tire des noeuds de façon aléatoire tant que ce degré est inférieur au degré souhaité. On l'incrémente à chaque fois qu'un arc est créé.
Version 1
End of explanation
adja = random_graph(numpy.array([0, 4, 3, 2]))
adja
Explanation: On remarque que la somme des degrés ne peut être impaire car chaque arc est connecté à deux noeuds.
End of explanation
adja.sum(axis=1)
from collections import Counter
Counter(adja.sum(axis=1))
Explanation: On regarde la distribution des degrés :
End of explanation
def random_graph_remove(distribution_degree):
    degrees = distribution_to_degree_list(distribution_degree)
    current = numpy.zeros(degrees.shape[0], dtype=numpy.int32)
    expected = degrees.sum()
    adja = numpy.zeros((degrees.shape[0], degrees.shape[0]), dtype=numpy.int32)
    nb = 0
    
    loop = tqdm(range(expected * 5))
    last_added = 0
    n_removed = 0
    edges = {i: [] for i in range(current.shape[0])}
    for n_iter in loop:
        loop.set_description("sum=%r expected=%r n_removed=%r" % (nb, expected, n_removed))
        nodes = [i for i, (c, d) in enumerate(zip(current, degrees)) 
                 if c < d]
        if len(nodes) > 1:
            di, dj = numpy.random.randint(0, len(nodes), 2)
            i, j = nodes[di], nodes[dj]
        else:
            i = j = 0
        
        if i == j or adja[i, j] == 1:
            if last_added + 5 < n_iter:
                # on supprime un arc
                nodes = [i for i, c in enumerate(current) if c > 0]
                di = (0 if len(nodes) <= 1 else 
                      numpy.random.randint(0, len(nodes)))
                i = nodes[di]
                dh = (0 if len(edges[i]) <= 1 else
                      numpy.random.randint(0, len(edges[i])))
                j = edges[i][dh]
                
                adja[i, j] = 0
                adja[j, i] = 0
                edges[i].remove(j)
                edges[j].remove(i)
                current[i] -= 1
                current[j] -= 1
                nb -= 2
                n_removed += 2
            continue
        current[i] += 1
        current[j] += 1
        adja[i, j] = 1
        adja[j, i] = 1
        nb += 2
        last_added = n_iter
        edges[i].append(j)
        edges[j].append(i)
        
        if nb >= expected:
            # Tous les noeuds ont le degré souhaité.
            loop.set_description("sum=%r expected=%r n_removed=%r" % (nb, expected, n_removed))
            break
    if nb < expected:
        warnings.warn("Graphe incomplet\ndegrees=%r\ncurrent=%r" % (degrees, current))
    return adja
adja = random_graph_remove(numpy.array([0, 4, 3, 2]))
adja
Counter(adja.sum(axis=1))
Explanation: L'algorithme ne semble pas aboutir à un graphe qui répond au critère souhaité. Il existe deux cas pour lesquels l'algorithme reste bloqué. On note $A_t$ l'ensemble des noeuds à l'itération t dont les degrés sont inférieurs au degré souhaité.
Tous les noeuds dans l'ensemble $A_t$ sont déjà reliés entre eux.
La seule option possible est de créer un arc entre un noeud et lui-même.
Pour éviter cela, on choisit après 5 tirages ne donnant lieu à aucune création d'arc d'en supprimer quelques-uns. L'algorithme qui suit n'est pas le plus efficace mais voyons déjà s'il marche avant de nous pencher sur un autre.
Version 2
End of explanation
def distribution_degree_realisable(distribution):
    degrees = -numpy.array(sorted(-distribution_to_degree_list(distribution)))
    if degrees.sum() % 2 != 0:
        return False
    sumdi = 0
    for i in range(degrees.shape[0] - 1):
        sumdi += degrees[i]
        mindi = numpy.minimum(degrees[i+1:], i + 1).sum()
        if sumdi >= i * (i + 1) + mindi:
            return False
    return True
distribution_degree_realisable(numpy.array([0, 2, 0, 0, 0, 0, 0, 0, 0, 1]))
distribution_degree_realisable(numpy.array([0, 4, 3, 2]))
fix, ax = plt.subplots(1, 1, figsize=(4, 4))
G = networkx.from_numpy_matrix(adja)  
networkx.draw(G, with_labels=True, ax=ax) 
Explanation: Il est possible que cet algorithme aboutisse au résultat souhaité même avec beaucoup de temps. Est-ce la stratégie ou le fait que la distribution des noeuds ne soit pas réalisable.
End of explanation
<END_TASK>