[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“)


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


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
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