README.md

# Projet RI

Nous allons analyser un réseau de collaboration scientifique en informatique. 
Le réseau est extrait de DBLP et disponible sur SNAP.
GraphStream permet de mesurer de nombreuses caractéristiques d'un réseau.
La plupart de ces mesures sont implantées comme des méthodes statiques dans la classe Toolkit. 
Elles vous seront très utiles par la suite.
# TP 1: 

## 1- Tout d'abord :

j'ai commencé par télécharger les données et les lire avec GraphStream.

## 2- Quelques mesures de base :
J'ai calculé quelques mesures de base : comme le nombre de nœuds et d'arêtes, le degré moyen ainsi que le coefficient de clustring.
- Nombre de noeuds : N = 317080
```java
int nodeCount = graph.getNodeCount();
```
- Nombre de liens : E = 1049866
```java
int edgeCount = graph.getEdgeCount();
```



- Degré moyen : ⟨k⟩ = 6.62208890914917
```java
double averageDegree = Toolkit.averageDegree(graph);
```

- Coefficient de clustering (réel) : 0.6324308280637396 
```java
double clusteringCoefficient = Toolkit.averageClusteringCoefficient(graph);
```
- Coefficient de clustering (aléatoire) : ⟨k⟩/N = 2.0884599814397534E-5

## 3- Autres mesures 
Voyons maintenant si le graphe est connexe : 
- Le réseau est-il connexe ? : Oui

```java
boolean isConnected = Toolkit.isConnected(graph);
```

- Degré moyen minimal pour qu'un graphe aléatoire soit connexe : 12.666909386951092

```java
double minAverageDegreeForConnectivity = Math.log(nodeCount);
```

## 4- Distribution des Degrés

Exportation des données : Les degrés des nœuds sont exportés dans le fichier degree_distribution.txt.

#### Analyse graphique : 

- Échelle linéaire :
  Tout d'abord,
nous pouvons tracer la distribution des degrés en
échelle linéaire. Cette courbe nous montrera comment 
la probabilité p(k) varie avec le degré k. 
Dans un graphique en échelle linéaire, 
la relation entre k et p(k) peut ne pas être évidente
et pourrait ne pas révéler de structure particulière.

![Distribution des degrés](distribution_degres.png)


- Échelle log-log :
  Lorsque nous traçons la même distribution en échelle
log-log, c'est-à-dire avec les axes 
log(k) et log(p(k)), cela permet de mieux observer les tendances à grande échelle.
nous observons une ligne droite ce qui nous dit que la distribution suit une loi de puissance.

![Distribution des degrés](distribution_degres_loglog.png)


une ligne droite est observée, cela indique une loi de puissance.
- Comparaison avec la distribution de Poisson : Superposer la distribution de Poisson avec ⟨k⟩.

![Dblp](dd_dblp.png)


## 5- Distance moyenne et distribution des distances 


Distance moyenne de notre réseau: 6.700611818856679

```java
double degreeAverage = Toolkit.averageDegree(graph);
double NetworkDistance = Math.log(graph.getNodeCount()) / Math.log(degreeAverage);
System.out.println("Distance moyenne dans notre réseau  : " + NetworkDistance);
```


- L'hypothèse des six degrés de séparation se confirme-t-elle ?

Oui, l'hypothèse des six degrés de séparation est confirmée : la distance moyenne entre les nœuds est proche de 6.

- Est-ce qu'il s'agit d'un réseau petit monde ? 

Le réseau montre des propriétés caractéristiques des réseaux "petit monde" : une distance moyenne faible et un clustering élevé.

- Quelle sera la distance moyenne dans un réseau aléatoire avec les mêmes caractéristiques ?

J'ai calculé la distance moyenne d'un réseau aléatoire de même taille et de même degré moyen que j'ai généré avec randomGenerator de graphstream et ça nous donne à peu prés la même chose 

Distance moyenne du réseau Aléatoire : 6.70193902051403

```java
double degreeAverage = Toolkit.averageDegree(randomGraph);
double NetworkDistance = Math.log(randomGraph.getNodeCount()) / Math.log(degreeAverage);
System.out.println("Distance moyenne du réseau Aléatoire : " + NetworkDistance);
```
Tracer les distributions des distances :


