During the last years, we have observed a progressive and continuous expansion of human-centered mobile wireless networks. The advent of these networks has encouraged the researchers to think about new solutions in order to ensure efficient evaluation and design of communication protocols. In fact, these networks are faced to several constraints as the lack of infrastructure, the dynamic topology, the limited resources and the deficient quality of service and security. We have been interested in the dynamicity of the network and in particular in human mobility. The human mobility has been widely studied in order to extract its intrinsic properties and to harness them to propose more accurate approaches. Among the prominent properties depicted in the literature, we have been specially attracted by the impact of the social interactions on the human mobility and consequently on the structure of the network. To grasp structural information of such networks, many metrics and techniques have been borrowed from the Social Network Analysis (SNA). The SNA can be seen as another network measurement task which extracts structural information of the network and provides useful feedback for communication protocols. In this context, the SNA has been extensively used to perform link prediction in social networks relying on their structural properties. Motivated by the importance of social ties in human-centered mobile wireless networks and by the possibilities that are brought by SNA to perform link prediction, we are interested by designing the first link prediction framework adapted for mobile wireless networks as Mobile Ad-hoc Networks (MANETs) and Delay/Disruption Tolerant Networks (DTN). Our proposal tracks the evolution of the network through a third-order tensor over T periods and computes the sociometric Katz measure for each pair of nodes to quantify the strength of the social ties between the network entities. Such quantification gives insights about the links that are expected to occur in the period T+1 and the new links that are created in the future without being observed during the tracking time. To attest the efficiency of our framework, we apply our link prediction technique on three real traces and we compare its performance to the ones of other well-known link prediction approaches. The results prove that our method reaches the highest level of accuracy and outperforms the other techniques. One of the major contributions behind our proposal highlights that the link prediction in such networks can be made in a distributed way. In other words, the nodes can predict their future links relying on the local information (one-hop and two-hop neighbors) instead of a full knowledge about the topology of the network. Furthermore, we are keen to improve the link prediction performance of our tensor-based framework. To quantify the social closeness between the users, we take into consideration two aspects of the relationships: the recentness of the interactions and their frequency. From this perspective, we wonder if we can consider a third criterion to improve the link prediction precision. Asserting the heuristic that stipulates that persistent links are highly predictable, we take into account the stability of the relationships (link and proximity stabilities). To measure it, we opt for the entropy estimation of a time series proposed in the Lempel-Ziv data compression algorithm. As we think that our framework measurements and the stability estimations complement each other, we combine them in order to provide new link prediction metrics. The simulation results emphasize the pertinence of our intuition. Providing a tensor-based link prediction framework and proposing relative enhancements tied to stability considerations represent the main contributions of this thesis. Along the thesis, our concern was also focused on mechanisms and metrics that contribute towards improving communication protocols in these mobile networks [...]

隨著資訊科技的發達，資訊成長的速度日以倍計，對於大量且片斷的資料，社會網路分析(Social Network Analysis)提供我們可能的研究方法。社會網路主要是由節點以及節點彼此間的連結所形成的網路結構，透過社會網路分析和連結預測理論，我們可以從微觀與巨觀的切入角度，來進行龐大資料量的政府人事異動資料庫進行研究分析。本論文研究，將政府人事異動資料庫中的異動記錄建構為人物與職務兩類不同的社會網路結構，並透過社會網路分析以及連結預測，來發掘人物與不同職務之間的相互影響性，並進一步分析在特定職務的實際接任人選上，實際被影響的因素為何。實驗結果呈現本研究所設計出的模型，對於政府人事異動的互動關係在不同角度的觀察上有所幫助，也從中可以發現在實際接任人選上的考量上，歷任人選的歷任職務有相當程度的影響性，並瞭解社會網路分析與連結預測在實際情境應用下的可能性與限制性。 / Information grows up in very fast way with the advancement in information technology. SNA (Social Network Analysis) provides the possible research ways for the large number of fragmentary information. Social network is the network structure which constructed by the links of each nodes in it. Through SNA (Social Network Analysis) and Link Prediction theory, we can investigate government official's succession database with huge amount of data from micro and macro perspectives. The objective of this study is the construction of two different types of person and position social network structures and the exploration of the interaction between the person and position nodes through link prediction theory. We also discover the impact factors for actual appointee of specific position in further analysis. The study result shows the design model helps us to observe the interaction in government official's succession from different perspectives. We found that is great influence of successive positions of successive candidates in consideration of actual appointee.

