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

Henning Meyerhenke meyerhenke at kit.edu
Wed Jan 21 17:58:45 CET 2015


A rather general note before I have time to be more specific:

When the algebraic interface was started, the graph data structure was 
much more limited than it is today. The Matrix class has not seen the 
same series of updates yet, though.

At least two unpublished important projects depend on the algebraic 
interface of NetworKit. Thus, changes should not be done without 
consideration. The unpublished projects must still work without major 

In particular coordinate your ideas with Michael Wegner, the author of 
the matrix code.


Am 21.01.15 um 17:17 schrieb Kolja Esders:
> 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


Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5316 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150121/60154c90/attachment.p7s>

More information about the NetworKit mailing list