Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 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.
## 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.
- É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.
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⟩.
## 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);
```
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.
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
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 :
- 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.
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
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;
}
```
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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
- Linéaire :
- Log-log :
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
j'ai aussi calculé les degrés de distribution à l'échelle linéaire et à l'échelle log-log
- Linéaire :
- Log-log :
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
Scenario 1: No Control
Scenario 2: Random Immunization
Scenario 3: Selective Immunization
Les résultats ont été sauvegardés dans les fichiers pour Gnuplot.
Degré moyen (Groupe 0 - Nœuds sélectionnés aléatoirement) : 0,000000000
Degré moyen (Groupe 1 - Voisins immunisés) : 0,000000000
Taux de propagation (τ) : 2.0
Seuil épidémique réel (c_réel) : 0.04598472436222584
Seuil épidémique théorique (c_théorique) : 0.13119762993051035
La maladie persiste dans le réseau réel (τ > c_réel).
Le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique).
Analyse après immunisation aléatoire :
Taux de propagation (τ) : 2.0
Seuil épidémique réel (c_réel) : 0.08901721301662724
Seuil épidémique théorique (c_théorique) : 0.23306206408564414
La maladie persiste dans le réseau réel (τ > c_réel).
Le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique).
Analyse après immunisation sélective :
Taux de propagation (τ) : 2.0
Seuil épidémique réel (c_réel) : 0.5542146555509032
Seuil épidémique théorique (c_théorique) : 0.8352912559058712
La maladie persiste dans le réseau réel (τ > c_réel).
Le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique).