Exploiting the Hierarchical Structure for Link Analysis

The rapid growth of the web and the ever increasing size of search results (along with their pollution by link spammers) means that new search and present methods need to be deployed. Here's a paper from MSR.

Link analysis algorithms have been extensively used in Web information retrieval. However, current link analysis algorithms generally work on a flat link graph, ignoring the hierarchal structure of the Web graph. They often suffer from two problems: the sparsity of link graph and biased ranking of newly-emerging pages. In this paper, we propose a novel ranking algorithm called Hierarchical Rank as a solution to these two problems, which considers both the hierarchical structure and the link structure of the Web. In this algorithm, Web pages are first aggregated based on their hierarchical structure at directory, host or domain level and link analysis is performed on the aggregated graph. Then, the importance of each node on the aggregated graph is distributed to individual pages belong to the node based on the hierarchical structure. This algorithm allows the importance of linked Web pages to be distributed in the Web page space even when the space is sparse and contains new pages. Experimental results on the .GOV collection of TREC 2003 and 2004 show that hierarchical ranking algorithm consistently outperforms other well-known ranking algorithms, including the PageRank, BlockRank and LayerRank. In addition, experimental results show that link aggregation at the host level is much better than link aggregation at either the domain or directory levels.

Source: Exploiting the Hierarchical Structure for Link Analysis, Gui-Rong Xue; Qiang Yang; Hua-Jun Zeng; Yong Yu; Zheng Chen.

Inductive Graph representation

Most people represent graphs with adjacency lists or as node objects with edges represented as references to other nodes. In this paper they represent a graph inductively. A graph is either an empty graph, or a graph with the addition of a new node and prev/next edges to existing nodes from the new node. This makes representation of some graph algorithms very elegant if you have the right primitives (ie. you need the ability to pull nodes out of the representation in an order that makes sense for your algorithm).

http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf

Several for September

I've been unable to post for a while so I have several diverse recommendations:

Some plan9 advocacy with good analysis of what happened to unix:
http://www.cs.unm.edu/~fastos/05meeting/PLAN9NOTDEADYET.pdf
http://herpolhode.com/rob/ugly.pdf
And a more detailed paper describing examples of how Plan9 leverages file servers to build a distributed system:
http://www.9con.org/rml/servers.pdf

An interesting talk about using recurrences and lazy evaluation to compute power series, and the paper it was based on:
http://herpolhode.com/rob/lec3.pdf
http://citeseer.ist.psu.edu/mcilroy89squinting.html
I goofed off with this concept a little in python to see how well generators work for this:
http://lava.net/~newsham/x/machine/powerseries.py
http://lava.net/~newsham/x/machine/powerseries2.py
And a tour de force on the same topic using haskell (which works much better for this purpose than python does). This paper is incredible:
http://citeseer.ist.psu.edu/mcilroy00music.html

While investigating Haskell (www.haskell.org) I came across this oldy but goody that tries to explain why anyone would want to use a functional language anyway. Seems like a good topic because I haven't heard many good reasons in the past.
http://www.md.chalmers.se/~rjmh/Papers/whyfp.pdf

Enjoy