Approche d'optimisation pour le suivi de l'évolution de la structure communautaire des réseaux dynamiques

Voir Plus Voir Moins

Afficher le Résumé

Dans cette thèse, nous présentons une nouvelle approche pour le suivi de l'évolution de la structure communautaire dans les réseaux incrémentiels. L'approche en question est basée sur la densité du réseau et la double optimisation de celle-ci. Le premier niveau d'optimisation consiste en l'intégration d'un nouveau nœud avec ses liens à la communauté appropriée maximisant la somme des différences entre la densité interne et la densité externe de toutes les communautés infectées. Le second niveau d'optimisation vise à améliorer davantage le score de la densité du réseau par des opérations sur les communautés infectées. Cette double optimisation permet de réduire le problème de limite de résolution dont souffre la majorité des algorithmes d'optimisation. Rappelons que ce problème de limite de la résolution est induit par l'optimisation de la modularité. L'algorithme présenté est incrémental dans le sens où il utilise la structure communautaire précédente pour identifier la structure courante. Pour la validation, nous avons effectué des tests sur des réseaux sociaux dynamiques du monde réel. Nos résultats expérimentaux sont comparés aux résultats obtenus par des algorithmes dédiés aux réseaux statiques ainsi que des résultats obtenus avec des algorithmes conçus pour des réseaux dynamiques. Ces tests montrent que notre algorithme donne de bonnes structures communautaires avec une complexité relativement faible.