Note ABES Characterizing edges in signed and vector-valued graphs Caractérisation des arêtes dans les graphes signés et attribués Graphes signés Graphes attribués 006.31 Apprentissage automatique Apprentissage supervisé (intelligence artificielle) Trolls (internet) Réseaux sociaux (Internet) Partitionnement de graphes Arbres (théorie des graphes) -- Informatique Optimisation convexe 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ù seul 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. We develop methods to efficiently and accurately characterize edges in complex networks. In simple graphs, nodes are connected by a single semantic. For instance, two users are friends in a social networks. Moreover, those connections are typically driven by node similarity, according to homophily. In the previous example, users become friends because of common features. By contrast, complex networks are graphs where every connection has one semantic among k possible ones. Those connections are moreover based on both partial homophily and heterophily of their endpoints. This additional information enable finer analysis of real world graphs. However, it can be expensive to acquire, or is sometimes not known beforehand. We address the problems of inferring edge semantics in various settings. First, we consider graphs where edges have two opposite semantics, and where we observe the label of some edges. These so-called signed graphs are a common way to represent polarized interactions. We propose two learning biases suited for directed and undirected signed graphs respectively. This leads us to design several algorithms leveraging the graph topology to solve a binary classification problem that we call edge sign prediction. Second, we consider graphs with k?> 2 available semantics for edge. In that case of multilayer graphs, we are not provided with any edge label, but instead are given one feature vector for each node. Faced with such an unsupervised problem, we devise a quality criterion expressing how well an edge k-partition and k semantical vectors explains the observed connections. We optimize this goodness of explanation criterion in vectorial and matricial forms. Electronic Thesis or Dissertation Text en PDF 6317711 text/html https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2018/50376-2018-Le_Falher.pdf https://theses.fr/2018LILUI013/abes Le Falher Géraud Le Fahler 1990-07-18 FR 231713983 https://theses.fr/2018LILUI013 2018LILUI013 https://doi.org/10.70675/909bbe94z5fa8z4ba3z80bbzc56545575d65 2018-04-16 Informatique et applications Université de Lille (2018-2021) 223446556 Doctorat Docteur es non oui Tommasi Marc MADS_DIRECTEUR_DE_THESE_1 121846385 Vitale Fabio MADS_DIRECTEUR_DE_THESE_2 231713304 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 18388695X Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_2 185432247 ddc:000 Tommasi Marc Vitale Fabio École doctorale Sciences pour l'Ingénieur (Lille) Centre de recherche en informatique, signal et automatique de Lille (CRIStAL) Institut national de recherche en informatique et en automatique (France). Centre de recherche Lille - Nord Europe PDF 6317711