What happnes if we use PageRank and HITS on a undirected graph ?

[Eugene Y.E]

Hi all, 

I was checking the networkx's documentation and noticed that PageRank and HITS algorithm are meant to work no directed graphs only.

However, I tried to use a undirected graph ( with max_iter=10000) and managed to receive values for PageRank and HITS.

I was wondering if the meaning of the PageRank and HITS will be changed in this case ? If so, how different will it be than using PageRank and HITS for a directed graph ?

Best.

[Ben Edwards]

Page rank is calculated by treating the undirected graph as a directed graph, that is it makes each edge bidirectional. It looks like the hits algorithm only relies on the neighbors of a node, so should be applicable to directed and undirected graphs.

Ben

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/0VgeRtblzl8J.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[Eugene Y.E]

Hi Ben, 

I was wondering if there's any theoretical stuff that backs it up?

As in using PageRank and HITS on undirected graph ?

Cos i was checking the PageRank paper ( http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf ) and HITS paper ( http://www.cs.cornell.edu/home/kleinber/auth.pdf ) 

and it appears that its meant to run on directed graphs.

So does that mean that the implementation of PageRank and HITS has a different meaning 

as per PageRank ( http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf ) and HITS  ( http://www.cs.cornell.edu/home/kleinber/auth.pdf )  ?

Thanks again!

On Sunday, March 18, 2012 8:01:58 PM UTC+8, Ben Edwards wrote:

Page rank is calculated by treating the undirected graph as a directed graph, that is it makes each edge bidirectional. It looks like the hits algorithm only relies on the neighbors of a node, so should be applicable to directed and undirected graphs.

Ben

Hi all, 

I was checking the networkx's documentation and noticed that PageRank and HITS algorithm are meant to work no directed graphs only.

However, I tried to use a undirected graph ( with max_iter=10000) and managed to receive values for PageRank and HITS.

I was wondering if the meaning of the PageRank and HITS will be changed in this case ? If so, how different will it be than using PageRank and HITS for a directed graph ?

Best.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/0VgeRtblzl8J.

To post to this group, send email to networkx-discuss@googlegroups.com.
To unsubscribe from this group, send email to networkx-discuss+unsubscribe@googlegroups.com.

[Tyler Rush]

Most likely my naivety with uses of PageRank (I've never used it) results in this question, but what is your use of PageRank for an undirected graph, since hyper links for webpages are naturally directional? Again, I don't know much about the uses of PageRank.

In the case of networkx's PageRank alg. there is no change in meaning that you are asking about because the algorithm doesn't actually run on an undirected graph. As a first step, the networkx PageRank implementation (https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/link_analysis/pagerank_alg.py) deep-copys the graph into a directed one with the to_directed() method, like so:

if not G.is_directed():

    D = G.to_directed()

else

    D = G

i.e. every undirected edge u--v gets copied (with data) to two separate directed edges u->v and v->u. So for networkx PageRank, there is no alternate meaning for undirected graphs as the algorithm doesn't actually ever perform on an undirected graph. That being said, your question boils down to "What are the implications of converting every undirected edge to two directional edges in the domain of PageRank". I never thought about it, but it sounds like a logical question to ask oneself after analyzing PageRank for directed graphs, in which case Google is your friend.

The code for the networkx HITS algorithm wasn't as easily interpretable to me, so I'll leave it up to someone else to help you on that one.

~ Tyler

To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/D7PDVlrv7YcJ.

To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.

[Marcel Blattner]

Hi there

The undirected case is simply when you have directions in both ways. Say, when webpage A points to B then B points to A as well. You can easily imagine, that this symmetric case does not happen always in the web. So, yes the web-network is surely not symmetric in terms of link-directions. But applying PageRank in the case of an undirected network works like in an undirected case. You just stick on a special network topology.

Cheers

Marcel

Dr. Marcel Blattner

blat...@gmail.com

[Eugene Y.E]

Wow, 

thanks Marcel.

I was wondering would the same apply to HITS ?

Best.

Dr. Marcel Blattner

blat...@gmail.com

[Eugene Y.E]

Hi Tyler, 

I'm using PageRank on social relationships. Such as Person A "knows" Person B.

I'm wondering if any PageRank exists for this.

Best Regards

On Sunday, March 18, 2012 10:23:45 PM UTC+8, Tyler wrote:

Most likely my naivety with uses of PageRank (I've never used it) results in this question, but what is your use of PageRank for an undirected graph, since hyper links for webpages are naturally directional? Again, I don't know much about the uses of PageRank.

In the case of networkx's PageRank alg. there is no change in meaning that you are asking about because the algorithm doesn't actually run on an undirected graph. As a first step, the networkx PageRank implementation (https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/link_analysis/pagerank_alg.py) deep-copys the graph into a directed one with the to_directed() method, like so:

if not G.is_directed():

    D = G.to_directed()

else

    D = G

i.e. every undirected edge u--v gets copied (with data) to two separate directed edges u->v and v->u. So for networkx PageRank, there is no alternate meaning for undirected graphs as the algorithm doesn't actually ever perform on an undirected graph. That being said, your question boils down to "What are the implications of converting every undirected edge to two directional edges in the domain of PageRank". I never thought about it, but it sounds like a logical question to ask oneself after analyzing PageRank for directed graphs, in which case Google is your friend.

The code for the networkx HITS algorithm wasn't as easily interpretable to me, so I'll leave it up to someone else to help you on that one.

~ Tyler

[Marcel Blattner]

hi there again

In the case of HITS it is a bit different. HITS compiles two ranking vectors: hubs and authorities. Check for the difference http://ranger.uta.edu/~chqding/cse6319/classPapers/Kleinberg-web-graph.pdf. However, in a undirected case, hubs and authorities gain the same score. When you read the paper, you will understand why. The scores for hubs and authorities are different when you have a directed network. HITS takes care of both in and out going links, whereas PageRank is ignorant for out going links. Hope this helps.

Cheers

Marcel

To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/KHK0n24OUeUJ.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.

For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

Dr. Marcel Blattner

blat...@gmail.com

[Eugene Y.E]

Hi Marcel, 

Thanks! that's really useful.

Best Regards.