L'explosion de données relationnelles largement disponiblessous la forme de graphes de connaissances a permisle développement de multiples applications, dont les agents personnels automatiques,les systèmes de recommandation et l'amélioration desrésultats de recherche en ligne.La grande taille et l'incomplétude de ces bases de donnéesnécessite le développement de méthodes de complétionautomatiques pour rendre ces applications viables.La complétion de graphes de connaissances, aussi appeléeprédiction de liens, se doit de comprendre automatiquementla structure des larges graphes de connaissances (graphes dirigéslabellisés) pour prédire les entrées manquantes (les arêtes labellisées).Une approche gagnant en popularité consiste à représenter ungraphe de connaissances comme un tenseur d'ordre 3, etd'utiliser des méthodes de décomposition de tenseur pourprédire leurs entrées manquantes.Les modèles de factorisation existants proposent différentscompromis entre leur expressivité, et leur complexité en temps et en espace.Nous proposons un nouveau modèle appelé ComplEx, pour"Complex Embeddings", pour réconcilier expressivité etcomplexité par l'utilisation d'une factorisation en nombre complexes,dont nous explorons le lien avec la diagonalisation unitaire.Nous corroborons notre approche théoriquement en montrantque tous les graphes de connaissances possiblespeuvent être exactement décomposés par le modèle proposé.Notre approche, basées sur des embeddings complexesreste simple, car n'impliquant qu'un produit trilinéaire complexe,là où d'autres méthodes recourent à des fonctions de compositionde plus en plus compliquées pour accroître leur expressivité.Le modèle proposé ayant une complexité linéaire en tempset en espace est passable à l'échelle, tout endépassant les approches existantes sur les jeux de données de référencepour la prédiction de liens.Nous démontrons aussi la capacité de ComplEx àapprendre des représentations vectorielles utiles pour d'autres tâches,en enrichissant des embeddings de mots, qui améliorentles prédictions sur le problème de traitement automatiquedu langage d'implication entre paires de phrases.Dans la dernière partie de cette thèse, nous explorons lescapacités de modèles de factorisation à apprendre lesstructures relationnelles à partir d'observations.De part leur nature vectorielle,il est non seulement difficile d'interpréter pourquoicette classe de modèles fonctionne aussi bien,mais aussi où ils échouent et comment ils peuventêtre améliorés. Nous conduisons une étude expérimentalesur les modèles de l'état de l'art, non pas simplementpour les comparer, mais pour comprendre leur capacitésd'induction. Pour évaluer les forces et faiblessesde chaque modèle, nous créons d'abord des tâches simplesreprésentant des propriétés atomiques despropriétés des relations des graphes de connaissances ;puis des tâches représentant des inférences multi-relationnellescommunes au travers de généalogies synthétisées.À partir de ces résultatsexpérimentaux, nous proposons de nouvelles directionsde recherches pour améliorer les modèles existants,y compris ComplEx. / The explosion of widely available relational datain the form of knowledge graphsenabled many applications, including automated personalagents, recommender systems and enhanced web search results.The very large size and notorious incompleteness of these data basescalls for automatic knowledge graph completion methods to make these applicationsviable. Knowledge graph completion, also known as link-prediction,deals with automatically understandingthe structure of large knowledge graphs---labeled directed graphs---topredict missing entries---labeled edges. An increasinglypopular approach consists in representing knowledge graphs as third-order tensors,and using tensor factorization methods to predict their missing entries.State-of-the-art factorization models propose different trade-offs between modelingexpressiveness, and time and space complexity. We introduce a newmodel, ComplEx---for Complex Embeddings---to reconcile both expressivenessand complexity through the use of complex-valued factorization, and exploreits link with unitary diagonalization.We corroborate our approach theoretically and show that all possibleknowledge graphs can be exactly decomposed by the proposed model.Our approach based on complex embeddings is arguably simple,as it only involves a complex-valued trilinear product,whereas other methods resort to more and more complicated compositionfunctions to increase their expressiveness. The proposed ComplEx model isscalable to large data sets as it remains linear in both space and time, whileconsistently outperforming alternative approaches on standardlink-prediction benchmarks. We also demonstrateits ability to learn useful vectorial representations for other tasks,by enhancing word embeddings that improve performanceson the natural language problem of entailment recognitionbetween pair of sentences.In the last part of this thesis, we explore factorization models abilityto learn relational patterns from observed data.By their vectorial nature, it is not only hard to interpretwhy this class of models works so well,but also to understand where they fail andhow they might be improved. We conduct an experimentalsurvey of state-of-the-art models, not towardsa purely comparative end, but as a means to get insightabout their inductive abilities.To assess the strengths and weaknesses of each model, we create simple tasksthat exhibit first, atomic properties of knowledge graph relations,and then, common inter-relational inference through synthetic genealogies.Based on these experimental results, we propose new researchdirections to improve on existing models, including ComplEx.

