Exception in PageRankAlgorithm

Topics: algorithm, bug
Aug 30, 2007 at 9:53 AM
I've been using PageRankAlgorithm and I found that creating FilteredBidirectionalGraph in PageRankAlgorithm throws
System.stackOverflowException

if you remove in line 109 of PageRankAlgorithm.cs:
FilteredBidirectionalGraph<
Vertex,
Edge,
IBidirectionalGraph<Vertex,Edge>
> fg = new FilteredBidirectionalGraph<Vertex, Edge, IBidirectionalGraph<Vertex, Edge>>(
this.VisitedGraph,
new InDictionaryVertexPredicate<Vertex,double>(this.ranks).Test,
new AnyEdgePredicate<Vertex,Edge>().Test
);

and add:
IBidirectionalGraph<Vertex, Edge> fg = this.VisitedGraph;

there is no exception, but results seem to be wrong because GetRanksSum should return 1 according to this article of the american mathematical society: http://www.ams.org/featurecolumn/archive/pagerank.html

I think it should be fixed with this new class that supports dangling nodes and converging fails related to non-primitive matrixes. (note that FilteredBidirectionalGraph is not used, so 'fg' variable has been replaced by this.VisitedGraph)

    [Serializable]
    public sealed class PageRankAlgorithm<Vertex, Edge> :
        AlgorithmBase<IBidirectionalGraph<Vertex, Edge>>
        where Edge : IEdge<Vertex>
    {
        private IDictionary<Vertex, double> ranks = new Dictionary<Vertex, double>();
 
        private int maxIterations = 60;
        private double tolerance = 2 * double.Epsilon;
        private double damping = 0.85;
 
        public PageRankAlgorithm(IBidirectionalGraph<Vertex, Edge> visitedGraph)
            : base(visitedGraph)
        { }
 
        public IDictionary<Vertex, double> Ranks
        {
            get
            {
                return this.ranks;
            }
        }
 
        public double Damping
        {
            get
            {
                return this.damping;
            }
            set
            {
                this.damping = value;
            }
        }
 
        public double Tolerance
        {
            get
            {
                return this.tolerance;
            }
            set
            {
                this.tolerance = value;
            }
        }
 
        public int MaxIteration
        {
            get
            {
                return this.maxIterations;
            }
            set
            {
                this.maxIterations = value;
            }
        }
 
        public void InitializeRanks()
        {
            this.ranks.Clear();
            foreach (Vertex v in this.VisitedGraph.Vertices)
            {
                this.ranks.Add(v, 0);
            }
            //            this.RemoveDanglingLinks();
        }
                /*
                public void RemoveDanglingLinks()
                {
                    VertexCollection danglings = new VertexCollection();
                    do
                    {
                        danglings.Clear();
 
                        // create filtered graph
                        IVertexListGraph fg = new FilteredVertexListGraph(
                            this.VisitedGraph,
                            new InDictionaryVertexPredicate(this.ranks)
                            );
 
                        // iterate over of the vertices in the rank map
                        foreach (IVertex v in this.ranks.Keys)
                        {
                            // if v does not have out-edge in the filtered graph, remove
                            if (fg.OutDegree(v) == 0)
                                danglings.Add(v);
                        }
 
                        // remove from ranks
                        foreach (IVertex v in danglings)
                            this.ranks.Remove(v);
                        // iterate until no dangling was removed
                    } while (danglings.Count != 0);
                }
        */
 
        protected override void InternalCompute()
        {
            IDictionary<Vertex, double> tempRanks = new Dictionary<Vertex, double>();
 
            int iter = 0;
            double error = 0;
            do
            {
                if (this.IsAborting)
                    return;
 
                // compute page ranks
                error = 0;
                foreach (KeyValuePair<Vertex, double> de in this.Ranks)
                {
                    if (this.IsAborting)
                        return;
 
                    Vertex v = de.Key;
                    double rank = de.Value;
                    // compute ARi
                    double r = 0;
                    foreach (Edge e in this.VisitedGraph.InEdges(v))
                    {
                        r += this.ranks[e.Source] / this.VisitedGraph.OutDegree(e.Source);
                    }
 
                    // DANGLING NODES
                    // We assume a dangling node has a link to every other node in the graph
                    // so it is not necessesary to remove dangling nodes
                    foreach (Vertex currentVertex in this.VisitedGraph.Vertices)
                    {
                        if (this.VisitedGraph.IsOutEdgesEmpty(currentVertex))
                        {
                            r += tempRanks[currentVertex] / this.VisitedGraph.VertexCount;
                        }
                    }
 
                    // add sourceRank and store
                    // newRank represents the probability of going to the nodes linked to the
                    // current node and to any other node in the graph
                    // thus we fix those graphs that fails to converge
                    double newRank = this.damping * r + (1 - this.damping) / this.VisitedGraph.VertexCount;
                    tempRanks[v] = newRank;
                    // compute deviation
                    error += Math.Abs(rank - newRank);
                }
 
                // swap ranks
                IDictionary<Vertex, double> temp = ranks;
                ranks = tempRanks;
                tempRanks = temp;
 
                iter++;
            } while (error > this.tolerance && iter < this.maxIterations);
            Console.WriteLine("{0}, {1}", iter, error);
        }
 
        public double GetRanksSum()
        {
            double sum = 0;
            foreach (double rank in this.ranks.Values)
            {
                sum += rank;
            }
            return sum;
        }
 
        public double GetRanksMean()
        {
            return GetRanksSum() / this.ranks.Count;
        }
 
    }

I sent you an e-mail but I found this alternative way to post the problem. Sorry for the other mail.

I hope this will help you to improve the library even more,

regards