https://www.mdu.se/

PageRank update refers to the process of computing new PageRank values after change(s) (addition or removal of links/vertices) has occurred in real life networks. The purpose of the updating is to avoid recalculating the values from scratch. To efficiently carry out the update, we consider PageRank as the expected number of visits to target vertex if multiple random walks are performed, starting at each vertex once and weighing each of these walks by a weight value. Hence, it might be looked at as updating non-normalised PageRank. In the proposed approach, a scaled adjacency matrix is sequentially updated after every change and the levels of the vertices being updated as well. This enables sets of internal and sink vertices dependent on their roots or parents, thus vector-vector product can be performed sequentially since there are no infinite steps from one vertex to the other.

A PageRank update refers to the process of computing new PageRank valuesafter a change(s) (addition or removal of links/vertices) has occurred in real-lifenetworks. The purpose of updating is to avoid re-calculating the values from scratch.To efficiently carry out the update, we consider PageRank to be the expected numberof visits to a target vertex if multiple random walks are performed, starting at eachvertex once and weighing each of these walks by a weight value. Hence, it mightbe looked at as updating a non-normalized PageRank. We focus on networks of treegraphs and propose an approach to sequentially update a scaled adjacency matrix afterevery change, as well as the levels of the vertices. In this way, we can update thePageRank of affected vertices by their corresponding levels.

In this article, we study how PageRank can be updated in an evolving tree graph. We are interested in finding how ranks of the graph can be updated simultaneously and effectively using previous ranks without resorting to iterative methods such as the Jacobi or Power method. We demonstrate and discuss how PageRank can be updated when a leaf is added to a tree, at least one leaf is added to a vertex with at least one outgoing edge, an edge added to vertices at the same level and forward edge is added in a tree graph. The results of this paper provide new insights and applications of standard partitioning of vertices of the graph into levels using breadth-first search algorithm. Then, one determines PageRanks as the expected numbers of random walk starting from any vertex in the graph. We noted that time complexity of the proposed method is linear, which is quite good. Also, it is important to point out that the types of vertex play essential role in updating of PageRank.

Summary Updating PageRank refers to a process of computing new PageRank values after changes have occurred in a graph. The main goal of the updating is to avoid recalculating the values from scratch. This chapter focuses on updating PageRank of an evolving tree graph when a vertex and an edge are added sequentially. It describes how to maintain level structures when a cycle is created and investigates the practical and theoretical efficiency to update PageRanks for an evolving graph with many cycles. The chapter discusses the convergence of the power method applied to stochastic complement of Google matrix when a feedback vertex set is used. It also demonstrates that the partition by feedback vertex set improves asymptotic convergence of power method in updating PageRank in a network with cyclic components.

Bioinformatics, internet search engines (web pages) and social networks are some of the examples with large and high sparsity matrices. For some of these systems, only the actual ranks of the solution vector is interesting rather than the vector itself. In this case, it is desirable that the stopping criterion reflects the error in ranks rather than the residual vector that might have a lower convergence. This chapter evaluates stopping criteria on Jacobi, successive over relaxation (SOR) and power series iterative schemes. Numerical experiments were performed and results show that Kendall's correlation coefficient gives good stopping criterion of ranks for linear system of equations. The chapter focuses on the termination criterion as means of obtaining good ranks. It outlines some studies carried out on stopping criteria in solving the linear system.

This chapter is devoted to studies of perturbed Markov chains, commonly used for the description of information networks. In such models, the matrix of transition probabilities for the corresponding Markov chain is usually regularized by adding aspecial damping matrix, multiplied by a small damping (perturbation) parameter ε. In this chapter, we present the results of detailed perturbation analysis of Markov chains with damping component and numerical experiments supporting and illustrating the results of this perturbation analysis.