Online social networks (OSNs) are Web platforms providing different services to facilitate social interaction among their users. A particular kind of OSNs is the location-based social network (LBSN), which adds services based on location. One of the most important challenges in LBSNs is the link prediction problem. Link prediction problem aims to estimate the likelihood of the existence of future friendships among user pairs. Most of the existing studies in link prediction focus on the use of a single information source to perform predictions, i.e. only social information (e.g. social neighborhood) or only location information (e.g. common visited places). However, some researches have shown that the combination of different information sources can lead to more accurate predictions. In this sense, in this thesis we propose different link prediction methods based on the use of different information sources naturally existing in these networks. Thus, we propose seven new link prediction methods using the information related to user membership in social overlapping groups: common neighbors within and outside of common groups (WOCG), common neighbors of groups (CNG), common neighbors with total and partial overlapping of groups (TPOG), group naïve Bayes (GNB), group naïve Bayes of common neighbors (GNB-CN), group naïve Bayes of Adamic-Adar (GNB-AA) and group naïve Bayes of Resource Allocation (GNB-RA). Due to that social groups exist naturally in networks, our proposals can be used in any type of OSN.We also propose new eight link prediction methods combining location and social information: Check-in Observation (ChO), Check-in Allocation (ChA), Within and Outside of Common Places (WOCP), Common Neighbors of Places (CNP), Total and Partial Overlapping of Places (TPOP), Friend Allocation Within Common Places (FAW), Common Neighbors of Nearby Places (CNNP) and Nearby Distance Allocation (NDA). These eight methods are exclusively for work in LBSNs. Obtained results indicate that our proposals are as competitive as state-of-the-art methods, or better than they in certain scenarios. Moreover, since our proposals tend to be computationally more efficient, they are more suitable for real-world applications. / Redes sociais online (OSNs) são plataformas Web que oferecem serviços para promoção da interação social entre usuários. OSNs que adicionam serviços relacionados à geolocalização são chamadas redes sociais baseadas em localização (LBSNs). Um dos maiores desafios na análise de LBSNs é a predição de links. A predição de links refere-se ao problema de estimar a probabilidade de conexão futura entre pares de usuários que não se conhecem. Grande parte das pesquisas que focam nesse problema exploram o uso, de maneira isolada, de informações sociais (e.g. amigos em comum) ou de localização (e.g. locais comuns visitados). Porém, algumas pesquisas mostraram que a combinação de diferentes fontes de informação pode influenciar o incremento da acurácia da predição. Motivado por essa lacuna, neste trabalho foram desenvolvidos diferentes métodos para predição de links combinando diferentes fontes de informação. Assim, propomos sete métodos que usam a informação relacionada à participação simultânea de usuários en múltiples grupos sociais: common neighbors within and outside of common groups (WOCG), common neighbors of groups (CNG), common neighbors with total and partial overlapping of groups (TPOG), group naïve Bayes (GNB), group naïve Bayes of common neighbors (GNB-CN), group naïve Bayes of Adamic-Adar (GNB-AA), e group naïve Bayes of Resource Allocation (GNB-RA). Devido ao fato que a presença de grupos sociais não está restrita a alguns tipo de redes, essas propostas podem ser usadas nas diversas OSNs existentes, incluindo LBSNs. Também, propomos oito métodos que combinam o uso de informações sociais e de localização: Check-in Observation (ChO), Check-in Allocation (ChA), Within and Outside of Common Places (WOCP), Common Neighbors of Places (CNP), Total and Partial Overlapping of Places (TPOP), Friend Allocation Within Common Places (FAW), Common Neighbors of Nearby Places (CNNP), e Nearby Distance Allocation (NDA). Tais propostas são para uso exclusivo em LBSNs. Os resultados obtidos indicam que nossas propostas são tão competitivas quanto métodos do estado da arte, podendo até superá-los em determinados cenários. Ainda mais, devido a que na maioria dos casos nossas propostas são computacionalmente mais eficientes, seu uso resulta mais adequado em aplicações do mundo real.

