This thesis studies two problems centered around non-backtracking walks on graphs. First, we analyze the spectrum of the non-backtracking matrix of a graph. We show how to obtain the eigenvectors of the non-backtracking matrix using a smaller matrix and in doing so, create a block diagonal decomposition which more clearly expresses the non-backtracking matrix eigenvalues. Additionally, we develop upper and lower bounds on the matrix spectrum and use the spectrum to investigate properties of the graph. Second, we investigate the difference between PageRank and non-backtracking PageRank. We show some instances where there is no difference and develop an algorithm to compare PageRank and non-backtracking PageRank under certain conditions using $\mu$-PageRank.

El 54% de la población mundial vive ya en torno a núcleos de población que llamamos ciudades, por lo que su estudio nos enseña la forma en que piensa y se desarrolla el propio ser humano. Un análisis de las relaciones espaciales que se producen en entornos urbanos reales requieren un procesamiento de dichas relaciones en paralelo. Con el fin de representar y analizar estas relaciones espaciales complejas, los especialistas en urbanismo han empezado a utilizar modelos basados en redes complejas. Las redes emergen como un nuevo modelo más acorde con el problema de la complejidad organizada que es una ciudad. Otro aspecto esencial unido a las ciudades es que se han convertido en unas entidades productoras y creadoras de datos, tanto físicos como virtuales. Un estudio serio de la ciudad significa, por tanto, un estudio de los datos que en ella se generan o se encuentran. Dentro de la moderna teoría de redes, un concepto fundamental y muy estudiado en la bibliografía en las últimas décadas es el de la centralidad de la red. La centralidad consiste en determinar cuantitativamente la importancia de cada nodo dentro de la red, dependiendo del criterio que se adopte en cuanto a lo que consideramos por “importante”. Existen unas medidas clásicas de centralidad en redes complejas, como son la centralidad de grado, de cercanía, de intermediación y basadas en el vector propio. Todas estas medidas solo tienen en cuenta la topología de la red para determinar un valor y una clasificación de los nodos en orden de importancia. Cuando aplicamos estas centralidades a las redes urbanas nos encontramos con el problema de la densidad de grado uniforme que tienen estas redes, lo que hace que no sean adecuadas para la realidad que representan las ciudades. En esta memoria, se han implementado un conjunto de medidas de centralidad para redes urbanas, con la principal característica que tienen en cuenta no solo la topología de la red sino la influencia de la cuantía de los datos presentes en la misma. De esta forma, cuando estudiamos la centralidad de una red urbana, tenemos en cuenta de forma determinante qué datos analizamos y su influencia en la red. Más concretamente, se han implementado tres medidas de centralidad basadas en el concepto de PageRank, introducido por Page y Brin en el conocido buscador Google, que clasifican los nodos de una red urbana en orden de importancia, tanto atendiendo a su conectividad como a los datos asociados a cada nodo. Se ha implementado una medida de centralidad basada en la clásica medida current-flow betweenness, un tipo concreto de medida de intermediación que estudia la distribución de flujos por una red. Por último, se ha implementado una medida de centralidad para redes urbanas basad en el concepto de centralidad basada en el vector propio, donde la idea básica es que un nodo es importante si sus conexiones o vecinos son importantes. Al final de la memoria se establece una pequeña comparativa entre las medidas basadas en el vector PageRank y vector propio, ya que todas se basan en el cálculo de un vector propio del valor propio dominante de una cierta matriz que resume tanto la conectividad de la red como sus datos.

The cold water of Antarctica has a unique endemic fauna, where durophagous predators are rare or absent. Due to climate change the water is heating up and the predators have begun to return to the Southern Ocean, which could bring a lot of changes to the food web. There is a high risk it will lead to losses in the unique marine fauna of Antarctica. The aim of this study is therefore to examine the potential effect these invasive species has on the food web structure in the Weddell Sea. To study this, several general network metrics were used (connectance, number of interactions, vulnerability and generality, trait distributions), as well as a number of centrality metrics (betweenness, closeness, PageRank). The analyses showed that none of the invasive species become important in the Weddell Sea food web. Nor do they significantly change the food web structure in any way which impact the importance of the native species. Their great opportunism regarding their prey species, and thereby their connectedness and thus their position in the network, are probably the main reason why theses invasive species did not become important in this food web. The lack of changes in the food web structure due to the presence of these invasive species are probably also a result of not including factors such as abundances and network dynamics in the analyses, which seem to be the driving forces when it comes to changes in food web structure caused by invasion of species.

