Réseau social et Coupe minimale

En 2016, le sujet d'Informatique du concours d'admission pour les filières MP et PC, proposait de manipuler la structure union-find sur un exemple de coupe minimale d'un réseau social.

Nous nous proposons de suivre les questions de ce sujet et d'y répondre, en donnant la version impérative attendue pour l'épreuve et une version orientée objet.

Petit historique des Union-Find

La structure a été inventée en 1964 par Bernard A. Galler mathématicien et informaticien de l'Université du Michigan et Michael J. Fischer informaticien.

C'est surtout dans les années 70 que la structure a beaucoup été étudiée notamment pour améliorer la complexités de ses opérations élémentaires find et union.

Mais revenons au sujet du concours.

PARTIE I. Réseaux sociaux

Modélisation impérative

Structure de données. Les individus sont numérotés de 0 à \(n - 1\) et les liens d'amitié par la liste [i, j] ou [j, i]... voilà déjà une première aberration. Puisque l'ordre n'a pas d'importance, on prendra l'ensemble (objet de type set) {i,j} qui est égal à l'ensemble {j, i}.

Un réseau \(R\) entre \(n\) individus est modélisé par une liste reseau de 2 éléments :

• reseau[0] vaut \(n\)
• reseau[1] vaut la liste, éventuellement vide, des liens déclarés (donc des ensembles à 2 élements)

Modélisation Objet

Définition Objet du Réseau

Par souci de concision, on laissera de côté la syntaxe simulant la privatisation des attributs avec @property.

class Reseau:

    def __init__(self, n, liens=None):
        self.n = n
        self.liens = [] if liens is None else [{a,b} for a, b in liens]
        self.saggital = gv.Graph(engine='neato', format='svg', graph_attr={'size':'2.4,2.4!'}, node_attr={'shape': 'circle', 'fixedsize':'true'})
        self.init_saggital()

    # ---
    # --- METHODES POUR LE GRAPHE (VUE)

    def init_saggital(self):
        for node_id in range(self.n):
            self.saggital.node(str(node_id))
        for n1, n2 in self.liens:
            self.saggital.edge(str(n1), str(n2))

    def positionne(self, nodes_positions, ech=1):
        """permet de contrôler l'affichage des noeuds"""
        for n, x, y in nodes_positions:
            pos = f'{ech*x},{ech*y}!'
            self.saggital.node(str(n), pos=pos)

    def write(self, filename='test', rep=DEFAULT_REP):
        self.saggital.render(f'{rep}/{filename}', view=True)

Notre définition objet permet de modéliser et visualiser le réseau de la figure 1 du sujet :

Réseau de la Figure 1

>>> FIG1 = Reseau(8, [(0, 1), (1, 3), (3, 2), (2, 0), (0, 3), (2, 1), (4, 5), (5, 7), (7, 6), (6, 4), (7, 4), (6, 5), (2, 4), (5, 3)])
>>> FIG1.positionne([(0,-3,1), (2, -1, 1), (4, 1, 1), (6, 3, 1), (1,-3,-1), (3, -1, -1), (5, 1, -1), (7, 3, -1)], 0.5) 
>>> FIG1.saggital

Question 1

Il s'agit de donner la modélisation de deux réseaux A et B dont on a le schéma du graphe :

Version ImpérativeVersion Objet

Je rappelle que j'ai remplacé les list par des set pour les arètes puisqu'elles ne sont pas orientées.

>>> RA = [5, [{0,1}, {0,2}, {0,3}, {1,2}, {2,3}]]
>>> RB = [5, [{0,1}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}]]

Création via l'objet Reseau et positionnement des noeuds :

>>> RA = Reseau(5, [{0,1}, {0,2}, {0,3}, {1,2}, {2,3}])
>>> RA.positionne([(2,0,0), (0,-1,1), (3,-1,-1), (1,1,1), (4,1,-1)], 0.5)
>>> RA.saggital

>>> RB = Reseau(5, [{0,1}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}])
>>> RB.positionne([(2,0,0.5), (0,-2,0), (3,0,-0.5), (1,-1,0), (4,1,0)], 0.8)
>>> RB.saggital

Question 2

Création d'un réseau vide. J'en profite pour changer le nom et adopter la notation snake_case conforme PEP8.

Version ImpérativeVersion Objet

def creer_reseau_vide(n):
    return [n, []]

Il n'y a pas de fonction à écrire puisque c'est le rôle du constructeur. Par exemple pour \(n = 5\) :

>>> VIDE = Reseau(5)
>>> VIDE.positionne([(0,-2,0), (1,-1,0), (2,0,0), (3,1,0), (4,2,0)], 0.8)
>>> VIDE.saggital