Durant ces dernières années, nous avons observe une expansion progressive et continue des réseaux mobile sans-fil centres sur l’être humain. L’apparition de ces réseaux a encouragé les chercheurs à réfléchir à de nouvelles solutions pour assurer une évaluation efficace et une conception adéquate des protocoles de communication. En effet, ces réseaux sont sujets à de multiples contraintes telles que le manque d’infrastructure, la topologie dynamique, les ressources limitées ainsi que la qualité de service et la sécurité des informations précaires. Nous nous sommes spécialement intéressés à l’aspect dynamique du réseau et en particulier à la mobilité humaine. La mobilité humaine a été largement étudiée pour pouvoir extraire ses propriétés intrinsèques et les exploiter pour des approches plus adaptées à cette mobilité. Parmi les propriétés les plus intéressantes soulevées dans la littérature, nous nous sommes focalisés sur l’impact des interactions sociales entre les entités du réseau sur la mobilité humaine et en conséquence sur la structure du réseau. Pour recueillir des informations structurelles sur le réseau, plusieurs métriques et techniques ont été empruntées de l’analyse des réseaux sociaux (SNA). Cet outil peut être assimilé à une autre alternative pour mesurer des indicateurs de performance du réseau. Plus précisément, il extrait des informations structurelles du réseau et permet aux protocoles de communication de bénéficier d’indications utiles telles que la robustesse du réseau, les nœuds centraux ou encore les communautés émergentes. Dans ce contexte, la SNA a été largement utilisée pour prédire les liens dans les réseaux sociaux en se basant notamment sur les informations structurelles. Motivés par l’importance des liens sociaux dans les réseaux mobiles sans-fil centres sur l’être humain et par les possibilités offertes par la SNA pour prédire les liens, nous nous proposons de concevoir la première méthode capable de prédire les liens dans les réseaux sans-fil mobiles tels que les réseaux ad-hoc mobiles (MANETs) et les réseaux tolérants aux délais (DTNs). Notre proposition suit l’évolution de la topologie du réseau sur T périodes à travers un tenseur (en ensemble de matrices d’adjacence et chacune des matrices correspond aux contacts observés durant une période bien spécifique). Ensuite, elle s’appuie sur le calcul de la mesure sociométrique de Katz pour chaque paire de nœuds pour mesurer l’étendue des relations sociales entre les différentes entités du réseau. Une telle quantification donne un aperçu sur les liens dont l’occurrence est fortement pressentie à la période T+1 et les nouveaux liens qui se créent dans le futur sans pour autant avoir été observés durant le temps de suivi. Pour attester l’efficacité de notre proposition, nous l’appliquons sur trois traces réelles et nous comparons sa performance à celles d’autres techniques de prédiction de liens présentées dans la littérature. Les résultats prouvent que notre méthode est capable d’atteindre le meilleur niveau d’efficacité et sa performance surpasse celles des autres techniques. L’une des majeures contributions apportées par cette proposition met en exergue la possibilité de prédire les liens d’une manière décentralisée. En d’autres termes, les nœuds sont capables de prédire leurs propres liens dans le futur en se basant seulement sur la connaissance du voisinage immédiat (voisins à un et deux sauts). En outre, nous sommes désireux d’améliorer encore plus la performance de notre méthode de prédiction de liens. Pour quantifier la force des relations sociales entre les entités du réseau, nous considérons deux aspects dans les relations : la récence des interactions et leur fréquence. À partir de là, nous nous demandons s’il est possible de prendre en compte un troisième critère pour améliorer la précision des prédictions […] / During the last years, we have observed a progressive and continuous expansion of human-centered mobile wireless networks. The advent of these networks has encouraged the researchers to think about new solutions in order to ensure efficient evaluation and design of communication protocols. In fact, these networks are faced to several constraints as the lack of infrastructure, the dynamic topology, the limited resources and the deficient quality of service and security. We have been interested in the dynamicity of the network and in particular in human mobility. The human mobility has been widely studied in order to extract its intrinsic properties and to harness them to propose more accurate approaches. Among the prominent properties depicted in the literature, we have been specially attracted by the impact of the social interactions on the human mobility and consequently on the structure of the network. To grasp structural information of such networks, many metrics and techniques have been borrowed from the Social Network Analysis (SNA). The SNA can be seen as another network measurement task which extracts structural information of the network and provides useful feedback for communication protocols. In this context, the SNA has been extensively used to perform link prediction in social networks relying on their structural properties. Motivated by the importance of social ties in human-centered mobile wireless networks and by the possibilities that are brought by SNA to perform link prediction, we are interested by designing the first link prediction framework adapted for mobile wireless networks as Mobile Ad-hoc Networks (MANETs) and Delay/Disruption Tolerant Networks (DTN). Our proposal tracks the evolution of the network through a third-order tensor over T periods and computes the sociometric Katz measure for each pair of nodes to quantify the strength of the social ties between the network entities. Such quantification gives insights about the links that are expected to occur in the period T+1 and the new links that are created in the future without being observed during the tracking time. To attest the efficiency of our framework, we apply our link prediction technique on three real traces and we compare its performance to the ones of other well-known link prediction approaches. The results prove that our method reaches the highest level of accuracy and outperforms the other techniques. One of the major contributions behind our proposal highlights that the link prediction in such networks can be made in a distributed way. In other words, the nodes can predict their future links relying on the local information (one-hop and two-hop neighbors) instead of a full knowledge about the topology of the network. Furthermore, we are keen to improve the link prediction performance of our tensor-based framework. To quantify the social closeness between the users, we take into consideration two aspects of the relationships: the recentness of the interactions and their frequency. From this perspective, we wonder if we can consider a third criterion to improve the link prediction precision. Asserting the heuristic that stipulates that persistent links are highly predictable, we take into account the stability of the relationships (link and proximity stabilities). To measure it, we opt for the entropy estimation of a time series proposed in the Lempel-Ziv data compression algorithm. As we think that our framework measurements and the stability estimations complement each other, we combine them in order to provide new link prediction metrics. The simulation results emphasize the pertinence of our intuition. Providing a tensor-based link prediction framework and proposing relative enhancements tied to stability considerations represent the main contributions of this thesis. Along the thesis, our concern was also focused on mechanisms and metrics that contribute towards improving communication protocols in these mobile networks […]

