La matrice de modularité Q, que vous allez devoir calculer, est une matrice symétrique très utilisée dans l’analyse de réseaux ou graphes, par exemple les réseaux sociaux. Elle se calcule à partir de la matrice n x n d’adjacence du réseau, A, qui contient les interactions / relations entre paires d’individus pris deux à deux (n individus au total). Par exemple, pour le réseau Facebook, l’élément \([A]_{ij} = a_{ij}\) de la matrice d’adjacence A contient +1 si l’individu numéro i est ami avec j et 0 sinon (ils sont en relation d’amitié ou pas).

Dans d’autres réseaux sociaux, cette matrice d’adjacence pourrait, par exemple, contenir le nombre de fois (fréquence) que la personne i est allée au cinéma en compagnie de le personne j durant l’année, ou toute autre forme d’interaction / relation entre paires d’individus. Donc, dans ce cas, plus la valeur \(a_{ij}\) est élevée, plus les deux personnes sont considérées comme « proches », socialement parlant, car elles interagissent beaucoup. Pour cette question d’examen, nous supposerons que la matrice d’adjacence, qui est connue, est carrée, symétrique, à diagonale nulle (pas d’auto-interaction), et contient uniquement des valeurs entières non-négatives.

La matrice de modularité Q se calcule à partir de la matrice d’adjacence et contient la fréquence d’interaction entre deux individus moins la fréquence attendue si les interactions se faisaient « au hasard » (elle ressemble donc au Chi-carré). Mais ce qui nous importe ici, c’est la forme de cette matrice : l’élément \([Q]_{ij} = q_{ij}\) de la matrice de modularité s’obtient à partir de la matrice d’adjacence à l’aide de la formule

\(q_{ij}=a_{ij}-\frac{d_id_j}{a_{**}}\)

où les \(d_i\) sont les « degrés » des individus, à savoir \(d_i\) est la fréquence totale d’interactions de l’individu i avec tous les autres individus. Celui-ci se calcule par \(d_i=a_{i*}=\sum^{n}_{j=1}a_{ij}\) et \(d_j=a_{*j}=\sum^{n}_{i=1}a_{ij}\) où le point (*) signifie donc la sommation sur l'indice correspondant. Par ailleurs, \(a_{**}=\sum^{n}_{i=1}\sum^{n}_{j=1}a_{ij}\). Dans le code, vous devez donc calculer le vecteur de degrés d et ensuite la matrice de modularité Q par la formule ci-dessus.

Exemple : Prenons un petit exemple. Voici une matrice d’adjacence d’un mini-réseau comprenant seulement trois personnes, et sa matrice de modularité correspondante. On a par exemple observé 2 interactions entre les individus 1 et 3.

et le vecteur de degrés est \(d = [3, 4, 5]^T\).

Nous vous demandons donc de calculer cette matrice de modularité Q à partir de la matrice d’adjacence A en python dans la fonction calculModularite. Ce code doit pouvoir gérer toute matrice d’adjacence carrée de taille n x n, symétrique, et contenant uniquement des valeurs non-négatives. Vous ne devez pas vérifier ces propriétés ; elle sont supposées avoir été vérifiées auparavant.

N’hésitez pas à écrire une fonction intermédiaire qui calcule les degrés des individus d et que vous utiliserez dans calculModularite.

Signature de la fonction : def calculModularite(A)