![Distribution des distances](distance_distribution.png)


- Analyse de la courbe des distances moyennes :

Forme en cloche avec une décroissance symétrique de chaque côté.

La courbe montre un pic central autour de 6. Cela suggère que la distance moyenne entre 
les paires de nœuds est proche de cette valeur. Cela soutient l'hypothèse des six degrés de séparation, car la majorité des distances sont à 6 ou moins.

Décroissance rapide : Les distances très petites et très grandes sont rares, tandis que les distances proches de la moyenne sont les plus fréquentes.


- Formulez une hypothèse sur la loi de cette distribution.

On conclut donc que la forme de la distribution est proche d'une loi normale, ce qui est souvent observé dans les réseaux petits mondes.


## 6- Générer deux graphes de même taille et de même degré :

1 - le graphe aléatoire:

Cette méthode génère un graphe aléatoire basé sur les propriétés d'un graphe d'entrée initialGraph, à l'aide d'un générateur de graphes aléatoires de GraphStream. 
Le graphe généré a un nombre total de nœuds fixé (N = 317080) et un degré moyen similaire à celui de initialGraph.




```java
public static Graph createRandomGraph(Graph initialGraph) {

        double averageDegree = Toolkit.averageDegree(initialGraph);

        Generator generator = new RandomGenerator(averageDegree, false);
        Graph graphAlea = new SingleGraph("graphe aléatoire");
        int N = 317080;

        // graphe aléatoire générer de taille N
        generator.addSink(graphAlea);
        generator.begin();
        while (graphAlea.getNodeCount() < N) {
            generator.nextEvents();
        }
        generator.end();
        if (graphAlea.getNodeCount() == N) {
            System.out.println("Graph aléatoire générer !");
        }


        return graphAlea;
    }

```

Les caractéristiques de ce graphe sont : 

Réseau aléatoire :
- Nombre de nœuds : 317080
- Nombre de liens : 1049473
- Degré moyen : 6.61961030960083
- Coefficient de clustering : 4.364833098823207E-5

j'ai aussi calculé les degrés de distribution à l'échelle linéaire et à l'échelle log-log

- Linéaire : 

![Distribution des degrés](degree_distribution_random.png)

- Log-log :

![Distribution des degrés](degree_distribution_loglog_random.png)


2 - Le graphe Barabàsi-Albert:

Cette méthode génère un graphe Barabási-Albert en utilisant le graphe d'entrée initialGraph comme référence. 
Le modèle Barabási-Albert est un modèle de croissance qui suit le principe de l'attachement préférentiel : 
les nouveaux nœuds ont une probabilité plus élevée de se connecter aux nœuds déjà fortement connectés (hubs). 
Ce modèle permet de générer des graphes sans échelle,
où la distribution des degrés suit une loi de puissance.



```java

public static Graph generateBarabasiAlbertGraph(Graph initialGraph) {
  int nodeCount = initialGraph.getNodeCount();
  double averageDegree = Toolkit.averageDegree(initialGraph);

  Graph barabasiGraph = new SingleGraph("Barabasi-Albert Network");
  BarabasiAlbertGenerator generator = new BarabasiAlbertGenerator((int) averageDegree);
  generator.addSink(barabasiGraph);
  generator.begin();
  while (barabasiGraph.getNodeCount() < nodeCount) {
    generator.nextEvents();
  }
  generator.end();
  return barabasiGraph;
}


```


Les caractéristiques de ce graphe sont :

Nombre de nœuds : 317080
Nombre de liens : 1108680
Degré moyen : 6.993061542510986
Coefficient de clustering : 4.235788849759945E-4


j'ai aussi calculé les degrés de distribution à l'échelle linéaire et à l'échelle log-log

- Linéaire :

![Distribution des degrés](degree_distribution_ba.png)

- Log-log :

![Distribution des degrés](degree_distribution_loglog_ba.png)



Comparaison des réseaux générés
En théorie, les deux modèles de réseaux, aléatoire
(Erdős-Rényi) et Barabási-Albert, se distinguent
par leur structure et leur comportement. 

En théorie :

- Réseau aléatoire :