No description available.

Link prediction is a crucial task in many downstream applications of graph machine learning. Graph Neural Networks (GNNs) are a prominent approach for transductive link prediction, where the aim is to predict missing links or connections only within the existing nodes of a given graph. However, many real-life applications require inductive link prediction for the newly-coming nodes with no connections to the original graph. Thus, recent approaches have adopted a Multilayer Perceptron (MLP) for inductive link prediction based solely on node features. In this work, we show that incorporating both connectivity structure and features for the new nodes provides better model expressiveness. To bring such expressiveness to inductive link prediction, we propose LEAP, an encoder that features LEArnable toPology augmentation of the original graph and enables message passing with the newly-coming nodes. To the best of our knowledge, this is the first attempt to provide structural contexts for the newly-coming nodes via learnable augmentation under inductive settings. Conducting extensive experiments on four real- world homogeneous graphs demonstrates that LEAP significantly surpasses the state-of-the-art methods in terms of AUC and average precision. The improvements over homogeneous graphs are up to 22% and 17%, respectively. The code and datasets are available on GitHub*. / Att förutsäga länkar är en viktig uppgift i många efterföljande tillämpningar av maskininlärning av grafer. Graph Neural Networks (GNNs) är en framträdande metod för transduktiv länkförutsägelse, där målet är att förutsäga saknade länkar eller förbindelser endast inom de befintliga noderna i en given graf. I många verkliga tillämpningar krävs dock induktiv länkförutsägelse för nytillkomna noder utan kopplingar till den ursprungliga grafen. Därför har man på senare tid antagit en Multilayer Perceptron (MLP) för induktiv länkförutsägelse som enbart bygger på nodens egenskaper. I det här arbetet visar vi att om man införlivar både anslutningsstruktur och egenskaper för de nya noderna får man en bättre modelluttryck. För att ge induktiv länkförutsägelse en sådan uttrycksfullhet föreslår vi LEAP, en kodare som innehåller LEArnable toPology augmentation av den ursprungliga grafen och möjliggör meddelandeöverföring med de nytillkomna noderna. Såvitt vi vet är detta det första försöket att tillhandahålla strukturella sammanhang för de nytillkomna noderna genom en inlärningsbar ökning i induktiva inställningar. Omfattande experiment på fyra homogena grafer i den verkliga världen visar att LEAP avsevärt överträffar "state-of-the-art" metoderna när det gäller AUC och genomsnittlig precision. Förbättringarna jämfört med homogena grafer är upp till 22% och 17%. Koden och datamängderna finns tillgängliga på Github*.

