Résumé technique : Qu'est-ce qui rend l'illusion de la majorité facile à détecter ?

Définition du problème

L'article étudie la complexité computationnelle de la détection de l'illusion de la majorité dans les réseaux sociaux. Formellement, un réseau social est modélisé par un graphe non orienté $G = (N, E)$ où les sommets représentent des agents et les arêtes représentent des relations sociales. Les agents se voient attribuer une étiquette binaire (par exemple, « rouge » ou « bleu »). Un agent est sous l'effet d'une illusion de la majorité s'il perçoit la minorité d'étiquettes comme étant dominante au sein de son voisinage local.

Le problème de décision central est le problème de l'illusion de la majorité $q$ : Étant donné un graphe $G$ et un rationnel $q \in [0, 1]$, existe-t-il un étiquetage binaire des agents tel que la couleur majoritaire soit une étiquette spécifique (disons, bleue), mais qu'au moins une fraction $q$ des agents ait une majorité stricte de voisins avec l'étiquette minoritaire (rouge) ?

Des travaux antérieurs par Grandi et al. (2025) ont établi que ce problème est NP-complet en général, même pour des classes de graphes restreintes comme les graphes bipartis, les graphes planaires ou les graphes de degré maximum 6. Bien qu'ils aient fourni des algorithmes FPT (Fixed-Parameter Tractable) pour des paramètres tels que le nombre de couverture de sommets et la diversité de voisinage, et qu'ils aient montré que le problème est dans XP pour la largeur de parcours (treewidth), ils ont laissé ouverte la question de savoir quelles restrictions structurelles rendent le problème efficacement soluble (FPT) versus intractable.

Méthodologie

Les auteurs emploient le cadre de la complexité paramétrée pour analyser la tractabilité du problème de l'illusion de la majorité $q$. Ils étudient systématiquement le problème par rapport à divers paramètres structurels de graphes, notamment :

• Intégrité de sommet ($vi(G)$) : La taille minimale d'un ensemble de sommets dont le retrait laisse des composantes de taille bornée.
• Ensemble d'arêtes de retour (Feedback Edge Set - $fes(G)$) et Ensemble de sommets de retour (Feedback Vertex Set - $fvs(G)$) : Le nombre minimal d'arêtes ou de sommets à retirer pour rendre le graphe acyclique.
• Distance aux classes de graphes : Paramètres mesurant la distance en sommets ou en arêtes vers des classes spécifiques telles que les étoiles disjointes, les chemins disjoints et les graphes de clusters (unions disjointes de cliques).
• Profondeur de l'arbre (Treedepth - $td(G)$) et Largeur de parcours (Treewidth - $tw(G)$) : Paramètres structurels standards.

La méthodologie repose sur deux techniques algorithmiques primaires :

1. Programmation Linéaire en N-parties (N-fold ILP) : Utilisée pour prouver les résultats FPT pour des paramètres comme l'intégrité de sommet. Le problème est formulé comme un ILP en N-parties où les contraintes sont séparées en contraintes globales (garantissant la majorité globale et le compte total d'agents sous illusion) et des contraintes locales (garantissant les conditions de voisinage local pour des composantes spécifiques).
2. Programmation Dynamique (DP) : Utilisée pour les structures de type arbre (arbres, chemins) et les graphes proches de ces structures. Pour les arbres, les auteurs conçoivent un algorithme en temps polynomial pour un problème connexe nommé « Max List Majority Illusion », qui sert de sous-routine pour les algorithmes FPT basés sur les ensembles d'arêtes de retour.

Pour les résultats de dureté, les auteurs fournissent des réductions paramétrées à partir de problèmes connus étant W[1]-hard, spécifiquement le Somme de sous-ensembles multidimensionnelle (et sa variante Halfset).

Contributions et résultats clés

1. Tractabilité paramétrée (FPT)

L'article établit des algorithmes FPT pour plusieurs nouvelles paramétrisations :

