Shahin-<br><br>Quasi-PageRank meaning:<br>- Semantically, It's not the actual PageRank algorithmn a la Google, since that's patented and so its doubtful that I've implemented exactly their PageRank alg. Also, PageRank is a strange name for this feature in our domain, so I think SocialRank makes more sense.<br>
- Semantics aside, I also removed the dampening factor, since I suspect that's only needed when your random walk will not visit all nodes. Since I can update all Nodes' values with each iteration, I left it out since it would make each iteration have a slower effect in updating values. Or in other words, I've set d=1.0. For nodes with no inbound edges, this means that their PR is 0.0 after one iteration, instead of approaching zero over time.<br>
<br>It's not in R. It's in Ruby and dumping the output to csv after each iteration. I'd be happy to reformat my output to something yummy for R to gobble up if csv is not ideal.<br><br>I'm not taking the approach Mike presented (power method), but rather an iterative method that should result in same calculations. More or less described in the "Iterative" section here: <a href="http://en.wikipedia.org/wiki/PageRank#Computation">http://en.wikipedia.org/wiki/PageRank#Computation</a> (but like I said with dampening removed). "The basic mathematical operations performed in the iterative method and the power method are identical." <br>
<br>Another caveat is that I'm equally initializing PR(t=0) for each node at equal values (1/N where N=number of nodes) instead of something related to number of inbound edges versus outbound as Mike's talk suggested. This is me keeping things simple to start, so I can verify correctness more easier. I can always rerun with different initial values if we determine that's better.<br>
<br>I've calculated 50 iterations deep so far, which isn't computationally difficult with my code (under an hour without any dumping, under two hours if dumping all iterations). However, I think I have a correctness issue that I need to fix and then re-run. Namely, I was keeping my PR values in one hash and updating it as I iterate but i think I need to keep separate hashes, one for the current timestep and another for the previous timestep. This would unfairly diminish the PR values of the nodes that are iterated on last. In theory since, my order changes with each iteration, this won't have a major effect, but it's easy enough for me to correct, so I will.<br>
<br>More to follow later this week once I fix my bug and rerun... At that time I'll post my code and sample data. That said, in the meantime if you want to try your hand at it in R using power method, go for it! We can always compare results to confirm we are finding the same nodes to be most "important". (So far node #146725 has the highest SocialRank value in our network, while #887961 is the lowest (non-zero) PR)<br>
<br>One thing I could use help with is knowing when I can stop iterating.... Any ideas on that? I'll be able to compare PR(t=i) and PR(t=i-1) for a given node in constant time, if that helps... <br><br>Jared-<br><br>
<div class="gmail_quote">On Fri, Nov 26, 2010 at 1:42 PM, Shahin Saneinejad <span dir="ltr"><<a href="mailto:ssaneine@gmail.com">ssaneine@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hey Jared,<div><br></div><div>Is this in R? Are you using power iteration? I'm considering both these approaches for memory footprint and code simplicity reasons, respectively (my laptop is a little long in the tooth).<div>
<br></div><div>Also, what's "quasi" about your quasi-PageRank feature?</div><div><div><br></div><div><font color="#888888">Shahin</font><div><div></div><div class="h5"><br><br><div class="gmail_quote">On Thu, Nov 25, 2010 at 4:11 PM, Jared Dunne <span dir="ltr"><<a href="mailto:jareddunne@gmail.com" target="_blank">jareddunne@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">I've implemented an iterative approach to quasi-PageRank feature
generation for all nodes. Each iteration across all nodes is under a
minute each time. I still need to fix some things with my approach and
possibly get some help sanity-checking the correctness of my algorithm.
I'll post more later, but I just wanted to let everyone know that I'm
making good progress on the PageRank feature generation, so that we
aren't duplicating our efforts. Gonna pick this back up later this
weekend. Enjoy your feasts.<br>
<br>
Jared-<br><br><div class="gmail_quote"><div><div></div><div>On Wed, Nov 24, 2010 at 6:23 PM, <span dir="ltr"><<a href="mailto:mike@mindmech.com" target="_blank">mike@mindmech.com</a>></span> wrote:<br></div>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div></div><div>
<div><div style="background-color: rgb(249, 223, 209); width: 650px; font-family: Arial,sans-serif; color: rgb(0, 0, 0); padding: 5px;"><div style="min-height: 36px; font-size: 14px; font-weight: bold; padding-bottom: 4px;">
<table style="display: inline; width: 100%;"><tbody><tr><td style="padding: 0pt;" width="32px"><img src="" style="min-height: 32px; margin-right: 5px;" alt=""></td>
<td style="padding: 0pt;" valign="middle" height="32px">I've shared <a href="https://docs.google.com/present/edit?id=0AbXOdbbcuXxAZGNidmNnNjJfMGRkNmg4OGR2&hl=en&invite=CO_7wcEI" target="_blank">SocialPageRank</a></td>
</tr></tbody></table></div>
<div style="font-size: 13px; background-color: rgb(255, 255, 255); padding: 10px 7px 7px;"><span style="color: rgb(0, 120, 37); font-weight: bold;">Message from <a href="mailto:mike@mindmech.com" style="color: rgb(0, 120, 37); font-weight: bold; text-decoration: none;" target="_blank">mike@mindmech.com</a>:</span>
<span style="color: rgb(0, 0, 0);"><pre style="font-size: 13px; font-family: Arial,sans-serif;">Here's the presentation I'll be giving tonight on Random Walks, PageRank, and Social Net Analysis.</pre></span>
<div style="min-height: 1px; background-color: rgb(204, 204, 204); padding: 0px;"></div>
<br>
Click to open:
<ul style="list-style-type: none; padding: 0pt; margin: 0pt;"><li style="margin: 0pt;"><a href="https://docs.google.com/present/edit?id=0AbXOdbbcuXxAZGNidmNnNjJfMGRkNmg4OGR2&hl=en&invite=CO_7wcEI" target="_blank">SocialPageRank</a></li>
</ul>
<br>
<span style="color: rgb(137, 137, 137);">Google Docs makes it easy to create, store and share online documents, spreadsheets and presentations.</span>
<div style="text-align: right;"><a href="http://docs.google.com" target="_blank"><img src="" style="border: 0pt none; margin-top: 10px;" alt="Logo for Google Docs"></a></div></div></div></div><br></div></div>_______________________________________________<br>
ml mailing list<br>
<a href="mailto:ml@lists.noisebridge.net" target="_blank">ml@lists.noisebridge.net</a><br>
<a href="https://www.noisebridge.net/mailman/listinfo/ml" target="_blank">https://www.noisebridge.net/mailman/listinfo/ml</a><br>
<br></blockquote></div><br>
<br>_______________________________________________<br>
ml mailing list<br>
<a href="mailto:ml@lists.noisebridge.net" target="_blank">ml@lists.noisebridge.net</a><br>
<a href="https://www.noisebridge.net/mailman/listinfo/ml" target="_blank">https://www.noisebridge.net/mailman/listinfo/ml</a><br>
<br></blockquote></div><br></div></div></div></div></div>
</blockquote></div><br>