Question 3

Cette question n'a pas de sens avec ma modélisation des arètes via les ensembles. Avec des listes on doit effectivement faire ceci :

def est_un_lien_entre(paire, i, j):
    return paire == [i,j] or paire == [j,i]

Question 4

Une fonction sont_amis qui prend un réseau en paramètre ainsi que deux entiers et retourne True ssi les entiers sont liés dans le réseau.

Version ImpérativeVersion Objet

Avec ma modélisation :

def sont_amis(reseau, i, j):
    return {i,j} in reseau[1]

Si on suit le sujet :

def sont_amis(reseau, i, j):
    return any(est_un_lien_entre(paire, i, j) for paire in reseau[1])

class Reseau:
    # ...

    def sont_amis(self, i, j):
        return {i,j} in self.liens

Par exemple, avec le Réseau A nommé RA :

>>> RA.sont_amis(2, 3)
True
>>> RA.sont_amis(0, 4)
False

Dans le pire des cas, on parcourt tous les liens pour se rendre compte que celui qu'on cherche n'y est pas. La complexité en temps est donc en \(O(m)\).

Question 5

On souhaite pouvoir ajouter des liens d'amitié à nos réseaux. On constate que quelque soit la modélisation, le fait d'utiliser une liste oblige à tester l'existence du lien avant de l'ajouter.

Version ImpérativeVersion Objet

def declare_amis(reseau, i, j):
    if not sont_amis(reseau, i, j):
        reseau[1].append({i,j})

class Reseau:
    # ...

    def declare_amis(self, i, j):
        if not self.sont_amis(i, j):
            self.liens.append({i,j})

La complexité est donc la même que le test de l'existence du lien soit \(O(m)\).

Question 6

Obtenir la liste des amis d'une personne.

Version ImpérativeVersion Objet

def liste_des_amis_de(reseau, i):
    return [j for j in range(reseau[0]) if sont_amis(reseau, i, j)]

class Reseau:
    # ...

    def personnes(self):
        return range(self.n)

    def liste_des_amis_de(self, i):
        return [j for j in self.personnes() if self.sont_amis(i, j)]

Pour chaque personne du réseau, on recherche un lien entre cette personne et celle dont on cherche les amis. Cela fait donc une complexité en \(O(n\times m)\) dans le pire des cas.

PARTIE II. Partitions

Définition

Une partition en \(k\) groupes d'un ensemble \(A\) à \(n\) éléments consiste en \(k\) sous-ensembles disjoints non vides \(A_1, \ldots, A_k\) de \(A\) dont l'union est \(A\).

Par exemple \(A_1 = \{1, 3\}\), \(A_2 = \{0, 4, 5\}\) et \(A_3 = \{2\}\) est une partition en trois groupes de \(A = [\![6]\!]\).

Principe de la structure

Les élémenst de chaque groupe sont structurés en une relation filiale : chaque élément a un (unique) parent choisi dans le groupe et l'unique élément du groupe qui est son propre parent est appelé le représentant du groupe.

Voici notre classe Partition (je ne remets pas la partie graphe qui est similaire à celle de la classe Réseau) :

Classe Partition

La relation parent est un dictionnaire.

class Partition:

    def __init__(self, n=0, liens=None):
        self.n = n
        self.parent = {i:i for i in range(n)} 
        if liens is not None:
            for i,j in liens:
                self.parent[i] = j 
        self.saggital = gv.Digraph(engine='neato', format='svg', node_attr={'shape': 'circle', 'width': '0.3', 'fixedsize':'true'}, edge_attr={'arrowsize':'0.6'})
        self.init_saggital()

Voici par exemple la définition de la partition présentée en Figure 2 du sujet :

Partition de la Figure 2

>>> FIG2 = Partition(16, [(14,11), (11,1), (8,1), (1,9), (13,9), (15,9),
            (12,4), (4,3), (2,3), (7,5), (6,5), (0,6)])
>>> FIG2.saggital

La modélisation impérative utilise un tableau parent qui donne la valeur du parent de chaque noeud. Par exemple pour la Figure 2 :

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
parents[i]	6	9	3	3	3	5	5	5	1	9	10	1	4	9	11	9

Question 7

Version impérativeVersion objet

Les représentations filiales A et B :

>>> RFA = [5,1,1,3,4,5,1,5,5,7]
>>> RFB = [3,9,0,3,9,4,4,7,1,9]

>>> PA = Partition(10, [(i, RFA[i]) for i in range(10)])
>>> PA.saggital

>>> PB = Partition(10, [(i, RFB[i]) for i in range(10)])
>>> PB.saggital

Question 8