• Intégrité de sommet ($vi(G)$) : Les auteurs prouvent que l'illusion de la majorité $q$ est dans FPT lorsqu'elle est paramétrée par l'intégrité de sommet. L'algorithme devine l'étiquetage de l'ensemble « séparateur » $M$ et utilise un N-fold ILP pour étendre cet étiquetage aux composantes restantes de petite taille. Ce résultat permet également d'améliorer le temps d'exécution pour le nombre de couverture de sommets ($vc(G)$), réduisant la complexité de double exponentielle ($2^{2^{O(vc)}}$) à simple exponentielle ($2^{O(vc^2 \log vc)}$).
• Ensemble d'arêtes de retour ($fes(G)$) : Le problème est montré comme étant dans FPT lorsqu'il est paramétré par le nombre d'arêtes de retour. L'approche consiste à deviner l'étiquetage des sommets incidents aux arêtes de retour, transformant le graphe en un arbre avec des « gadgets » (feuilles pendantes), puis à résoudre l'instance résultante à l'aide d'un algorithme de programmation dynamique en temps polynomial sur les arbres.
• Nombre de suppression d'arêtes de cluster ($cdn(G)$) : Pour les graphes qui deviennent une union disjointe de cliques après avoir retiré un nombre borné d'arêtes, le problème est dans FPT. L'algorithme devine l'étiquetage des extrémités des arêtes retirées et utilise la programmation dynamique sur les cliques, en tirant parti du fait que le statut des agents au sein d'une clique ne dépend que du nombre d'agents rouges et des connexions externes fixes.

2. W[1]-Dureté et intractabilité

L'article fournit des résultats négatifs forts, montrant que le problème reste difficile même pour des graphes qui sont « proches » de structures simples :

• Distance aux étoiles disjointes ($dds(G)$) : Le problème est W[1]-dur lorsqu'il est paramétré par la distance en sommets aux étoiles disjointes. Ceci est prouvé via une réduction de la Somme de Halfset multidimensionnelle.
• Distance aux chemins disjoints ($ddp(G)$) : De même, le problème est W[1]-dur lorsqu'il est paramétré par la distance en sommets aux chemins disjoints.
• Profondeur de l'arbre ($td(G)$) : Le problème est W[1]-dur lorsqu'il est paramétré par la profondeur de l'arbre. Cela résout une question ouverte importante de Grandi et al. (2025), impliquant qu'un algorithme FPT pour la largeur de parcours (qui est bornée par la profondeur de l'arbre) est peu probable sous les hypothèses de complexité standard.
• Distance aux graphes de clusters ($dcg(G)$) : Le problème est dans XP mais W[1]-dur lorsqu'il est paramétré par la distance en sommets aux graphes de clusters. Cela contraste avec le résultat FPT pour la distance en arêtes aux graphes de clusters ($cdn(G)$).

3. Résolubilité en temps polynomial sur des classes spécifiques

Les auteurs fournissent un algorithme en temps linéaire pour les graphes qui sont des unions de chemins disjoints. Ils dérivent une expression en forme close pour le nombre maximum d'agents sous l'illusion de la majorité dans un chemin, montrant que le problème est trivialement soluble sur les chemins et les chemins disjoints.

Signification et conclusion

La principale contribution de l'article est une « carte » complète du paysage de la complexité computationnelle pour le problème de détection de l'illusion de la majorité. Elle clarifie la frontière entre les instances tractables et intractables en identifiant les propriétés structurelles spécifiques qui permettent une détection efficace.

Les auteurs concluent que pour que le problème soit tractable (FPT), le réseau social doit satisfaire l'une des trois conditions suivantes :

1. Il est à une distance en arêtes bornée d'une classe où le problème est soluble en temps polynomial (ex: arbres via l'ensemble d'arêtes de retour, ou graphes de clusters via la suppression d'arêtes de cluster).
2. Il est à une distance en sommets bornée de composantes de taille bornée (ex: via l'intégrité de sommet).
3. Il consiste en un nombre borné de blocs bien structurés (ex: diversité de voisinage bornée).

Les résultats mettent en évidence une dichotomie marquée : alors que le retrait d'un petit nombre d'arêtes pour atteindre une structure simple donne souvent des algorithmes FPT, le retrait d'un petit nombre de sommets pour atteindre la même structure mène souvent à la W[1]-dureté. L'article laisse ouverte la complexité du problème lorsqu'il est paramétré par le nombre de couverture de jumeaux (twin-cover number), notant qu'il se situe entre la distance en sommets aux graphes de clusters (XP) et la distance en arêtes aux graphes de clusters (FPT), et questionne si la structure supplémentaire de jumeaux permet un algorithme FPT.