Algebraic reputation model RepRank and its application to spambot detection

Due to popularity surge social networks became lucrative targets for spammers and guerilla marketers, who are trying to game ranking systems and broadcast their messages at little to none cost. Ranking systems, for example Twitters Trends, can be gamed by scripted users also called bots, who are automatically or semi-automatically twitting essentially the same message. Judging by the prices and abundance of supply from PR firms this is an easy to implement and widely used tactic, at least in Russian blogosphere. Aggregative analysis of social networks should at best mark those messages as spam or at least correctly downplay their importance as they represent opinions only of a few, if dedicated, users. Hence bot detection plays a crucial role in social network mining and analysis. In this paper we propose technique called RepRank which could be viewed as Markov chain based model for reputation propagation on graphs utilizing simultaneous trust and anti-trust propagation and provide effective numerical approach for its computation. Comparison with another models such as TrustRank and some of its modifications on sample of 320000 Russian speaking Twitter users is presented. The dataset is presented as well.

Fast low-rank solution of the Poisson equation with application to the Stokes problem

We consider the problem of computing approximate solution of Poisson equation in the low-parametric tensor formats. We propose a new algorithm to compute the solution based on the cross approximation algorithm in the frequency space, and it has better complexity with respect to ranks in comparison with standard algorithms, which are based on the exponential sums approximation. To illustrate the effectiveness of our solver, we incorporate into a Uzawa solver for the Stokes problem on semi-staggered grid as a subsolver. The resulting solver outperforms the standard method for $n geq 256$.