Création d'une partition à \(n\) groupes constitués d'un unique élément.

Version impérativeVersion objet

def creer_partition_singletons(n):
    return list(range(n))

Pas de fonction à écrire puisque le constructeur par défaut crée cette partition singletons :

>>> PSINGLETONS = Partition(5)
>>> PSINGLETONS.saggital

A partir de la question 9, on s'attaque aux opérations de la structure :

• déterminer si deux noeuds font partie du même groupe
• fusionner deux groupes pour n'en faire qu'un

Question 9

Version impérativeVersion objet

def representant(parent, i):
    while parent[i] != i:
        i = parent[i]
    return i

class Partition:
    # ...

    def representant(self, i):
        while i != self.parent[i]:
            i = self.parent[i]
        return i

Dans le pire des cas, c'est-à-dire lorsque la partition est réduite à un unique groupe contenant tous les éléments, ordonnés. La recherche du représentant du dernier élément ie celui qui n'est le parent de personne, parcourra les \(n\) éléments. La complexité est donc en \(O(n)\).

L'algorithme de la fusion des groupes dont on donne 2 éléments \(i\) et \(j\) est le suivant :

1. Calculer \(p\) et \(q\) les représentants de \(i\) et \(j\) respectivement,
2. faire parent[p] = q

Question 10

Version impérativeVersion objet

def fusion(parent, i, j):
    parent(representant[i]) = representant[j]

On rappelle la partition de la Figure 2 :