We study the double-mean-reverting model by Gatheral. Our previous results concerning the asymptotic expansion of the implied volatility of a European call option, are improved up to order 3, that is, the error of the approximation is ultimately smaller that the 1.5th power of time to maturity plus the cube of the absolute value of the difference between the logarithmic security price and the logarithmic strike price.

The double-mean-reverting model by Gatheral [1] is motivated by empirical dynamics of the variance of the stock price. No closed-form solution for European option exists in the above model. We study the behaviour of the implied volatility with respect to the logarithmic strike price and maturity near expiry and at-the- money. Using the method by Pagliarani and Pascucci [6], we calculate explicitly the first few terms of the asymptotic expansion of the implied volatility within a parabolic region.

The double-mean-reverting model by Gatheral is motivated by empirical dynamics of the variance of the stock price. No closed-form solution for European option exists in the above model. We study the behaviour of the implied volatility with respect to the logarithmic strike price and maturity near expiry and at-the-money. Using the method by Pagliarani and Pascucci, we calculate explicitly the first few terms of the asymptotic expansion of the implied volatility within a parabolic region.

In graph theory, centrality measures are very crucial in ranking vertices of the graph in order of their importance. Alpha and eigenvector centralities are some of the highly placed centrality measures applied especially in social network analysis, disease diffusion networks and mechanical infrastructural developments. In this study we focus on recalculating alpha and eigenvector centralities using graph partitioning techniques. We write an algorithm for partitioning, sorting and efficiently computing these centralities for a graph. We then numerically demonstrate the technique on some sample small-sized networks to recalculate the two centrality measures

When working with a network, it is often of interest to locate the “most important”nodes in the network. A common way to do this is by using some graph centralitymeasures. Since what constitutes as an important node varies from one network toanother, or even in applications on the same network, there is a large number ofdifferent centrality measures proposed in the literature. Due to the large amount ofdifferent centrality measures proposed in different fields, there is also a large amountof very similar or equivalent centrality measures (in the sense that they give the sameranks). In this chapter, we focus on the centrality measures based on powers of theadjacency matrix and those based on random walk. In this case, we show how someof these centrality measures are related, as well as their lazy variants.We will performsome experiments to demonstrate the similarities between the centrality measures.

When working with a network it is often of interest to locate the "most important" nodes in the network. A common way to do this is using some graph centrality measures. Since what constitutes an important node is different between different networks or even applications on the same network there is a large amount of different centrality measures proposed in the literature. Due to the large amount of different centrality measures proposed in different fields, there is also a large amount very similar or equivalent centrality measures in the sense that they give the same ranks. In this paper we will focus on centrality measures based on powers of the adjacency matrix or similar matrices and those based on random walk in order to show how some of these are related and can be calculated efficiently using the same or slightly altered algorithms.

PageRank is an algorithm for ranking web pages. It is the first and best known webgraph-based algorithm in the Google search engine. The algorithm is simple, robust and reliable to measure the importance of web pages. This chapter presents a comparative review of three variants of PageRank, namely ordinary PageRank (introduced by Brin and Page as a measure of importance of a web page), lazy PageRank and random walk with backstep PageRank. It compares the variants in terms of their convergence and consistency in rank scores for different graph structures with reference to PageRank’s parameters, damping factor and backstep parameter. The chapter also shows that ordinary PageRank can be formulated from the other two variants by some proportionality relationships.

PageRank was initially defined by S. Brin and L. Page for the purpose of measuring the importance of web pages (nodes) based on the structure of links between them. Due to existence of diverse methods of random walk on the graph, variants of PageRank now exists. They include traditional (or normal) PageRank due to normal random walk and Lazy PageRank due to lazy random walk on a graph. In this article, we establish how the two variants of PageRank changes when complete graphs are connected to a line of nodes whose links between the nodes are in one direction. Explicit formulae for the two variants of PageRank are presented. We have noted that the ranks on a line graph are the same except their numerical values which differ. Further, we have observed that both normal random walk and lazy random walk on complete graphs spend almost the same time at each node.

