Determining the Diameter of Small World Networks

This website provides the C++ source code of BoundingDiameters, as presented in the paper:

• F.W. Takes and W.A. Kosters, Determining the Diameter of Small World Networks, in Proceedings of the 20th ACM Conference on Information and Knowledge Management (CIKM 2011), pp. 1191-1196, 2011.

Implementaton

• An implementation in C++ of BoundingDiameters is now part of the GitHub project teexGraph.
  Apart from the diameter, this version also efficiently computes the radius, center, periphery and eccentricity values of all nodes.
  Version 0.2, 0.32 and 0.4 are still available, yet inferior and therefore the use of these older versions is strongly discouraged.
• A Gephi plugin is available here: BoundingDiamters Gephi Plugin
  This plugin was ported from the C++ code by Alex Keizer, Bram Klaas Honig, David F. A. Nieuwenhuizen, Swan H. Lin, Ceyhan Deve and Tristan Oosterhoorn.

Datasets

To test the algorithm, the datasets listed below have been used. Note that in the paper, some originally directed graphs have been interpreted as if they were undirected. For each of the datasets, a path realizing the diameter is shown.

• AstroPhys - url
  (length 14): 59697 102582 60701 40324 37937 37784 3877 65454 40764 57951 120783 66241 102576 33513
• Enron - url
  (length 13): 32896 32877 32875 32880 9861 89 54 78 435 4629 4802 4805 8553
• Flickr - url
  (length 24): 1413074 1401469 1369991 1401470 1413073 1416867 1417898 1418306 427422 233703 18998 969 351 74743 190573 235052 1558937 1039307 1039305 1074276 1074290 1074295 1074298 1074299
• Hyves - unavailable due to legal restrictions
• LiveJournal - url
  (length 23): 5284443 5284412 5284238 5283198 5274009 5194227 4149854 3023167 1755951 11898 10093 8551 244998 1828109 5021250 5259630 5281700 5284036 5284371 5284442 5284446 5284453 5284455
• Orkut - url
  (length 10): 2250603 65080 1129 4013 14 6 1 8 1102 73114
• Skitter - url
  (length 31): 1695692 1695691 1695689 1695661 1694703 1686897 1685188 1633951 1313458 562183 222281 912 25549 638220 1371359 1644129 1687079 1692111 1693865 1694448 1694494 1694496 1696064 1696065 1696066 1696067 1696068 1696069 1696070 1696071 1696073
• YouTube - url
  (length 24): 1014215 1014191 1014099 1013842 1012820 1008044 989014 887594 631774 619071 631772 5579 2733 59960 337843 557717 626262 633306 634880 635300 888125 989184 1008103 1012854
• Web - url
  (length 24): 282697 810665 802636 431652 570953 231638 3408 69683 432954 440735 125907 188804 767559 11470 138821 65412 251918 191560 739557 660667 163783 19016 281002 384645
• Wikipedia - nl pagelinks of DBPedia v3.5 - url
  (length 18): 1030523 1030522 1029344 1029343 1029303 1029328 1027678 1027676 2763 412428 577290 2033701 1988515 1988514 1940213 1988480 1988481 2166993

Errata

For the paper "Determining the Diameter of Small World Networks":

On page 4, first line of that page, "line 12" should be "line 9".
On page 4, "denote the a lower bound" should be "denote the lower bound".

HTML | Page maintained by Frank Takes