Les liens sont créés de manière totalement aléatoire entre les nœuds.
Le degré moyen suit une distribution de Poisson : 
la plupart des nœuds ont un degré proche de 
la moyenne, et il y a très peu de nœuds avec un
degré beaucoup plus élevé ou plus faible.

Le coefficient de clustering est très faible car les
triangles (groupes de trois nœuds connectés entre 
eux) sont rares dans ce type de réseau.


- Réseau Barabási-Albert :

Ce modèle suit une loi de puissance : quelques 
nœuds, appelés hubs, ont un très grand nombre de 
connexions, tandis que la majorité des nœuds sont 
faiblement connectés.

Le coefficient de clustering est plus élevé que
dans un réseau aléatoire, car les hubs favorisent
la connexion entre plusieurs nœuds, augmentant la
probabilité de former des triangles.



Les résultats expérimentaux correspondent à ces prédictions théoriques comme le démontre le tableau ci-dessous :


| Propriété                 | Réseau Aléatoire            | Réseau Barabási-Albert |
|---------------------------|-----------------------------|-------------------|
| **Nombre de nœuds**       | 317 080                     | 317 080           |
| **Nombre de liens**       | 1 049 907                   | 1 108 082         |
| **Degré moyen**           | 6,6223                      | 6,9893            |
| **Clustering**            | 3.57 × 10⁻⁵                 | 3.82 × 10⁻⁴         |

Le faible clustering du réseau random et le clustering un peu plus élevé du réseau BA sont conformes à ce qu'on attend.
En résumé, ces expériences confirment que le modèle Barabási-Albert est plus adapté pour modéliser des réseaux où les hubs
jouent un rôle important.

## 7- La méthode Copie :
La méthode de copie modifiée sert à générer un réseau en imitant des caractéristiques des réseaux réels, comme la formation 
de triangles et un haut coefficient de clustering.

Comment ça fonctionne ?

- On commence par choisir un nœud au hasard.

À chaque étape :

- Un nouveau nœud est ajouté au réseau.

- Ce nouveau nœud choisit au hasard un nœud existant dans le réseau, qu’on appelle nœud cible.

- Il parcourt les voisins du nœud cible. Pour chaque voisin, il a une probabilité p (par exemple, p=0,5) de se connecter à ce voisin.

- À la fin, il se connecte obligatoirement au nœud cible.

Pourquoi c'est intéressant ?

La probabilité p permet de créer des connexions locales, ce qui augmente le coefficient de clustering.

ATTENTION : Le nouveau nœud ne se connecte pas à tous les voisins du nœud cible, mais seulement à certains d’entre eux,
en fonction de la probabilité p.
Cette méthode garde le réseau connexe grâce à la connexion obligatoire au nœud cible.

Voici comment je m'y suis prise :

```java

public static Graph genererGrapheCopie(int nombreNoeuds, double probabilitéCopie) {
Graph grapheCopie = new SingleGraph("GrapheCopie");
Random aleatoire = new Random();

        // Ajouter un premier nœud pour démarrer le réseau
        grapheCopie.addNode("0");

        for (int i = 1; i < nombreNoeuds; i++) {
            Node nouveauNoeud = grapheCopie.addNode(String.valueOf(i));

            // Choisir un nœud aléatoire existant
            Node noeudCible = grapheCopie.getNode(aleatoire.nextInt(grapheCopie.getNodeCount()));

            // Parcourir les voisins de noeudCible
            noeudCible.edges().forEach(edge -> {
                if (edge != null) { // Vérifier que l'arête n'est pas null
                    Node voisin = edge.getOpposite(noeudCible);

                    // Connecter au voisin avec probabilité p
                    String edgeIdVoisin = nouveauNoeud.getId() + "-" + voisin.getId();
                    if (aleatoire.nextDouble() < probabilitéCopie && grapheCopie.getEdge(edgeIdVoisin) == null) {
                        grapheCopie.addEdge(edgeIdVoisin, nouveauNoeud, voisin);
                    }
                }
            });

            // Connecter le nouveau nœud au nœud cible
            String edgeIdCible = nouveauNoeud.getId() + "-" + noeudCible.getId();
            if (grapheCopie.getEdge(edgeIdCible) == null) {
                grapheCopie.addEdge(edgeIdCible, nouveauNoeud, noeudCible);
            }
        }

        return grapheCopie;
    }


```
Voici les résultats après éxecution du code :

