[Networkit] Efficient way to calculate avg path length

Henning Meyerhenke meyerhenke at kit.edu
Tue Jan 27 17:45:34 CET 2015


Hello Israa,

No, APSP as such does not exist. Simple (but maybe not the very best 
solution): n SSSP/BFS runs. For unweighted graphs this should be not too 
bad. To exploit parallelism, write your own C++ code for calling the BFS 
runs.

As an important side note: accumulated path lengths become large very 
quickly. For networks with millions of nodes you need to beware of 
numerical issues.

Best,
Henning


Am 27.01.15 um 17:20 schrieb Isra Al Qasem:
> Hello Henning,
>
> I'm working on the most recent release of NetworKit (python package)
> Is APSP implemented in networkit?
>
> Thanks,
> Israa
>
>
>  > Date: Tue, 27 Jan 2015 17:05:37 +0100
>  > From: meyerhenke at kit.edu
>  > To:
>  > Subject: Re: [Networkit] Efficient way to calculate avg path length
>  >
>  > Dear Israa,
>  >
>  > What do you mean by efficient? Is there an algorithm that is in general
>  > more effiicient than APSP and averaging?
>  >
>  > APSP for graphs with 10M nodes can take a while, even for unweighted
>  > graphs...
>  >
>  > Moreover, are you looking for a C++ implementation of an avg path length
>  > algorithm? If not, you could put the existing pieces together in Python,
>  > using the cythonized C++ algorithms, of course.
>  >
>  > Best,
>  > Henning
>  >
>  >
>  > Am 25.01.15 um 16:46 schrieb Isra Al Qasem:
>  > > Dear NetworKit developers,
>  > >
>  > > Is there an efficient way to estimate/calculate avg path length in a
>  > > graph consisting roughly of 10M nodes?
>  > >
>  > > Thanks for your continuous help!
>  > >
>  >
>  > --
>  >
>  > =======================================================
>  > 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
>  > =======================================================
>  >

-- 

=======================================================
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/20150127/8f282ba4/attachment-0001.p7s>


More information about the NetworKit mailing list