D-iteration: evaluation of the update algorithm

The aim of this paper is to analyse the gain of the update algorithm associated to the recently proposed D-iteration: the D-iteration is a fluid diffusion based new iterative method. It exploits a simple intuitive decomposition of the product matrix-vector as elementary operations of fluid diffusion (forward scheme) associated to a new algebraic representation. We show through experimentations on real datasets how much this approach can improve the computation efficiency in presence of the graph evolution. the weight of the edge from j to i) and the initial condition F0 . We recall the definition of the two vectors used in Diteration: the fluid vector Fn by: Fn where: · Id is the identity matrix; · I = {i1 , i2 , ..., in , ...} with in {1, .., N } is a deterministic or random sequence such that the number of occurrence of each value k {1, .., N } in I is infinity; · Jk a matrix with all entries equal to zero except for the k-th diagonal term: (Jk )kk = 1. And the history vector Hn by (H0 initialized to a null vector): n