全米道路グラフの疎性１。

DIMACS で公開されているグラフはかなり疎であるので、様々な手法でグラフ疎化や階層化がなされてきた。割合を調べて見たので、載せておく。

最も小さなグラフである NY (264,346 nodes 733,846 arcs) では、

   [#degrees]    [%]    [%]
 0          0   0.00   0.00
 1      41050  15.53  15.53
 2      38048  14.39  29.92
 3     126262  47.76  77.69
 4      57341  21.69  99.38
 5       1341   0.51  99.88
 6        285   0.11  99.99
 7         17   0.01 100.00
 8          2   0.00 100.00

中くらいの LKS (2758119 nodes 6885658 arcs) では、

   [#degrees]    [%]    [%]
 0          0   0.00   0.00
 1     475892  17.25  17.25
 2     842136  30.53  47.79
 3    1056949  38.32  86.11
 4     365776  13.26  99.37
 5      12818   0.46  99.84
 6       4402   0.16  99.99
 7        127   0.00 100.00
 8         19   0.00 100.00

最も大きなグラフである USA (23,947,347 nodes 58,333,344 arcs) でも、

   [#degrees]    [%]    [%]
 0          0   0.00   0.00
 1    4744422  19.81  19.81
 2    6912883  28.87  48.68
 3    9521467  39.76  88.44
 4    2668493  11.14  99.58
 5      76526   0.32  99.90
 6      22836   0.10 100.00
 7        626   0.00 100.00
 8         91   0.00 100.00
 9          3   0.00 100.00

と、かなり疎であることが分かる。

なお、表の見方だが、
次数（点から出ている枝の数）、該当する点数、全体の割合、累計割合
となっている。