[Networkit] Matrix classes & separation of algorithm and data structure

Kolja Esders kolja.esders at student.kit.edu
Wed Jan 21 17:17:15 CET 2015


Hi NetworKit developers,

as part of my bachelor thesis I currently implement a number of link
prediction algorithms for NetworKit.

During this effort I encountered that the regular Matrix class is not well
suited to store the resulting scores for all algorithms as the similarity
matrices are oftentimes very dense or need only the storage space of an
triangular matrix due to symmetry.
Consequently I've implemented a vector-based SymmetricSimilarityMatrix
which stores a triangular-matrix in a vector allowing for fast access and
less memory usage.
This approach collides with the Matrix classes already present because the
new class can't inherit from the current Matrix class which is based on a
graph-implementation.
To solve this problem I would propose a common interface "Matrix" which
simply defines a set of pure virtual functions which could then be
implemented from a SparseMatrix class (the current Matrix class) and the
SymmetricSimilarityMatrix as well.
What do you guys think about this approach? Are there better ways to solve
this?

Another problem is the separation of algorithm and the used data structure.
Right now every algorithm takes a graph as an input and outputs a matrix
containing the scores for every node-pair. The matrix is stored in the
class itself and gets allocated during construction.
Now in order to make use of one algorithm (e.g. common neighbors [CN]) in
another algorithm (e.g. Jaccard's coefficent using CN) this would mean to
allocate twice the needed memory (2 matrices, one per class).
What would be the best approach to separate algorithm and data structure? I
would suggest that the constructor (or maybe the run method) takes a
reference to the output matrix to fill with scores. Thus the class wouldn't
own the matrix.

Please note if the above explanation is not clear enough.
I would appreciate any feedback!

Best regards,
Kolja
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150121/34fa361c/attachment.html>


More information about the NetworKit mailing list