Approche D'optimisation Pour Le Suivi De L'évolution De La Structure Communautaire Des Réseaux Dynamiques

Résumé: L'évolution rapide des réseaux sociaux au cours des dernières années a retenu l'attention de plusieurs chercheurs en quête de solutions adéquates pour la gestion de ces réseaux. À cet effet, plusieurs algorithmes efficaces dédiés au suivi de la structure communautaire et la détection de communautés ont été proposés. Ces algorithmes ont été conçus pour les réseaux dynamiques évoluant par l'ajout et / ou la suppression de nœuds et d'arêtes. Il existe cependant, également des réseaux évoluant uniquement par l'ajout de nœud et d'arêtes (liens), appelés réseaux incrémentiels. Ces derniers sont un cas particulier des réseaux dynamiques qui augmentent considérablement en taille. 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.

Publié dans la revue: