Questions tagged [page-rank]

For questions about Google PageRank algorithm and other similar algorithms.

Filter by
Sorted by
Tagged with
0 votes
1 answer
43 views

Proof of the equivalence of PageRank and degree centrality in undirected connected graphs

Surprisingly, although this is stated everywhere in literature (usually citing surveys), there seems to be no recent source that explicitly proved this statement (there are, however, sources that ...
user avatar
-1 votes
1 answer
42 views

Teletrasporation step in Page Rank

I'm reading some definition of page rank, in particular how page rank work on the web graph. I'm a little bit confused about the definition of the teletransportation step. How I understand this phase ...
user avatar
0 votes
0 answers
15 views

Markov chain with edges described by random variables?

this is my first stack exchange question, would really appreciate patience if I am misusing the forum. I'm modeling a certain network as a (sparsely connected) Markov chain. Every node in the network ...
user avatar
  • 1
0 votes
1 answer
74 views

What is meant by the term: The matrix is "irreducible"

I came across the application of the Power Method used in determining the largest eigenvalue of a matrix in solving Google's PageRank algorithm and as a summary, the entire problem lies in finding the ...
user avatar
  • 343
0 votes
0 answers
66 views

When are Eigenvector centrality and PageRank equivalent?

The Eigenvector centrality for a graph $G = (V,E)$ is defined as the eigenvector corresponding to the larges eigenvalue of the adjacency matrix $\mathbf{A}$. The PageRank is a special case of ...
user avatar
  • 252
0 votes
0 answers
7 views

Optimize rank order survey experiment

What are methods for describing/comparing rank ordering of many items by multiple evaluators, where evaluators might not have the same items they are evaluating? For example: Suppose I have a dog show ...
user avatar
  • 131
0 votes
1 answer
52 views

Mathematical modelling of flu on an island

Given a flu on an island of 10000 people. Every day 15% of healthy people become infected and have a less illness (not require hospitalization), 12% of healthy people become infected and have a more ...
user avatar
  • 187
1 vote
1 answer
172 views

Explanation on Google’s PageRank is Webpages as Eigenvectors

Help understand what is the matrix A and the vector x discussed below. Mathematics for Machine Learning Example 4.9 Google uses the eigenvector corresponding to the maximal eigenvalue of a matrix A ...
user avatar
  • 235
1 vote
1 answer
122 views

network pagerank algorithm -- custom initial weights vs personalization

I am working with a graph and I want to compute the pagerank of its nodes. I want to emphasize some nodes more than others (and I use the networkx python package). I can think of two ways of doing ...
user avatar
  • 113
1 vote
0 answers
33 views

PageRank of the highest rank page (Directed graph)

Suppose Matrix of a directed graph is given as follows: $$A = \begin{pmatrix}0&0&\frac{1}{3}&\frac{1}{2}&0\\ \:\:\:0&0&0&\frac{1}{2}&\frac{1}{3}\\ \:\:\:0&\frac{1}{...
user avatar
  • 11.9k
1 vote
0 answers
80 views

PageRank sensitive calculation

𝐀 is the adj. matrix of a directed graph 𝐺. 𝐱 is the PageRank vector we calculate for a given 𝛼 (e.g. 0.85). 𝐶 is a subset of pages of 𝐺, for which we change some of the outgoing links. By 𝐱̃ ...
user avatar
0 votes
0 answers
50 views

Computing PageRank Vector

I have been given the adjacency matrix $$A = \begin{pmatrix} 0 & 1 & 0&1&1 \\ 1 & 0 &1&1& 0\\ 0& 1 &0&0&1 \\1&1&0&0&1 \\0&1&1&...
user avatar
  • 163
0 votes
0 answers
41 views

Show that the vector of ones, e, is an eigenvector of the Google matrix transpose

In the Google matrix where $$G=\alpha A+(1-\alpha)\frac{1}{n}ee^T$$ and $e$ is a vector of ones, how do I show that $e$ is the eigenvector of $G^T$ corresponding to the eigenvalue of 1 I need to ...
user avatar
  • 197
0 votes
1 answer
143 views

Show that columns of PageRank matrix sum to 1

Where the matrix A is replaced with $$G=\alpha A+(1-\alpha)\frac{1}{n}ee^T$$ Is it a sufficient condition a matrix is stochastic if the largest eigenvalue is 1? Or that in this case since A is ...
user avatar
  • 197
1 vote
1 answer
117 views

Calculating PageRank of a Google Matrix

Let $A$ the adjacency matrix of a Web Digraph, with $\{0,1\}$ entries. For sake of clarity, we assume that the matrix is irreducible and without full-zero rows (i.e. no leaf nodes in the graph) . ...
user avatar
1 vote
1 answer
373 views

Perron Frobenius Theorem modified

On this site I found a modified version of Perron Frobenius Theorem Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then: 1 is an eigenvalue of multiplicity one. 1 is ...
user avatar
  • 15
1 vote
0 answers
106 views

Connections between the randomness of the normal distribution and Textrank?

In a TED speech on 8:40 the mathematician said that: This algorithm uses the laws of mathematical randomness to determine automatically the most relevant web pages, in the same way as we used ...
user avatar
1 vote
0 answers
22 views

What is the relationship between the fluid in PageRank and web traffic?

PageRank can be interpreted as the amount of an imaginary fluid that collects at different nodes in a web graph. I would like to know what the relationship is between this imaginary fluid and actual ...
user avatar
  • 1,319
3 votes
1 answer
59 views

Ranking participants based on tiers and totals

I am trying to rank participants based on sets of data that I have. The data used is for a competition. In this competition, you can participate in X amount of events, at the end of the event you ...
user avatar
  • 33
2 votes
1 answer
441 views

Prove that the dimension of the eigenspace corresponding to the eigenvalue $\lambda=1$ of $H$ is at least the number of the clusters..

There are lots of ’islands’ in the world-wide-web, meaning clusters of websites that are not connected to other parts of the world wide web via hyperlinks. Let $H$ denote the column stochastic ...
user avatar
  • 1,370
0 votes
1 answer
356 views

Initial distribution of a Markov Chain (Power Model)

So, I was trying to model the PageRank algorithm based on the information of an article, and it said that in order to implement the power method, I needed the distribution of the process given by $$\...
user avatar
2 votes
0 answers
50 views

Calculate PageRank for small web

Calculate PageRank for: A links to B, B links to C and C links to B and C where the damping factor $\beta=0.8$ I have: $M=\begin{bmatrix} 0&0&\frac{1}{2} \\ 1&0&\frac{1}{2} \\ 0&...
user avatar
2 votes
1 answer
118 views

PageRank algorithm for grid graph

I am currently studying the PageRank algorithm. To find the ranks i know you have two options: Compute the result of a large linear system Apply the surfer concept (like Markov chains) I have this ...
user avatar
4 votes
1 answer
123 views

Why is the matrix $(I - A)$ theoretically singular?

I've the following Matlab code to compute the eigenvector using the inverse iteration (or power) method: A = p * G * D + delta; x = (I − A) \ e; x = x / sum(x); ...
user avatar
2 votes
1 answer
1k views

Understanding PageRank as an eigenvalue problem

In the book "A first course in numerical methods" by U. Arscher and C. Greif, chapter 8 on "Eingenvalues and singular values", example 8.1, we have: Given a network linkage graph ...
user avatar
1 vote
1 answer
190 views

Rewriting the simplified google algorithm in linear algebra form

I have the expression for the rank ($x_{i}$) of a page $i$ in an internet with $n$ sites, each site contains $n_{i}$ links to other sites and is linked to by the pages $L_{i}\subset\{1,\dots,n\}$. The ...
user avatar