A análise de redes sociais permite estudar a maneira como são estabelecidas as conexões entre indivíduos e como estas evoluem ao longo do tempo. A coautoria é uma das formas mais estudadas e bem documentadas de colaboração científica. Existem muitos aspectos de redes de colaboração científica, os quais podem ser rastreados de forma confiável através da análise de redes de colaboração usando métodos bibliométricos. Diversos esforços em diferentes áreas de pesquisa tentam analisar, entender, explicar e predizer o comportamento de sistemas modelados através de redes sociais. Nestes estudos, os indivíduos são modelados como vértices de um grafo, enquanto as relações entre eles são representadas por arestas. Atualmente, o estudo de redes de colaboração científica é importante e necessário para apoiar o planejamento estratégico, implementação e gestão dos programas de pesquisa científica. Neste trabalho, apresentamos um modelo de análise de redes científicas baseado em Grafos Relacionais com Atributos (ARG). O modelo proposto permite representar as redes de colaboração científica incluindo atributos individuais dos pesquisadores e atributos dos trabalhos colaborativos de pares de pesquisadores. Os dados correspondem às produções científicas de pesquisadores cadastrados na plataforma Lattes e extraídas automaticamente usando a ferramenta scriptLattes. Na primeira etapa, foi implementado o cálculo automatizado da taxa de internacionalização de cada pesquisador, a qual mostra a proporção entre o número de publicações internacionais e o número total de publicações. Esta medida junto com a produção científica individual discretizada em diversos grupos fazem parte das informações armazenadas nos vetores de atributos dos vértice dos ARGs. Por outro lado os vetores de atributos das arestas armazenam informações dos trabalhos colaborativos discretizados segundo a classificação da CAPES. Adicionalmente, neste trabalho foram exploradas duas aplicações relacionadas à (i) predição de trabalhos colaborativos futuros e à (ii) influência dos pesquisadores na rede de colaboração. O resultado da predição de vínculos foi usado para determinar a influência dos pesquisadores na redes de colaboração. A influência tem sido explorada com base na variação da predição de ligações com a presença ou a ausência do pesquisador na rede. Nossa proposta foi avaliada considerando diferentes testes sobre redes de coautoria científica de diversos grupos de pesquisadores. Os resultados obtidos são promissores para a análise de redes sociais em geral. / The social network analysis allows the study of how the relationships are established between individuals and how their are evolving with the time. The co-authorship is one of the most studied and documented scientific collaboration. There are some aspects which could be traced in a reliable way through the social network analysis using bibliometric methods. There are several proposals in different research areas trying to analyse, understand, explain and predict the behaviour of systems modeled as social networks. In this study, the individuals are modeled as vertices of a graph, while the relationships between them are represented by edges. Currently the study of scientific collaboration networks is important and necessary to support the strategic planning, implementation and management of scientific research programs. In this work, we present an scientific networks analysis model based on Attributed Relational Graphs (ARG). The proposed model allows to represent the scientific collaboration networks including individual attributes of researchers and attributes of the collaborative work of researchers pairs. The data correspond to the scientific production of researchers, registered in the Lattes Platform and automatically extracted using the tool scriptLattes \\citep{Mena-Chalco:2009}. In the first step, was implemented the automated computation of the internationalization rate for each researcher, that shows the ratio between the number of international publications and the total number of publications. This measure together with the individual scientific production discretized in diverse groups form part of the information stored in the vertices of the ARGs. On the other hand, the edges store information of collaborative work discretized according to the CAPES classification. Additionally, this work explores two related applications (i) prediction of future collaborative work and (ii) influence of researchers in collaboration network. The result of the link prediction was used to determine the influence of researchers in collaborative networks. The influence in collaboration network is computed based on the variation of the link prediction with the presence or absence of the researcher in the network. Our proposal was evaluated with different real scientific co-authorship networks and with different research groups. The results obtained look promising for analyzing social networks in general.