PageRank is a widely-used hyperlink-based algorithm to estimate the relative importance of nodes in networks [11]. Since many real world networks are large sparse networks, this makes efficient calculation of PageRank complicated. Moreover, one needs to escape from dangling effects in some cases as well as slow convergence of the transition matrix. Primitivity adjustment with a damping (perturbation) parameter ε(0,ε₀] (for fixed ε₀ 0.15) is one of the essential procedure that is known to ensure convergence of the transition matrix [24]. If ε is large, the transition matrix looses information due to shift of information to teleportation matrix [27]. In this paper, we formulate PageRank problem as the first and second order Markov chains perturbation problem. Using numerical experiments, we compare convergence rates for the two problems for different values of ε on different graph structures and investigate the difference in ranks for the two problems.

PageRank is a widely used hyperlink-based algorithm for estimating the relative importance of nodes in networks. Since many real-world networks are large sparse networks, efficient calculation of PageRank is complicated. Moreover, we need to overcome dangling effects in some cases as well as slow convergence of the transition matrix. Primitivity adjustment with a damping (perturbation) parameter is one of the essential procedures known to ensure convergence of the transition matrix. If the perturbation parameter is not small enough, the transition matrix loses information due to the shift of information to the teleportation matrix. We formulate the PageRank problem as a first- and second-order Markov chains perturbation problem. Using numerical experiments, we compare convergence rates for different values of perturbation parameter on different graph structures and investigate the difference in ranks for the two problems.

PageRank was initially defined by S. Brin and L. Page for the purpose of ranking homepages (nodes) based on the structure of links between these pages. Studies has shown that PageRank of a graph changes with changes in the structure of the graph. In this article, we examine how the PageRank changes when two or more outside nodes are connected to a line directed graph. We also look at the PageRank of a graph resulting from connecting a line graph to two complete graphs. In this paper we demonstrate that both the probability (or random walk on a graph) and blockwise matrix inversion approaches can be used to determine explicit formulas for the PageRanks of simple networks.

In different applications (i.e., information retrieval, filteringor analysis), it is useful to detect similar terms and to provide the possibilityto use them jointly. Clustering of terms is one of the methods whichcan be exploited for this. In our study, we propose to test three methodsdedicated to the clustering of terms (hierarchical ascendant classification,Radius and maximum), to combine them with the semantic distance algorithmsand to compare them through the results they provide whenapplied to terms from the pharmacovigilance area. The comparison indicatesthat the non disjoint clustering (Radius and maximum) outperformthe disjoint clusters by 10 to up to 20 points in all the experiments.

This thesis is dedicated to the use of graph based methods applied to ranking problems on the Web-graph and applications in natural language processing and biology.

Chapter 2-4 of this thesis is about PageRank and its use in the ranking of home pages on the Internet for use in search engines. PageRank is based on the assumption that a web page should be high ranked if it is linked to by many other pages and/or by other important pages. This is modelled as the stationary distribution of a random walk on the Web-graph.

Due to the large size and quick growth of the Internet it is important to be able to calculate this ranking very efficiently. One of the main topics of this thesis is how this can be made more efficiently, mainly by considering specific types of subgraphs and how PageRank can be calculated or updated for those type of graph structures. In particular we will consider the graph partitioned into strongly connected components and how this partitioning can be utilized.

Chapter 5-7 is dedicated to graph based methods and their application to problems in Natural language processing. Specifically given a collection of texts (corpus) we will compare different clustering methods applied to Pharmacovigilance terms (5), graph based models for the identification of semantic relations between biomedical words (6) and modifications of CValue for the annotation of terms in a corpus.

In Chapter 8-9 we look at biological networks and the application of graph centrality measures for the identification of cancer genes. Specifically in (8) we give a review over different centrality measures and their application to finding cancer genes in biological networks and in (9) we look at how well the centrality of vertices in the true network is preserved in networks generated from experimental data.

