Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do weighted edges affect PageRank in networkx?

Tags:

I'm playing around with networkx (graph library in python) and I found documentation saying the PageRank algorithm takes edge weights into account when scoring, but I was wondering if larger edge weights were better or lower weights better?

like image 798
Lostsoul Avatar asked Feb 03 '12 22:02

Lostsoul


People also ask

How do you add weighted edges on Networkx?

Add all the edges in ebunch as weighted edges with specified weights. Each edge given in the list or container will be added to the graph. The edges must be given as 3-tuples (u,v,w) where w is a number.

What is damping factor in PageRank?

Damping factor. The PageRank theory holds that an imaginary surfer who is randomly clicking on links will eventually stop clicking. The probability, at any step, that the person will continue is a damping factor d.

What is PageRank in Networkx?

PageRank computes a ranking of the nodes in the graph G based on the structure of the incoming links. It was originally designed as an algorithm to rank web pages.

What is personalized PageRank?

Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node s and a target node t, the PPR value \pi(s,t) represents the probability that a random walk from s terminates at t, and thus indicates the bidirectional importance between s and t.


1 Answers

Shortly, large weights are better for incoming nodes.

PageRank works on a directed weighted graph. If page A has a link to page B, then the score for B goes up, i.e. the more input the page B (node) have, the higher is its score.

Wikipedia article on PageRank for further details.

Edit: let's make an experiment. Create a directed graph with 3 nodes and two directed edges with equal weights.

import networkx as nx D=nx.DiGraph() D.add_weighted_edges_from([('A','B',0.5),('A','C',0.5)]) print nx.pagerank(D)  >> {'A': 0.259740259292235, 'C': 0.3701298703538825, 'B': 0.3701298703538825} 

Now, increase the weight of the (A,C) edge:

D['A']['C']['weight']=1 print nx.pagerank(D)      >> {'A': 0.259740259292235, 'C': 0.40692640737443164, 'B': 0.3333333333333333} 

As you see, the node C got higher score with increasing weight of the incoming edge.

like image 112
Max Li Avatar answered Sep 23 '22 13:09

Max Li