Les réseaux sociaux sont de très grands systèmes permettant de représenter les interactions sociales entre les individus. L'analyse des réseaux sociaux est une collection de méthodes spécialement conçues pour examiner les aspects relationnels des structures sociales. L'un des défis les plus importants dans l'analyse de réseaux sociaux est le problème de prédiction de liens. La prédiction de liens étudie l'existence potentielle de nouvelles associations parmi des entités sociales non connectées. La plupart des approches de prédiction de liens se concentrent sur une seule source d'information, c'est-à-dire sur les aspects topologiques du réseau (par exemple le voisinage des nœuds) en supposant que les données sociales sont entièrement fiables. Pourtant, ces données sont généralement bruitées, manquantes et sujettes à des erreurs d'observation causant des distorsions et des résultats probablement erronés. Ainsi, cette thèse propose de gérer le problème de prédiction de liens sous incertitude. D'abord, deux nouveaux modèles de graphes de réseaux sociaux uniplexes et multiplexes sont introduits pour traiter l'incertitude dans les données sociales. L'incertitude traitée apparaît au niveau des liens et est représentée et gérée à travers le cadre de la théorie des fonctions de croyance. Ensuite, nous présentons huit méthodes de prédiction de liens utilisant les fonctions de croyance fondées sur différentes sources d'information dans les réseaux sociaux uniplexes et multiplexes. Nos contributions s'appuient sur les informations disponibles sur le réseau social. Nous combinons des informations structurelles aux informations des cercles sociaux et aux attributs des nœuds, ainsi que l'apprentissage supervisé pour prédire les nouveaux liens. Des tests sont effectués pour valider la faisabilité et l'intérêt de nos approches à celles de la littérature. Les résultats obtenus sur les données du monde réel démontrent que nos propositions sont pertinentes et valables dans le contexte de prédiction de liens. / Social networks are large structures that depict social linkage between millions of actors. Social network analysis came out as a tool to study and monitor the patterning of such structures. One of the most important challenges in social network analysis is the link prediction problem. Link prediction investigates the potential existence of new associations among unlinked social entities. Most link prediction approaches focus on a single source of information, i.e. network topology (e.g. node neighborhood) assuming social data to be fully trustworthy. Yet, such data are usually noisy, missing and prone to observation errors causing distortions and likely inaccurate results. Thus, this thesis proposes to handle the link prediction problem under uncertainty. First, two new graph-based models for uniplex and multiplex social networks are introduced to address uncertainty in social data. The handled uncertainty appears at the links level and is represented and managed through the belief function theory framework. Next, we present eight link prediction methods using belief functions based on different sources of information in uniplex and multiplex social networks. Our proposals build upon the available information in data about the social network. We combine structural information to social circles information and node attributes along with supervised learning to predict new links. Tests are performed to validate the feasibility and the interest of our link prediction approaches compared to the ones from literature. Obtained results on social data from real-world demonstrate that our proposals are relevant and valid in the link prediction context.