In this article we will take a look at a variant of the PageRank algorithminitially used by S. Brinn and L. Page to rank homepages on the Internet. The aim ofthe article is to see how we can use the topological structure of the graph to speed upcalculations of PageRank without doing any additional approximations. We will seethat by considering a non-normalized version of PageRank it is easy to see how wecan handle dierent types of vertices or strongly connected components in the graphmore eciently. Using this we propose two PageRank algorithms, one similar to theLumping algorithm proposed by Qing et al which handles certain types of verticesfaster and last another PageRank algorithm which can handle more types of verticesas well as strongly connected components more eectively. In the last sections we willlook at some specic types of components as well as verifying the time complexity ofthe algorithm.

Clustering of data into groups of similar objects plays an important part when analysing many types of data especially when the datasets are large as they often are in for example bioinformatics social networks and computational linguistics. Many clustering algorithms such as K-means and some types of hierarchical clustering need a number of centroids representing the 'center' of the clusters. The choice of centroids for the initial clusters often plays an important role in the quality of the clusters. Since a data point with a high centrality supposedly lies close to the 'center' of some cluster this can be used to assign centroids rather than through some other method such as picking them at random. Some work have been done to evaluate the use of centrality measures such as degree betweenness and eigenvector centrality in clustering algorithms. The aim of this article is to compare and evaluate the usefulness of a number of common centrality measures such as the above mentioned and others such as PageRank and related measures.

PageRank was initially developed by S. Brinn and L. Page in 1998 to rank homepages on the Internet using the stationary distribution of a Markov chain created using the web graph. Due to the large size of the web graph and many other real worldnetworks fast methods to calculate PageRank is needed and even if the original way of calculating PageRank using a Power iterations is rather fast, many other approaches have been made to improve the speed further. In this paper we will consider the problem of recalculating PageRank of a changing network where the PageRank of a previous version of the network is known. In particular we will consider the special case of adding or removing edges to a single vertex in the graph or graph component

In this article we will look at the PageRank algorithm used to rank nodes in a network. While the method was originally used by Brin and Page to rank home pages in order of “importance”, since then many similar methods have been used for other networks such as financial or P2P networks. We will work with a non-normalised version of the usual PageRank definition which we will then generalise to enable better options, such as adapting the method or allowing more types of data. We will show what kind of effects the new options creates using examples as well as giving some thoughts on what it can be used for. We will also take a brief look at how adding new connections between otherwise unconnected networks can change the ranking.

In this article we will present a graph partitioning algorithm which partitions a graphinto two different types of components: the well known ‘strongly connected components’ as well as another type of components we call ‘connected acyclic component’. We will give analgorithm based on Tarjan’s algorithm for finding strongly connected components used to find such a partitioning. We will also show that the partitioning given by the algorithm is unique and that the underlying graph can be represented as a directed acyclic graph (similar to a pure strongly connected component partitioning). In the second part we will show how such an partitioning of a graph can be used to calculate PageRank of a graph effectively by calculating PageRank for different componentson the same ‘level’ in parallel as well as allowing for the use of different types of PageRankalgorithms for different types of components. To evaluate the method we have calculated PageRank on four large example graphs and compared it with a basic approach, as well as our algorithm in a serial as well as parallel implementation.

In this article we will look at a variation of the PageRank algorithmoriginally used by L. Page and S. Brin to rank home pages on the Web. Wewill look at a non-normalized variation of PageRank and show how this version ofPageRank relates to a random walk on a graph. The article has its main focus inunderstanding the behavior of the ranking depending on the structure of the graphand how the ranking changes as the graph change. More specic we will look atN-partite graphs and see that by considering a random walk on the graph we cannd explicit formulas for PageRank of the vertices in the graph. Both the case withuniform and non-uniform personalization vector are considered.