- Nombre de nœuds : 317080
- Nombre de liens : 3392116
- Degré moyen : 21.395963668823242
- Coefficient de clustering : 0.44452828185775123

On remarque bien que le degré moyen est très élevé, mais aussi le coeff de clustring.





# TP 2 :

## 1 - Taux de propagation et seuil épidémique du réseau ainsi que le seuil théorique d'un réseau aléatoire du même degré moyen :

Avant de commencer, il faut savoir que ce modèle est un SIS (Susceptible-Infected-Susceptible)
##### Dans un modèle SIS:

chaque individu de la population peut être dans l’un des deux états suivants :

- Susceptible (S) :
L'individu est en bonne santé mais peut être infecté.
- Infecté (I) :
L'individu est malade et peut transmettre l'infection.

##### Dynamique des transitions
- Un individu susceptible (S) peut devenir infecté (I) après un contact avec une personne infectée, avec une probabilité appelée taux d'infection (β).
- Un individu infecté (I) peut se rétablir et redevenir susceptible (S) avec une probabilité appelée taux de récupération (μ).

La principale caractéristique du modèle SIS est que les individus infectés ne développent pas d'immunité après récupération, ce qui signifie qu'ils peuvent être réinfectés.


- Taux de propagation :

###### τ = β/μ 

avec β = 1 (une personne est infécté a partir du moment où elle reçoit un mail)

et μ = 0.5 ( il mettent à jour leurs anti-virus 2 fois par mois donc 2 semaines sur 4)


ce qui nous donne un taux de propagation (τ) : 2.0 que j'ai calculé comme suit :


```java
double infectionProbability = 1.0; // β = 1
double recoveryProbability = 0.5; // μ = 0.5

        double tau = infectionRate / recoveryRate;         // Taux de propagation
```

- Seuil épidémique :

###### c = < k > / <k^2>

avec <k> : degré moyen (le nombre moyen de connexions par nœud)

et <k^2>: moyenne des carrés des degrés des nœuds.

ce qui nous donne un seuil épidémique réel (c_réel) de 0.04598472436222584 que j'ai calculé comme suit :


```java
double cReal = avgDegree / avgDegreeSquared;
```
```java

private static double calculateSquaredAverageDegree(Graph graph) {
double totalDegreeSquared = 0;
for (Node node : graph) {
totalDegreeSquared += Math.pow(node.getDegree(), 2); // Somme des carrés des degrés
}
return totalDegreeSquared / graph.getNodeCount(); // Moyenne des carrés des degrés
}
```

enfin, le seuil théorique : 

```java
double cTheoretical = 1.0 / (avgDegree + 1);       // Seuil théorique pour un réseau aléatoire avec normalisation
```
ce qui nous donne un seuil théorique de 0.13119762993051035.

on constate que la maladie persiste La maladie persiste dans le réseau réel (τ > c_réel) et que le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique).

## 2 - Simulation des 3 scénario :

Voici les paramètres de ma méthode de simulation : il y'en a 6 :

- Graph graph : Le graphe
- double infectionRate : La probabilité qu'un nœud infecté transmette la maladie à un voisin susceptible.
- double recoveryRate : La probabilité qu'un nœud infecté se rétablisse et redevienne susceptible.
- int days : Le nombre total de jours pendant lesquels la simulation est exécutée.
- double immunizationFraction : La fraction de nœuds ou voisins à immuniser avant le début de la simulation.
- boolean randomImmunization : Détermine la stratégie d'immunisation :

true : Immunisation aléatoire.