This work concerns optimalization of web pages for finders in the way that the web pages could be placed on best positions. The key of success for optimalization of web pages is the combination of some basic rules. The comparison of advantages of different ways of navigation and creation of menu, speed optimalization of pages loading, texts optimalization with the help of chosen key words, principles of choosing the key words, item placing on web pages and comparison of design, marketing and custom view of making the web pages. First of all, we will look on the difference between catalogues and full text finders, their historical development and current ratio of finders on our market. Subsequently we will describe the presumptions for optimalization from the resource code and programming languages point of view, which are used on web pages. The most important part of our interest is the optimalization methods of web pages content and also the methods which are considered as forbidden. The final implementation is made in PHP language.

No description available.

Motivation: Disease progression in cancer can vary substantially between patients. Yet, patients often receive the same treatment. Recently, there has been much work on predicting disease progression and patient outcome variables from gene expression in order to personalize treatment options. A widely used approach is high-throughput experiments that aim to explore predictive signature genes which would provide identification of clinical outcome of diseases. Microarray data analysis helps to reveal underlying biological mechanisms of tumor progression, metastasis, and drug-resistance in cancer studies. Despite first diagnostic kits in the market, there are open problems such as the choice of random gene signatures or noisy expression data. The experimental or computational noise in data and limited tissue samples collected from patients might furthermore reduce the predictive power and biological interpretability of such signature genes. Nevertheless, signature genes predicted by different studies generally represent poor similarity; even for the same type of cancer. Integration of network information with gene expression data could provide more efficient signatures for outcome prediction in cancer studies. One approach to deal with these problems employs gene-gene relationships and ranks genes using the random surfer model of Google's PageRank algorithm. Unfortunately, the majority of published network-based approaches solely tested their methods on a small amount of datasets, questioning the general applicability of network-based methods for outcome prediction. Methods: In this thesis, I provide a comprehensive and systematically evaluation of a network-based outcome prediction approach -- NetRank - a PageRank derivative -- applied on several types of gene expression cancer data and four different types of networks. The algorithm identifies a signature gene set for a specific cancer type by incorporating gene network information with given expression data. To assess the performance of NetRank, I created a benchmark dataset collection comprising 25 cancer outcome prediction datasets from literature and one in-house dataset. Results: NetRank performs significantly better than classical methods such as foldchange or t-test as it improves the prediction performance in average for 7%. Besides, we are approaching the accuracy level of the authors' signatures by applying a relatively unbiased but fully automated process for biomarker discovery. Despite an order of magnitude difference in network size, a regulatory, a protein-protein interaction and two predicted networks perform equally well. Signatures as published by the authors and the signatures generated with classical methods do not overlap -- not even for the same cancer type -- whereas the network-based signatures strongly overlap. I analyze and discuss these overlapping genes in terms of the Hallmarks of cancer and in particular single out six transcription factors and seven proteins and discuss their specific role in cancer progression. Furthermore several tests are conducted for the identification of a Universal Cancer Signature. No Universal Cancer Signature could be identified so far, but a cancer-specific combination of general master regulators with specific cancer genes could be discovered that achieves the best results for all cancer types. As NetRank offers a great value for cancer outcome prediction, first steps for a secure usage of NetRank in a public cloud are described. Conclusion: Experimental evaluation of network-based methods on a gene expression benchmark dataset suggests that these methods are especially suited for outcome prediction as they overcome the problems of random gene signatures and noisy expression data. Through the combination of network information with gene expression data, network-based methods identify highly similar signatures over all cancer types, in contrast to classical methods that fail to identify highly common gene sets across the same cancer types. In general allows the integration of additional information in gene expression analysis the identification of more reliable, accurate and reproducible biomarkers and provides a deeper understanding of processes occurring in cancer development and progression.

