Nous proposons des méthodes pour caractériser efficacement les arêtes au sein de réseaux complexes. Dans les graphes simples, les nœuds sont liés par une sémantique unique, tels deux utilisateurs amis dans un réseau social. De plus, ces arêtes sont guidées par la similarité entre les nœuds (homophilie). Ainsi, les membres deviennent amis à cause de caractéristiques communes. En revanche, les réseaux complexes sont des graphes où chaque arête possède une sémantique parmi k possibles. Ces arêtes sont de plus basées à la fois sur une homophilie et une hétérophilie partielle. Cette information supplémentaire permet une analyse plus fine de graphes issus d’applications réelles. Cependant, elle peut être coûteuse à acquérir, ou même être indisponible. Nous abordons donc le problème d’inférer la sémantique des arêtes. Nous considérons d'abord les graphes dont les arêtes ont deux sémantiques opposées, et où seule une fraction des étiquettes est visibles. Ces «graphes signés» sont une façon élégante de représenter des interactions polarisées. Nous proposons deux biais d’apprentissage, adaptés respectivement aux graphes signés dirigés ou non, et plusieurs algorithmes utilisant la topologie du graphe pour résoudre un problème de classification binaire. Ensuite, nous traitons les graphes avec k > 2 sémantiques possibles. Dans ce cas, nous ne recevons pas d’étiquette d’arêtes, mais plutôt un vecteur de caractéristiques pour chaque nœud. Face à ce problème non supervisé, nous concevons un critère de qualité exprimant dans quelle mesure une k-partition des arêtes et k vecteurs sémantiques expliquent les arêtes observées. Nous optimisons ce critère sous forme vectorielle et matricielle.
- Directeur de thèse : Marc Tommasi - Rapporteurs : Alessandro Provetti, Liva Ralaivola - Examinateurs : Elisa Fromont, Sophie Tison
Thèse de l'équipe MAGNET soutenue le 16/04/2018
français
English