[Networkit] Update: Clustering coefficients accelerated

Staudt, Christian (ITI) christian.staudt at kit.edu
Wed Apr 9 15:09:43 CEST 2014


Calculation of clustering coefficients is now significantly faster. The trick: Checking whether a triangle is closed is now done via hash set lookup, not G.hasEdge(u,v). Remember that the latter is not a constant time operation but works in O(deg(v)).


In [2]: G = readGraph("/home/i11/staudt/Graphs/Collections/ICPP/G/soc-LiveJournal.metis.graph“)

before:

In [3]: %time properties.ClusteringCoefficient().avgLocal(G)
CPU times: user 34min 42s, sys: 342 ms, total: 34min 42s
Wall time: 15min 29s
Out[3]: 0.4282433026988098

after:

In [3]: %time properties.ClusteringCoefficient().avgLocal(G)
CPU times: user 7min 4s, sys: 71 ms, total: 7min 4s
Wall time: 1min 25s
Out[3]: 0.4076603777997689

Kind regards



Christian Staudt

christian.staudt at kit.edu
http://parco.iti.kit.edu/staudt/index-en.shtml
Institut of Theoretical Computer Science - Parallel Computing Group 
Building 50.34 Room 249
Karlsruhe Institute of Technology (KIT)





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140409/2e475c64/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140409/2e475c64/attachment.sig>


More information about the NetworKit mailing list