In this article we will look at the PageRank algorithm used as part of the ranking process of different Internet pages in search engines by for example Google. This article has its main focus in the understanding of the behavior of PageRank as the system dynamically changes either by contracting or expanding such as when adding or subtracting nodes or links or groups of nodes or links. In particular we will take a look at link structures consisting of a line of nodes or a complete graph where every node links to all others. We will look at PageRank as the solution of a linear system of equations and do our examination in both the ordinary normalized version of PageRank as well as the non-normalized version found by solving corresponding linear system. We will show that using two different methods we can find explicit formulas for the PageRank of some simple link structures.

The focus of this article is the PageRank algorithm originally defined by S. Brin and L. Page as the stationary distribution of a certain random walk on a graph used to rank homepages on the Internet. We will attempt to get a better understanding of how PageRank changes after you make some changes to the graph such as adding or removing edge between otherwise disjoint subgraphs. In particular we will take a look at link structures consisting of a line of nodes or a complete graph where every node links to all others and different ways to combine the two. Both the ordinary normalized version of PageRank as well as a non-normalized version of PageRank found by solving corresponding linear system will be considered. We will see that it is possible to find explicit formulas for the PageRank in some simple link structures and using these formulas take a more in-depth look at the behavior of the ranking as the system changes.

In this work it is described how a partitioning of a graph into components can be used to calculate PageRank in a large network and how such a partitioning can be used to re-calculate PageRank as the network changes. Although considered problem is that of calculating PageRank, it is worth to note that the same partitioning method could be used when working with Markov chains in general or solving linear systems as long as the method used for solving a single component is chosen appropriately. An algorithm for calculating PageRank using a modified partitioning of the graph into strongly connected components is described. Moreover, the paper focuses also on the calculation of PageRank in a changing graph from two different perspectives, by considering specific types of changes in the graph and calculating the difference in rank before and after certain types of edge additions or removals between components. Moreover, some common specific types of graphs for which it is possible to find analytic expressions for PageRank are considered, and in particular the complete bipartite graph and how PageRank can be calculated for such a graph. Finally, several open directions and problems are described.

PageRank was first defined by S. Brinn and L. Page in 1998 in order to rank homepages on the Internet by ranking pages according to the stationary distribution of a random walk on the web graph. While the original way to calculate PageRank is fast, due to the huge size and growth of the web there have been many attempts at improving upon the calculation speed of PageRank through various means. In this article we will look at a slightly different but equally important problem, namely how to improve the calculation of PageRank in a changing network where PageRank of an earlier stage of the network is available. In particular we consider two types of changes in the graph, the change in rank after changing the personalization vector used in calculating PageRank as well as added or removed edges between different strongly connected components in the network.

PageRank was first defined by S. Brinn and L. Page in 1998 in order to rank homepages on the Internet for use in search engines using a random walk on the web graph. While the original way to calculate PageRank is fast, due to the huge size and growth of the web there have been many attempts at improving upon the calculation speed of PageRank through various means. In this article we will look at a slightly dierent but equally important problem, namely how to improve the calculation speed of PageRank in a changing network where PageRank of an earlier stage of the network is available. In particular we consider two types of changes in the graph, the change in rank after changing the personalization vector used in calculating PageRank as well as added or removed edges between dierent strongly connected components in the network.

The acquisition of semantic resources and relations is an important task for several applications, such as query expansion, information retrieval and extraction, machine translation. However, their validity should also be computed and indicated, especially for automatic systems and applications. We exploit the compositionality based methods for the acquisition of synonymy relations and of indicators of these synonyms. We then apply pagerank-derived algorithm to the obtained semantic graph in order to filter out the acquired synonyms. Evaluation performed with two independent experts indicates that the quality of synonyms is systematically improved by 10 to 15% after their filtering.

