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⟩.
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
## 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 ?
Analyse de la courbe
Distance moyenne :
- La courbe atteint son pic 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.
Est-ce qu'il s'agit d'un réseau petit monde ?
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 ?
Tracez également la distribution des distances.
Formulez une hypothèse sur la loi de cette distribution.
Génération du réseau Barabási-Albert...
Réseau Barabási-Albert :
Nombre de nœuds : 317080
Nombre de liens : 1108680
Degré moyen : 6.993061542510986
Coefficient de clustering : 4.235788849759945E-4