Sur l'effet du coefficient moyen de clustering sur la prédiction de liens basée sur la topologie dans les graphes sans caractéristiques

La prédiction de liens est un problème fondamental en théorie des graphes, aux applications diverses, notamment dans les systèmes de recommandation, la détection de communautés et l’identification de connexions artificielles. Bien que les méthodes basées sur les caractéristiques atteignent une haute précision, leur dépendance aux attributs des nœuds limite leur applicabilité aux graphes sans attributs. Dans de tels cas, les approches basées sur la structure, telles que les méthodes fondées sur les voisins communs ou les méthodes dépendantes du degré, sont couramment utilisées. Toutefois, l’efficacité de ces méthodes dépend de la densité du graphe : les algorithmes basés sur les voisins communs se comportent bien sur les graphes denses, tandis que les méthodes dépendantes du degré sont plus adaptées aux graphes creux ou de type arbre. Malgré cela, la littérature manque d’un critère clair permettant de distinguer les graphes denses des graphes creux. Ce papier introduit le coefficient moyen de regroupement comme critère d’évaluation de la densité du graphe, afin d’aider au choix des algorithmes de prédiction de liens. Pour pallier le manque de jeux de données disponibles pour l’analyse empirique, nous proposons une nouvelle méthode de génération de graphes basée sur le modèle de Barabasi-Albert, permettant une variation contrôlée de la densité tout en préservant l’hétérogénéité structurelle. À travers des expérimentations approfondies sur des jeux de données synthétiques et réels, nous établissons une frontière empirique pour le coefficient moyen de regroupement, facilitant ainsi le choix de techniques de prédiction de liens efficaces.