Term extraction methods based on linguistic rules have been proposed to help the terminology building from corpora. As they face the difficulty of identifying the relevant terms among the noun phrases extracted, statistical measures have been proposed. However, the term selection results may depend on corpus and strong assumptions reflecting specific terminological practice. We tackle this problem by proposing a parametrised C-Value which optimally considers the length and the syntactic roles of the nested terms thanks to a genetic algorithm. We compare its impact on the ranking of terms extracted from three corpora. Results show average precision increased by 9% above the frequency-based ranking and by 12% above the C-Value-based ranking.

Background: The inflammatory responses are central components of diseases associated with particulate matter (PM) exposure, including systemic diseases such as cardiovascular diseases (CVDs). The aim of this study was to determine if exposure to PM, including respirable dust or quartz in the iron foundry environment mediates systemic inflammatory responses, focusing on the NLRP3 inflammasome and novel or established inflammatory markers of CVDs. Methods: The exposure to PM, including respirable dust, metals and quartz were determined in 40 foundry workers at two separate occasions per worker. In addition, blood samples were collected both pre-shift and post-shift and quantified for inflammatory markers. The respirable dust and quartz exposures were correlated to levels of inflammatory markers in blood using Pearson, Kendall τ and mixed model statistics. Analyzed inflammatory markers included: 1) general markers of inflammation, including interleukins, chemokines, acute phase proteins, and white blood cell counts, 2) novel or established inflammatory markers of CVD, such as growth/differentiation factor-15 (GDF-15), CD40 ligand, soluble suppressor of tumorigenesis 2 (sST2), intercellular/vascular adhesion molecule-1 (ICAM-1, VCAM-1), and myeloperoxidase (MPO), and 3) NLRP3 inflammasome-related markers, including interleukin (IL)-1β, IL-18, IL-1 receptor antagonist (IL-1Ra), and caspase-1 activity. Results: The average respirator adjusted exposure level to respirable dust and quartz for the 40 foundry workers included in the study was 0.65 and 0.020 mg/m3, respectively. Respirable quartz exposure correlated with several NLRP3 inflammasome-related markers, including plasma levels of IL-1β and IL-18, and several caspase-1 activity measures in monocytes, demonstrating a reverse relationship. Respirable dust exposure mainly correlated with non-inflammasome related markers like CXCL8 and sST2. Conclusions: The finding that NLRP3 inflammasome-related markers correlated with PM and quartz exposure suggest that this potent inflammatory cellular mechanism indeed is affected even at current exposure levels in Swedish iron foundries. The results highlight concerns regarding the safety of current exposure limits to respirable dust and quartz, and encourage continuous efforts to reduce exposure in dust and quartz exposed industries. 

In this paper we apply data-mining techniques to a classication problemon actual electricity consumption data from 350 Swedish households. Morespecically we use measurements of hourly electricity consumption during one monthand t classication models to the given data. The goal is to classify and later predict whether the building type of a specic household is an apartmentor a detached house. This classication/prediction problem becomes important ifone has a consumption time series for a household with unknown building type. Tocharacterise each household, we compute from the data some selected statistical attributesand also the load prole throughout the day for that household. The most important task here is to select a good representative set of feature variables, whichis solved by ranking the variable importance using technique of random forest. Wethen classify the data using classication tree method and linear discriminant analysis.The predictive power of the chosen classication models is plausible.

In this paper we apply data-mining techniques to customer classification and clustering tasks on actual electricity consumption data from 350 Swedish households. For the classification task we classify households into different categories based on some statistical attributes of their energy consumption measurements. For the clustering task, we use average daily load diagrams to partition electricity-consuming households into distinct groups. The data contains electricity consumption measurements on each 10-minute time interval for each light source and electrical appliance. We perform the classification and clustering tasks using four variants of processeddata sets corresponding to the 10-minute total electricity consumption aggregated from all electrical sources, the hourly total consumption aggregated over all 10-minute intervals during that clock hour, the total consumption over each four-hour intervals and finally the daily total consumption. The goal is to see if there are any differences in using data sets of various frequency levels. We present the comparison results and investigate the added value of the high-frequency measurements, for example 10-minute measurements, in terms of its influence on customer clustering and classification.