隨著個人電腦與網際網路科技的逐漸成熟，網路上每日都有巨量資料（Big Data）產生。近年來隨著社群網站的崛起，如何處理這些巨量的社群資料，並有效率地提供出有意義的社群資訊，將是這幾年社群網路領域研究的重點。每當內閣改組消息一出的時候，各政府部門單位的官職繼任官員，都會成為社會公眾關注的議題。本研究將使用中華民國政府官職資料庫，以社群網路分析與連結預測理論為基礎，並透過資料庫中所提供的資料，隨著不同評選時間點以及評選官職建置出網路。擷取網路的資訊，利用本文所提出的多面向模型（Multiperspective Model）產生多種觀點的分數。接著使用評選模型（Evaluation Model）將各個觀點的分數整合，進行某官員繼任某官職可能性計算，然後輸出官職繼任官員的評選清單（Evaluation List）。最後對輸出的評選清單分別對空降繼任狀況、各級上司對於繼任人選決定影響力、單一觀點與多觀點評選方式的評選結果、多觀點評選方式下重視的觀點，以及官職繼任成因五項分析進行探討。 / With the well development of personal PC and the Internet technology, there is a huge amount of data (Big Data) being generated on the Internet every day. Because of the debut and rise of social websites, how to deal with such a huge amount of community information as well as efficiently provide meaningful data to the public has been an explored main issue in the field of social network research in recent years. When the news about cabinet changing was released, the successor of various government departments will become the actively concerned topic for the public. This research applied a government position transaction database as the elements to build the network, which based on Social Network Analysis and Link Prediction theory with different evaluation position and evaluation time. Captured information in the network was used to generate the scores of multiple perspectives according to the Multiperspective Model. Then using the Evaluation Model, which can integrate each observed perspective, and calculate the probability of an official succeeds of a position. Finally the network could output the evaluation list of position successor. In the end, the outcome of the evaluation list was applied to analyze and discuss the following 5 research questions: The situation that the successor isn’t from the unit of successive position, the influence of all levels superiors on the succession decision, result of evaluative methods of a single view and multiple perspective, the important perspective of Multiperspective evaluation, and causal relationship of official successor.