Vous êtes ici : Accueil » Kiosque » Annonce

Identification

Identifiant: 
Mot de passe : 

Mot de passe oublié ?
Détails d'identification oubliés ?

Annonce

14 novembre 2017

Stage M2 - Analyse spectrale des réseaux complexes pour une meilleure information de centralité


Catégorie : Stagiaire


Mots clés : Réseaux Complexes, Centralités, Matrice d’Adjacence/Laplacienne, Distributions de Marchenko-Pastur/Tracy-Widom, valeurs propres/vecteurspropres

Contexte : Les réseaux complexes permettent la modélisation

  • des réseaux sociaux
  • des diffusions épidémiques
  • des dépendances entre packages informatiques, etc.

L’importance d’un nœud, la centralité, peut être identifié par recherche des valeurs propres des matrices d’adjacence ou Laplacienne.

Problématique : On peut modéliser les réseaux complexes par des graphes aléatoires, lorsque la dimension des réseaux est grande, l’utilisation de la théorie des matrices aléatoires de grande dimensions est alors bien adaptée.

Il s’agit dans ce stage d’appliquer cette théorie pour une meilleur caractérisation de la centralité, soit une meilleure estimation des valeurs propres de certaines matrices.

 

L’importance relative d’un nœud dans un réseau complexe est évaluée par les mesures de centralité. Différentes mesures ont été proposées dans la littérature [1]. Citons parmi les plus courantes la centralité des degrés, la centralité d’intermédiarité, la centralité de proximité ou encore la centralité des vecteurs propres. Ces centralités diffèrent par la façon dont elles sont calculées. Ainsi, la centralité des degrés correspond au nombre de liens d’un nœud, les centralités de proximité (Closeness centrality) et d’intermédiarité (Betweenness centrality) sont basées sur les plus courts chemins, la centralité des vecteurs propres (Eigenvector centrality) est calculée à partir de la matrice d’adjacence du réseau.

Les centralités permettent d’exprimer différents aspects du concept d’importance. Elles sont largement utilisées dans l’analyse des grands graphes de terrain tels que les réseaux sociaux pour identifier les personnes influentes, en épidémiologie pour l’identification des personnes les plus susceptibles de transmettre une maladie, en informatique pour l’identification d’éléments centraux dans un système d’information [2]. Certaines applications plus récentes ont vu le jour dans le domaine des chaînes d’approvisionnement [3] pour identifier les acteurs clés. Dans ces différents domaines d’application, nous avons à faire à des réseaux de taille de plus en plus importante. Dans ce cas, le calcul des centralités peut poser un certain nombre de problèmes [4].

Dans ce travail, nous proposons d’utiliser les représentations matricielles des réseaux afin de pouvoir étudier leurs topologies et la centralité des nœuds au travers de l’analyse des valeurs propres/vecteurs propres des matrices d’adjacence ou Laplacienne. De nombreux travaux montrent en effet qu’un réseau complexe peut se représenter par un large graphe aléatoire [5,8,9]. Les matrices d’adjacence et Laplacienne sont donc des matrices dont les coefficients sont eux-mêmes aléatoires. L’étude des centralités par analyse des valeurs propres revient alors à connaître dans un premier temps la distribution théorique des valeurs propres de ces matrices [6,10,11] sous l’hypothèse de grandes dimensions. Cette hypothèse essentielle permet de revisiter les outils associés aux matrices aléatoires en étudiant un régime asymptotique (doublement asymptotique) où le nombre de lignes et de colonnes des matrices d’adjacence ou Laplacienne augmentent avec un ratio constant. La connaissance plus précise des distributions des valeurs propres/vecteurs propres permet ensuite d’envisager de corriger l’estimation de ces derniers et ainsi pouvoir mieux caractériser les centralités du réseau.

Références bibliographiques

[1] Lü & al., Vital nodes identification in complex networks, Physics Reports, Vol 650, Pgs 1-64, 2016

[2] Muchou Wang, Weifeng Pan, A Comparative Study of Network Centrality Metrics in Identifying Key Classes in Software, Journal of Computational Information Systems 8: 24, 2012

[3] Yusoon Kim, Thomas Y. Choi, Tingting Yan, Kevin Dooley, Structural Investigation of Supply Networks- A Social Network Analysis Approach, Journal of Operations Management, 29(3), 194-211, 2011

[4] U Kang, Spiros Papadimitriou, Jimeng Sun, Hanghang Tong, Centralities in Large Networks: Algorithms and Observations, Proceedings of the Eleventh SIAM International Conference on Data Mining, SDM 2011, April 28- 30, 2011, Mesa, Arizona, USA

[5] P. Erdös, A. Rényi, On random graphs, I, Publicationes Mathematicae (Debrecen), Vol. 6 (1959), pp. 290-297

[6] Farkas, Deré nyi, Barabá si, and Vicsek, Spectra of “real-world” graphs: Beyond the semicircle law, Physical Review E 64, 026704, 2001.

[7] S.P. Borgatti, M.G. Everett, "A Graph-theoretic perspective on centrality", Social Networks, Volume 28, Issue 4, October 2006, Pages 466-484

[8] Jayendra N. Bandyopadhyay, and Sarika Jalan, Universality in complex networks: Random matrix analysis, Phys. Rev. E 76, 026109, 2007

[9] Piet van Mieghem, Graph spectra for complex networks, Cambridge University Press, 2011

[10] B. Ye, K. Zuo and J. Jia, Random matrix analysis of spectral properties in directed complex networks, The 26th Chinese Control and Decision Conference, Changsha, 2014, pp. 616-620.

[11] B Ding and T Jiang, spectral distributions of adjacency and laplacian matrices of random graphs, The Annals of Applied Probability , 2010, Vol. 20, No. 6, 2086–2117

Contact

guillaume.bouleux@insa-lyon.fr, chantal.bonnercherifi@univ-lyon2.fr

 

Dans cette rubrique

(c) GdR 720 ISIS - CNRS - 2011-2018.