Cubature is an effective way to calculate integrals in a finite dimensional space. Extending the idea of cubature to the infinite-dimensional Wiener space would have practical usages in pricing financial instruments. In this paper, we calculate and use cubature formulae of degree 5 and 7 on Wiener space to price European options in the classical Black–Scholes model. This problem has a closed form solution and thus we will compare the obtained numerical results with the above solution. In this procedure, we study some characteristics of the obtained cubature formulae and discuss some of their applications to pricing American options.

Perturbed Markov chains are popular models for description of information networks. Insuch models, the transition matrix P₀ of an information Markov chain is usually approximated bymatrix Pε = (1-ε)P₀+εD, where D is a so-called damping stochastic matrix with identical rowsand all positive elements, while ε [0; 1] is a damping (perturbation) parameter. Using procedure ofarticial regeneration for the perturbed Markov chain η_ε,n with the matrix of transition probabilities P_ε , and coupling methods, we get ergodic theorems, in the form of asymptotic relations for P_ε,ij (n) =P_i {η_ε,n =j}, as n  and ε0, and explicit upper bounds for the rates of convergence in such theorems. In particular, the most dicult case of the model with singular perturbations, wherethe phase space of the unperturbed Markov chain η0_,n split in several closed classes of communicativestates and possibly a class of transient states, is investigated.

Perturbed Markov chains are popular models for description of information networks. In such models, the transition matrix P₀ of an information Markov chain is usually approximated by matrix P^_ε = (1 - ε) P₀ + ε D, where D is a so-called damping stochastic matrix with identical rows and all positive elements, while ε is a damping (perturbation) parameter. We perform a detailed perturbation analysis for stationary distributions of such Markov chains, in particular get effective explicit series representations for the corresponding stationary distributions π_ε, upper bounds for the deviation |π_ε- π₀ |, and asymptotic expansions for πε with respect to the perturbation parameter ε.

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter epsilon. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems forn-step transition probabilities, as well as ergodic theorems in triangular array mode.

Perturbed Markov chains are popular models for description of information networks. In such models, the transition matrix P0 of an information Markov chain is usually approximated by matrix P_ε = (1 − ε)P₀ + εD, where D is a so-called damping stochastic matrix with identical rows and all positive elements, while ε ∈ [0, 1] is a damping (perturbation) parameter. Using procedure of artificial regeneration for the perturbed Markov chain ηε,n, with the matrix of transition probabilities P_ε, and coupling methods, we get ergodic theorems, in the form of asymptotic relations for p_ε,ij (n) = P_i {η_ε,n = j} as n → ∞ and ε → 0, and explicit upper bounds for the rates of convergence in such theorems. In particular, the most difficult case of the model with singular perturbations, where the phase space of the unperturbed Markov chain η₀,n split in several closed classes of communicative states and possibly a class of transient states, is investigated.

PageRank was first defined by S. Brin and L. Page in 1998 in order to rank home pages on the Internet by ranking pages according to the stationary distribution of a random walk on the web graph. While the original way to calculate PageRank is fast, due to the huge size and growth of the web there have been many attempts at improving upon the calculation speed of PageRank through various means. In this article we will look at a slightly different but equally important problem, namely how to improve the calculation of PageRank in a changing network where PageRank of an earlier stage of the network is available. In particular, we consider two types of changes in the graph, the change in rank after changing the personalization vector used in calculating PageRank as well as added or removed edges between different strongly connected components in the network.

