The analysis of the structural properties and the spanning trees entropy of complex networks

Abstract

L’analyse des r´eseaux complexes a ´et´e largement stimul´ee par les ressources de donn´ees massives et leur ´etude a ´et´e initi´ee pour une volont´e de comprendre le comportement de divers syst`emes r´eels. Ces r´eseaux complexes sont le r´esultat de toutes les interactions entre les composants physiques et logiques des r´eseaux. Pour comprendre leur m´ecanisme et leur comportement, de nombreuses propri´et´es structurelles sont utilis´ees, telles que la distance moyenne, le diam`etre, le coefficient de clustering, la distribution des degr´es et le degr´e moyen, etc. Ces caract´eristiques d´efinissent trois mod`eles de r´eseaux complexes notamment les r´eseaux sans ´echelle, les r´eseaux petit monde et les r´eseaux al´eatoires. Ces trois mod`eles affichent un comportement riche, observ´e dans une grande vari´et´e de syst`emes r´eels, y compris Internet, le World Wide Web, les r´eseaux ´electriques, les r´eseaux de neurones c´er´ebraux et les r´eseaux sociaux. Pour caract´eriser et analyser leur structure, la th´eorie des graphes dispose d’un outil puissant, nomm´e le nombre d’arbres couvrants d’un r´eseau, ´egalement appel´e la complexit´e d’un r´eseau. Il est d´efini comme le nombre total des sous-graphes connexes et sans cycles contenant tous les sommets du r´eseau avec le plus petit nombre possible d’ar^etes. L’objectif principal de ce travail est le calcul du nombre d’arbres couvrants d’un r´eseau, qui permet de pr´edire sa fiabilit´e et sa robustesse. En effet, le calcul de ce nombre reste un d´efi, en particulier pour les r´eseaux complexes. Nous nous sommes int´eress´es `a la recherche des m´ethodes efficaces pour obtenir la formule exacte du nombre d’arbres couvrants pour les r´eseaux complexes. Le premier but de cette ´etude est de cr´eer de nouveaux mod`eles ´evoluant de mani`ere dynamique dans le temps pour chaque cat´egorie de r´eseaux complexes. Ensuite, calculer leurs propri´et´es structurelles pertinentes pour comprendre leurs m´ecanismes et leurs comportements. De plus, ´evaluer leur complexit´e en utilisant et am´eliorant des m´ethodes combinatoires et g´eom´etriques. Finalement, comme application, nous calculons leur entropie afin de quantifier leur robustesse et la comparer avec d’autres r´eseaux ayant le m^eme degr´e moyen.