This repository presents the approach to compute SimRank lowrank approximation [I. Oseledets, G. Ovchinnikov, A. Katrutsa 2017]. SimRank is a similarity measure between graph vertices originally introduced in [Jeh and Widom, 2002]. But for large graphs storing SimRank for all pairs of vertices is intractable. Therefore we propose a method to store not exhaustive SimRank matrix, but only two lowrank matrices. Moreover, we provide an equation how to recover SimRank approximation from the adjacency matrix and two lowrank matrices.
To test SimRankLowrank approximation approach, run the following commands in the directory you choose:
git clone https://github.com/amkatrutsa/SimRankLowrank.git
cd ./mcode
Then in MATLAB command line from the directory mcode run the command:
main
After that, you will have precise SimRank matrix S, computed by the naive SimRank algorithm, and its lowrank approximation S_lr, computed by our method.
To use our code from C++ you need to install Armadillo library. To test SimRankLowrank approximation approach, run the following commands in the directory you choose:
git clone https://github.com/amkatrutsa/SimRankLowrank.git
cd ./ccode
mkdir build
cd ./build
cmake ..
make
After that you will have the binary file simrank_lowrank.
We carried out our experiments on the graphs from DIMACS10 Collection, which are in the directory data.