Graph centralities are often used to prioritize disease genes in transcrip-tional regulatory networks. Studies on small networks of experimentally validatedinteractions emphasize the general validity of this approach and extensions of suchndings have recently also been proposed for networks inferred from expression data.However, due to the noise inherent to expression data, it is largely unknown howwell centralities are preserved in such networks. Specically, while previous stud-ies have evaluated the performance of inference methods on synthetic expression, ithas yet to be established how the choice of method can aect individual centralitiesin the network. Here we compare two centralities between reference networks andnetworks inferred from corresponding simulated expression data using a number ofrelated methods. The results indicate that there exists only a modest conservationof centrality measures for the used inference methods. In conclusion, caution shouldbe exercised when inspecting centralities in reverse-engineered networks and furtherwork will be required to establish the use of such networks for prioritizing genes.

Current cancer therapies including surgery, radiotherapy and chemotherapy are often plagued by high failure rates. Designing more targeted and personalized treatment strategies requires a detailed understanding of druggable tumor drivergenes. As a consequence, the detection of cancer driver genes has evolved to a critical scientific field integrating both high-through put experimental screens as well as computational and statistical strategies. Among such approaches, network based prediction tools have recently been accentuated and received major focus due to their potential to model various aspects of the role of cancer genes in a biological system. In this chapter, we focus on how graph centralities obtained from biological networks have been used to predict cancer genes. Specifically, we start by discussing the current problems in cancer therapy and the reasoning behind using network based cancer gene prediction, followed by an outline of biological networks, their generation and properties. Finally, we review major concepts, recent results as well as future challenges regarding the use of graph centralities in cancer gene prediction.

Graph centralities are commonly used to identify and prioritize disease genes in transcriptional regulatory networks. Studies on small networks of experimentally validated protein-protein interactions underpin the general validity of this approach and extensions of such findings have recently been proposed for networks inferred from gene expression data. However, it is largely unknown how well gene centralities are preserved between the underlying biological interactions and the networks inferred from gene expression data. Specifically, while previous studies have evaluated the performance of inference methods on synthetic gene expression, it has not been established how the choice of inference method affects individual centralities in the network. Here, we compare two gene centrality measures between reference networks and networks inferred from corresponding simulated gene expression data, using a number of commonly used network inference methods. The results indicate that the centrality of genes is only moderately conserved for all of the inference methods used. In conclusion, caution should be exercised when inspecting centralities in reverse-engineered networks and further work will be required to establish the use of such networks for prioritizing disease genes.

The prioritization of genes based on their centrality in biological networkshas emerged as a promising technique for the prediction of phenotype related genes.A number of methods have been developed to derive one such type of network, i.e.transcriptional regulatory networks, from expression data. In order to reliably prioritizegenes from such networks, it is crucial to investigate how well the inferencemethods reconstruct the centralities that exist in the true biological system. We haverecently reported that the correlation of centrality rankings between reference andinferred networks is only modest when using an unbiased inference approach. In thisstudy we extend on these results and demonstrate that the correlation remains modestalso when using a biased inference utilizing a priori information about transcriptionfactors. However, we show further that despite this lack of a strong correlation, theinferred networks still allow a signicant prediction of genes with high centralities inthe reference networks.

Retroviral tagging represents an important technique, which allows researchers to screen for candidate cancer genes. The technique is based on the integration of retroviral sequences into the genome of a host organism, which might then lead to the artificial inhibition or expression of proximal genetic elements. The identification of potential cancer genes in this framework involves the detection of genomic regions (common insertion sites; CIS) which contain a number of such viral integration sites that is greater than expected by chance. During the last two decades, a number of different methods have been discussed for the identification of such loci and the respective techniques have been applied to a variety of different retroviruses and/or tumor models. We have previously established a retrovirus driven brain tumor model and reported the CISs which were found based on a Monte Carlo statistics derived detection paradigm. In this study, we consider a recently proposed alternative graph theory based method for identifying CISs and compare the resulting CIS landscape in our brain tumor dataset to those obtained when using the Monte Carlo approach. Finally, we also employ the graph-based method to compare the CIS landscape in our brain tumor model with those of other published retroviral tumor models.