Faisons en une copie, et déplaçons un peu les sommets pour préparer la fusion (la méthode deplace permet de décaler la position d'un noeud et éventuellement tout son groupe) :

>>> FIG3 = FIG2.copy()
>>> FIG3.deplace(3, 1.5, 0)
>>> FIG3.deplace(10, 1, 0)
>>> FIG3.deplace(5, -5.25, -1)
>>> FIG3.deplace(9, 1.5, 0, False)
>>> FIG3.place(0.7)
>>> FIG3.saggital

Effectuons la fusion :

class Partition:
    # ...

    def fusion(self, i, j):
        self.parent[self.representant(i)] = self.representant(j)

>>> FIG3.fusion(6, 14)
>>> FIG3.place(0.7)
>>> FIG3.saggital

Question 11

Si on a une partition de \(n\) singletons alors les \((n - 1)\) fusions suivantes nécessitent \(1\,\times 2\,\times ... \times\,(n-1)\) opérations et donc de l'ordre de \(n^2\) opérations.

>>> fusion(1, 0)
>>> fusion(2, 1)
...
>>> fusion(n-1, n-2)

On remédie à cette mauvaise performance en compressant la relation lors de la recherche du représentant. La question suivante met en oeuvre la compression.

Question 12

Version impérativeVersion objet

def representant(parent, i):
    a = i
    while a != parent[a]:
        a = parent[a]
    ancetre = a
    a = i
    while a != parent[a]:
        b = parent[a]
        parent[a] = ancetre
        a = b

On fait 2 parcours au lieu d'un seul, mais d'un point de vue complexité on reste en \(O(n)\) ce qui permet de dire que cette opération de compression est gratuite.

class Partition:
    # ...

    def representant(self, i, compression=False):
        if compression:
            a = i
            while a != self.parent[a]:
                a = self.parent[a]
            ancetre = a
            a = i
            while a != self.parent[a]:
                b = self.parent[a]
                self.parent[a] = ancetre
                a = b
            self.init_saggital()
            return ancetre
        else:
            while i != self.parent[i]:
                i = self.parent[i]
            return i

Utilisation sur la relation filiale de la Figure 2, en compressant à partir du noeud 14 :

>>> FIG2.representant(14, True)
>>> FIG2.saggital

La dernière question de cette partie permet d'obtenir les groupes de la partition sous la forme d'une liste de liste.

Question 13

A noter que la structure de dictionnaire serait plus adaptée.

Version impérativeVersion objet

def liste_des_groupes(parent):
    groupes = {}
    n = len(parent)
    for i in range(n):
        if parent[i] == i:
            groupes[i] = [i]
    for i in range(n):
        if parent[i] != i:
            groupes[representant(parent, i)].append(i)
    return list(groupe.values())

class Partition:
    # ...

    def liste_des_groupes(self):
        groupes = {}
        for i in self.nodes():
            if self.parent[i] == i:
                groupes[i] = [i]
        for i in self.nodes():
            if self.parent[i] != i:            
                groupes[self.representant(i, True)].append(i)
        return list(groupes.values())       

Par construction, chaque premier élément est le représentant du groupe.

>>> FIG2.liste_des_groupes()
[[3, 2, 4, 12], [5, 0, 6, 7], [9, 1, 8, 11, 13, 14, 15], [10]]

Ce calcul réalise la compression de tous les groupes :

>>> FIG2.saggital

PARTIE III. Algorithme randomisé pour la coupe minimum

Pour résoudre ce problème nous allons utiliser l’algorithme randomisé suivant :

Entrée : un réseau social à \(n\) individus

1. Créer une partition \(P\) en \(n\) singletons de \([\![n]\!]\)
2. Initialement aucun lien d'amitié n'est marqué
3. Tant que la partition \(P\) contient au moins trois groupes et qu'il reste des liens d'amitié non marqués dans le réseau faire :
   1. Choisir un lien uniformément au hasard parmi les liens non marqués du réseau, notons-le [i,j].
   2. Si \(i\) et \(j\) n'appartiennent pas au même groupe dans la partition \(P\), fusionner les deux groupes correspondants
   3. Marquer le lien [i,j].
4. Si \(P\) contient \(k \geq 3\) groupes, faire \(k − 1\) fusions pour obtenir deux groupes.
5. Renvoyer la partition \(P\).

Question 14

Pour profiter au maximum des listes de Python, on crée la liste de indices des liens (liste des non marqués) ; on mélange cette liste via la fonction shuffle du module random ensuite il suffira de dépiler cette liste par la fin via des pop().

La longueur d'une partition est le nombre de groupes, que l'on peut calculer en comptant les éléments qui sont leur propre parent.

Version impérativeVersion objet

def coupe_minimum_randomisee(reseau):
    n = reseau[0]
    m = len(reseau[1])
    p = creer_partition_singletons(n)
    liens_non_marques = list(range(m))
    random.shuffle(liens_non_marques)
    while longueur(p) >= 3 and liens_non_marques:
        i, j = reseau[1][liens_non_marques.pop()]
        if representant(p, i) != representant(p, j):
            fusion(p, i, j)
    if longueur(p) >= 3:
        reduire(p)
    return p

où

def longueur(parent):
    return sum(i == parent[i] for i in range(len(parent))

et

def reduire(parent):
    representants = [i for i in range(len(parent)) if i == parent[i]]
    ancetre = 0
    for i in representants[2:]:
        fusion(parent, i, representants[ancetre])
        nacetre = ancetre - 1

On modifie notre classe Reseau :

class Reseau:

    def __init__(self, ...):
        # ...

        self.partition = Partition(n)

    def coupe_minimum_randomisee(self):
        p = self.partition
        liens_non_marques = list(range(len(self.liens)))
        random.shuffle(liens_non_marques)
        while len(p) >= 3 and liens_non_marques:
            i, j = self.liens[liens_non_marques.pop()]
            if p.representant(i) != p.representant(j):
                p.fusion(i, j)
        if len(p) >= 3:            
            p.reduire()

Et les ajouts à la classe Partition :

class Partition:
    # ...

    def __len__(self):
        return sum(self.parent[i] == i for i in self.nodes())

    def reduire(self):
        representants = [i for i in self.nodes()]
        ancetre = 0
        for k in range(2, len(representants)):
            self.fusion(representants[k], representants[ancetre])
            ancetre = 1 - ancetre

Complexité :

• la création de la partition singletons est en \(O(n)\)
• le mélange via shuffle utilise probablement un algorithme efficace type Fisher-Yates en \(O(m)\)
• la boucle while effectue au plus \(m\) passages où elle fait :
  • un calcul de représentant qui est en \(O(\alpha(n))\)
  • une fusion qui est aussi un calcul de representant

Au total on a donc \(O(n + m.\alpha(n))\).

Question 15

Version impérativeVersion objet

def taille_coupe(reseau, parent):
    return len([(i,j) for i,j in reseau[1] if representant(parent, i) != representant(parent, j)])

class Reseau:
    # ...

    def taille_coupe(self):
        return len([(i,j) for i,j in self.liens if self.partition.representant(i) != self.partition.representant(j)])

Test

Si on reprends le réseau FIG1 de la Figure 1 :

On peut alors calculer une partition :

>>> FIG1.coupe_minimum_randomisee()
>>> FIG1.saggital()

On constate que celle-ci n'est pas minimale :

>>> FIG1.taille_coupe()
3

Un autre essai :

>>> FIG1.reset_partition()
>>> FIG1.coupe_minimum_randomisee()
>>> FIG1.saggital()

Cette fois on obtient le minimum :

>>> FIG1.taille_coupe()
2

En exécutant plusieurs fois la coupe, on constate une probabilité d'obtenir le minimum sur 8 exécutions indépendantes de l'ordre de 90%. :