false : Immunisation sélective (immuniser un voisin d'un nœud sélectionné).

Cette partie là concerne les deux scénario où il y'a des gens à immuniser (scénario 2 et 3)
ceci est assuré grâce au premier if, et le deuxième if nous permet de savoir si c'est une random immunisation donc le scénario 2 (on convint 50% des gens à mettre à jour leurs anti-virus) où la condition nous retournera true car c'est un boolean 
ou non et on passera au else donc le scénario 3 (on convint 50% des gens à convaincre un de leurs voisins).

```java
// Immunization
        if (immunizationFraction > 0) {
            int immunizedCount = (int) (immunizationFraction * graph.getNodeCount());
            if (randomImmunization) {
                // Immunisation aléatoire : immuniser des nœuds directement
                for (int i = 0; i < immunizedCount; i++) {
                    Node node = graph.getNode(random.nextInt(graph.getNodeCount()));
                    node.setAttribute("immune", true);
                }
            } else {
                // Immunisation sélective : immuniser un voisin pour 50% des nœuds existants
                List<Node> nodes = new ArrayList<>( graph.nodes().toList());

                // Calculer le nombre de nœuds à immuniser (50% des nœuds existants)
                int nodesToImmunize = (int) (immunizationFraction * nodes.size());

                // Mélanger les nœuds pour garantir une sélection aléatoire
                Collections.shuffle(nodes, random);

                // Sélectionner les premiers `nodesToImmunize` nœuds et immuniser un voisin pour chacun
                for (int i = 0; i < nodesToImmunize; i++) {
                    Node node = nodes.get(i);

                    // Vérifier que le nœud a des voisins
                    if (node.getDegree() > 0) {
                        // Prendre un voisin aléatoire
                        List<Node> neighbors = node.neighborNodes().toList();
                        Node neighbor = neighbors.get(random.nextInt(neighbors.size()));

                        // Immuniser ce voisin
                        neighbor.setAttribute("immune", true);
                    }
                }

            }

        }
```

viens maintenant la simulation (c'est un peu là ou tout se déroule y compris le scénario 1)

On commence par infecter un patient qu'on appellera patient 0.

- infectedCount : Nombre de nœuds infectés au cours de la journée actuelle.
- totalNonImmune : Nombre total de nœuds non immunisés dans le graphe 
(c'est-à-dire les nœuds susceptibles ou infectés).

- Exclusion des nœuds immunisés : Les nœuds avec l'attribut immune ne participent pas à la propagation.

###### Propagation (S→I) :
- Les nœuds infectés propagent l'infection à leurs voisins susceptibles avec une probabilité définie par infectionRate.
- Les nœuds susceptibles infectés reçoivent un état futur "infected" stocké dans nextState.
###### Récupération (I→S) :
- Les nœuds infectés peuvent récupérer avec une probabilité définie par recoveryRate et sont marqués comme "susceptible" dans nextState.


On fait ensuite une mise à jour des états des nœuds, Les changements d’état sont appliqués après chaque jour.

Résultats : La fraction de nœuds infectés est calculée chaque jour et retournée à la fin.

```java
// Infect patient zero
Node patientZero = graph.getNode(new Random().nextInt(graph.getNodeCount()));
        patientZero.setAttribute("state", "infected");


// Simulation
for (int day = 0; day < days; day++) {
int infectedCount = 0;
int totalNonImmune = 0;

            for (Node node : graph) {
                if (!node.hasAttribute("immune")) {
                    totalNonImmune++;
                    if (node.getAttribute("state").equals("infected")) {
                        infectedCount++;
                        for (Node neighbor : node.neighborNodes().toList()) {
                            if (!neighbor.hasAttribute("immune") && neighbor.getAttribute("state").equals("susceptible") && random.nextDouble() < infectionRate) {
                                neighbor.setAttribute("nextState", "infected");
                            }
                        }
                        if (random.nextDouble() < recoveryRate) {
                            node.setAttribute("nextState", "susceptible");
                        }
                    }
                }
            }
            
            // mise à jour de l'état des noeuds
            for (Node node : graph) {
                if (node.hasAttribute("nextState")) {
                    node.setAttribute("state", node.getAttribute("nextState"));
                    node.removeAttribute("nextState");
                }
            } 
            infectedFractions[day] = (double) infectedCount / totalNonImmune;
        }

                return infectedFractions;
    }
```
#### on obtient ces courbes qui montrent bien l'efficacité de l'immunisation séléctive.

![propagation simulation](propagationsimulation.png)


## 3 - Le degré moyen des groupes 0 et 1 :

Il faut savoir que le groupe 0 sont les nœuds choisis aléatoirement et le groupe un de leurs voisins.

Resumé :
- Groupe 0 => 50% des nœuds [non immunisé]
- Groupe 1 => 1 voisin de ces nœuds [immunisés]

voici comment j'ai procédé :

```java
// Appliquer une immunisation aléatoire (immuniser 50 % des nœuds)
        Set<Node> immune = new HashSet<>();
        Random random = new Random();
        int immuneCount = (int) (0.5 * graph.getNodeCount()); // Immuniser 50 % des nœuds
        List<Node> nodes = new ArrayList<>(graph.nodes().toList());
        Collections.shuffle(nodes, random);
        for (int i = 0; i < immuneCount; i++) {
            Node node = nodes.get(i);
            node.setAttribute("immune", true); // Marquer comme immunisé
            immune.add(node);
        }

        // Groupes
        Set<Node> group0 = new HashSet<>(); // Groupe 0 : 50 % des nœuds non immunisés
        Set<Node> group1 = new HashSet<>(); // Groupe 1 : Un voisin immunisé de chaque nœud du Groupe 0

        // Sélectionner 50 % des nœuds non immunisés pour le Groupe 0
        List<Node> nonImmuneNodes = new ArrayList<>();
        for (Node node : graph) {
            if (!immune.contains(node)) { // Nœuds non immunisés
                nonImmuneNodes.add(node);
            }
        }
        Collections.shuffle(nonImmuneNodes, random); // Mélanger les nœuds non immunisés
        int targetCount = (int) (0.5 * nonImmuneNodes.size()); // 50 % des nœuds non immunisés
        for (int i = 0; i < targetCount; i++) {
            group0.add(nonImmuneNodes.get(i)); // Ajouter au groupe 0
        }

        // Pour chaque nœud du Groupe 0, ajouter un voisin immunisé au Groupe 1
        for (Node node : group0) {
            List<Node> neighbors = node.neighborNodes().toList();
            for (Node neighbor : neighbors) {
                if (immune.contains(neighbor)) { // Vérifier si le voisin est immunisé
                    group1.add(neighbor); // Ajouter un seul voisin immunisé au groupe 1
                    break; // Sortir de la boucle après avoir trouvé un voisin immunisé
                }
            }
        }

        // Calcul du degré moyen pour le Groupe 0 (non immunisé)
        double totalDegreeGroup0 = 0;
        for (Node node : group0) {
            totalDegreeGroup0 += node.getDegree();
        }
        double averageDegreeGroup0 = group0.isEmpty() ? 0 : totalDegreeGroup0 / group0.size();
        System.out.printf("Degré moyen (Groupe 0 - Non immunisé) : %.9f%n", averageDegreeGroup0);

        // Calcul du degré moyen pour le Groupe 1 (voisins immunisés)
        double totalDegreeGroup1 = 0;
        for (Node node : group1) {
            totalDegreeGroup1 += node.getDegree();
        }
        double averageDegreeGroup1 = group1.isEmpty() ? 0 : totalDegreeGroup1 / group1.size();
        System.out.printf("Degré moyen (Groupe 1 - Voisins immunisés) : %.9f%n", averageDegreeGroup1);
```

Immunisation aléatoire :

50 % des nœuds du graphe sont sélectionnés de manière aléatoire pour être immunisés.

Ces nœuds sont marqués avec l'attribut "immune" et ajoutés à un ensemble immune.


###### Groupe 0 (non immunisé) :

les nœuds non immunisés forment le groupe 0.

Ces nœuds représentent une population aléatoire non immunisée dans le graphe.

###### Groupe 1 (voisins immunisés) :

Pour chaque nœud du Groupe 0, on cherche un voisin immunisé (parmi ceux marqués "immune").
Ce voisin immunisé est ajouté au Groupe 1.

Chaque nœud du Groupe 0 est associé à un seul voisin immunisé.


Voici les résultats : 

- Degré moyen (Groupe 0 - Non immunisé) : 6,601652580
- Degré moyen (Groupe 1 - Voisins immunisés) : 14,067850086

La différence entre les degrés moyens reflète l’efficacité de l’immunisation sélective :

###### Immunisation aléatoire : 
Le degré moyen est similaire au degré moyen global du graphe.
###### Immunisation sélective :
Le degré moyen est nettement plus élevé, car les voisins des hubs 
(nœuds critiques) sont ciblés, ce qui fragmente davantage le réseau.