This is a literature study, in linear algebra, about positive and nonnegative matrices and their special properties. We say that a matrix or a vector is positive/nonnegative if all of its entries are positive/nonnegative. First, we study some generalities and become acquainted with two types of nonnegative matrices; irreducible and reducible. After exploring their characteristics we investigate and prove the two main theorems of this subject, namely Perron's and Perron-Frobenius' theorem. In short Perron's theorem from 1907 tells us that the spectral radius of a positive matrix is a simple eigenvalue of the matrix and that its eigenvector can be taken to be positive. In 1912, Georg Frobenius generalized Perron's results also to irreducible nonnegative matrices. The two theorems have a wide range of applications in both pure mathematics and practical matters. In real world scenarios, many measurements are nonnegative (length, time, amount, etc.) and so their mathematical formulations often relate to Perron-Frobenius theory. The theory's importance to linear dynamical systems, such as Markov chains, cannot be overstated; it determines when, and to what, an iterative process will converge. This result is in turn the underlying theory for the page-ranking algorithm developed by Google in 1998. We will see examples of all these applications in chapters four and five where we will be particularly interested in different types of Markov chains.  The theory in this thesis can be found in many books. Here, most of the material is gathered from Horn-Johnson [5], Meyer [9] and Shapiro [10]. However, all of the theorems and proofs are formulated in my own way and the examples and illustrations are concocted by myself, unless otherwise noted. / Det här är en litteraturstudie, inom linjär algebra, om positiva och icke-negativa matriser och deras speciella egenskaper. Vi säger att en matris eller en vektor är positiv/icke-negativ om alla dess element är positiva/icke-negativa. Inledningsvis går vi igenom några grundläggande begrepp och bekanta oss med två typer av icke-negativa matriser; irreducibla och reducibla. Efter att vi utforskat deras egenskaper så studerar vi och bevisar ämnets två huvudsatser; Perrons och Perron-Frobenius sats. Kortfattat så säger Perrons sats, från 1907, att spektralradien för en positiv matris är ett simpelt egenvärde till matrisen och att dess egenvektor kan tas positiv. År 1912 så generaliserade Georg Frobenius Perrons resultat till att gälla också för irreducibla icke-negativa matriser.  De två satserna har både många teoretiska och praktiska tillämpningar. Många verkliga scenarios har icke-negativa mått (längd, tid, mängd o.s.v) och därför relaterar dess matematiska formulering till Perron-Frobenius teori. Teorin är betydande även för linjära dynamiska system, såsom Markov-kedjor, eftersom den avgör när, och till vad, en iterativ process konvergerar. Det resultatet är i sin tur den underliggande teorin bakom algoritmen PageRank som utvecklades av Google år 1998. Vi kommer se exempel på alla dessa tillämpningar i kapitel fyra och fem, där vi speciellt intresserar oss för olika typer av Markov-kedjor. Teorin i den här artikeln kan hittas i många böcker. Det mesta av materialet som presenteras här har hämtats från Horn-Johnson [5], Meyer [9] och Shapiro [10]. Däremot är alla satser och bevis formulerade på mitt eget sätt och alla exempel, samt illustrationer, har jag skapat själv, om inget annat sägs.

L'application des mesures d'importance de type PageRank aux graphes du Web est le sujet de cette thèse, qui est divisée en deux parties. La première introduit une famille particulière de grands graphes, les graphes du Web. Elle commence par définir la notion de Web indexable, puis donne quelques considérations sur les tailles des portions de Web effectivement indexées. Pour finir, elle donne et utilise quelques constatations sur les structures que l'on peut observer sur les graphes induits par ces portions de Web. Ensuite, la seconde partie étudie en profondeur les mesures d'importance à la PageRank. Après un rappel sur la théorie des chaînes de Markov est présentée une classification originale des algorithmes de PageRank, qui part du modèle le plus simple jusqu'à prendre en compte toutes les spécificités liées aux graphes du Web. Enfin, de nouveaux algorithmes sont proposés. L'algorithme BackRank utilise un modèle alternatif de parcours du graphe du Web pour un calcul de PageRank plus rapide. La structure fortement clusterisée des graphes du Web permet quant à elle de décomposer le PageRank sur les sites Web, ce qui est réalisé par les algorithmes FlowRank et BlowRank.

Some of the theory of nonnegative matrices is first presented. The Perron-Frobenius theorem is highlighted. Some of the important linear algebraic methods of information retrieval are surveyed. Latent Semantic Indexing (LSI), which uses the singular value de-composition is discussed. The Hyper-Text Induced Topic Search (HITS) algorithm is next considered; here the power method for finding dominant eigenvectors is employed. Through the use of a theorem by Sinkohrn and Knopp, a modified HITS method is developed. Lastly, the PageRank algorithm is discussed. Numerical examples and MATLAB programs are also provided.

Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2014. / Neste trabalho apresentamos o algoritmo PageRank, usado pela Google para ordenar páginas no resultado de buscas. No primeiro capítulo descrevemos de maneira detalhada as estruturas matemáticas por trás do algoritmo, apresentando uma interpretação probabilística para suas estruturas e resultados. Para melhor entender a matemática do Google, nos capítulos 2 e 3 trabalhamos conceitos básicos de Cadeias de Markov, em especial a noção de medidas invariantes. / In the present work we present the PageRank algorithm, used by Google to sort the search results on the web. At the first chapter we describe in details the mathematical structures behind the algorithm, providing a probabilistic interpretation for it¿s structures and results. For a better understanding of Google¿s math, in chapters 2 and 3 we work on some basic concepts of Markov Chains, specially the notion of invariant measures.