The purpose of this activity is to investigate how the PageRank algorithm behaves in relation to the damping factor when applied to small graphs and certain special graph types. The PageRank algorithm involves the calculation of eigenvalues and eigenvectors of the Google matrix for both directed and undirected graphs. This discussion will focus on all directed graphs with up to four vertices and select special graphs. Our primary objective is to observe how the damping factor influences the dominant eigenvector for each graph and, consequently, how it impacts PageRank. We have calculated PageRank for all the graphs and conducted an analysis, particularly focusing on the effect of the damping factor, denoted as "c," in our discussions. To compute the PageRank algorithm, we constructed a probability matrix for all the graphs and performed the calculations using MATLAB. This process yielded eigenvalues and eigenvectors associated with the Google matrix. The theoretical section of this thesis encompasses the PageRank theory, including essential proofs, theorems, and definitions that serve as foundational elements throughout the thesis. Additionally, we delve into the historical context and practical applications of PageRank. In our study, we present a comparative analysis of the results, specifically examining the impact of a damping factor on the dominant PageRank eigenvector.

The purpose of this thesis is to present research related to the damping factor in relation to the PageRank algorithm where a method of symbolic calculations is used to calculate eigenvalues, eigenvectors corresponding to the Google matrix in relation to both directed and undirected graphs. These graphs given comprise all the directed graphs up to four vertices and in addition the undirected graphs of five vertices are given in this thesis. A central research question has been to determine how $d$ behaves in relation to effecting the result of the dominant eigenvector for corresponding graphs such as to determine how the PageRank is directly influenced. A few selected graphs along with their calculations were extracted and analyzed in terms of the parameter $d$. For the calculations in this thesis probability matrices were constructed for all graphs and calculations were made using Matlab where eigenvalues, eigenvectors corresponding to the Google matrix were returned along with the input probability matrix and the Google matrix. In addition, the thesis contains a theoretical portion related to the theory behind PageRank along with relevant proofs, theorems and definitions which are used throughout the thesis. Some brief mention of the historical background and applications of the PageRank are also given. \bigskip A discussion of the results is provided involving the interaction of the damping factor with the dominant PageRank eigenvector. Lastly, a conclusion is given and future prospects relating to the topic of research is discussed. The work in this thesis is inspired by a previous work done by Silvestrov et al. in $2008$ where we have here placed further emphasis on the damping factor.

Cette thèse s’intéresse à l’analyse du réseau dirigé extrait de la structure des hyperliens de Wikipédia. Notre objectif est de mesurer les interactions liant un sous-ensemble de pages du réseau Wikipédia. Par conséquent, nous proposons de tirer parti d’une nouvelle représentation matricielle appelée matrice réduite de Google ou "reduced Google Matrix". Cette matrice réduite de Google (GR) est définie pour un sous-ensemble de pages donné (c-à-d un réseau réduit).Comme pour la matrice de Google standard, un composant de GR capture la probabilité que deux noeuds du réseau réduit soient directement connectés dans le réseau complet. Une des particularités de GR est l’existence d’un autre composant qui explique la probabilité d’avoir deux noeuds indirectement connectés à travers tous les chemins possibles du réseau entier. Dans cette thèse, les résultats de notre étude de cas nous montrent que GR offre une représentation fiable des liens directs et indirects (cachés). Nous montrons que l’analyse de GR est complémentaire à l’analyse de "PageRank" et peut être exploitée pour étudier l’influence d’une variation de lien sur le reste de la structure du réseau. Les études de cas sont basées sur des réseaux Wikipédia provenant de différentes éditions linguistiques. Les interactions entre plusieurs groupes d’intérêt ont été étudiées en détail : peintres, pays et groupes terroristes. Pour chaque étude, un réseau réduit a été construit. Les interactions directes et indirectes ont été analysées et confrontées à des faits historiques, géopolitiques ou scientifiques. Une analyse de sensibilité est réalisée afin de comprendre l’influence des liens dans chaque groupe sur d’autres noeuds (ex : les pays dans notre cas). Notre analyse montre qu’il est possible d’extraire des interactions précieuses entre les peintres, les pays et les groupes terroristes. On retrouve par exemple, dans le réseau de peintre sissu de GR, un regroupement des artistes par grand mouvement de l’histoire de la peinture. Les interactions bien connues entre les grands pays de l’UE ou dans le monde entier sont également soulignées/mentionnées dans nos résultats. De même, le réseau de groupes terroristes présente des liens pertinents en ligne avec leur idéologie ou leurs relations historiques ou géopolitiques.Nous concluons cette étude en montrant que l’analyse réduite de la matrice de Google est une nouvelle méthode d’analyse puissante pour les grands réseaux dirigés. Nous affirmons que cette approche pourra aussi bien s’appliquer à des données représentées sous la forme de graphes dynamiques. Cette approche offre de nouvelles possibilités permettant une analyse efficace des interactions d’un groupe de noeuds enfoui dans un grand réseau dirigé / This thesis concentrates on the analysis of the large directed network representation of Wikipedia.Wikipedia stores valuable fine-grained dependencies among articles by linking webpages togetherfor diverse types of interactions. Our focus is to capture fine-grained and realistic interactionsbetween a subset of webpages in this Wikipedia network. Therefore, we propose to leverage anovel Google matrix representation of the network called the reduced Google matrix. This reducedGoogle matrix (GR) is derived for the subset of webpages of interest (i.e. the reduced network). Asfor the regular Google matrix, one component of GR captures the probability of two nodes of thereduced network to be directly connected in the full network. But unique to GR, anothercomponent accounts for the probability of having both nodes indirectly connected through allpossible paths in the full network. In this thesis, we demonstrate with several case studies that GRoffers a reliable and meaningful representation of direct and indirect (hidden) links of the reducednetwork. We show that GR analysis is complementary to the well-known PageRank analysis andcan be leveraged to study the influence of a link variation on the rest of the network structure.Case studies are based on Wikipedia networks originating from different language editions.Interactions between several groups of interest are studied in details: painters, countries andterrorist groups. For each study, a reduced network is built, direct and indirect interactions areanalyzed and confronted to historical, geopolitical or scientific facts. A sensitivity analysis isconducted to understand the influence of the ties in each group on other nodes (e.g. countries inour case). From our analysis, we show that it is possible to extract valuable interactions betweenpainters, countries or terrorist groups. Network of painters with GR capture art historical fact sucha painting movement classification. Well-known interactions of countries between major EUcountries or worldwide are underlined as well in our results. Similarly, networks of terrorist groupsshow relevant ties in line with their objective or their historical or geopolitical relationships. Weconclude this study by showing that the reduced Google matrix analysis is a novel powerfulanalysis method for large directed networks. We argue that this approach can find as well usefulapplication for different types of datasets constituted by the exchange of dynamic content. Thisapproach offers new possibilities to analyze effective interactions in a group of nodes embedded ina large directed network.