KONECT
KONECT > Statistics > Diameter

## Diameter

The distance between two nodes in a network is defined as the number of edges needed to reach one node from another, and serves as the basis for a class of network statistics.
A path in a network is a sequence of incident edges, or equivalently, a sequence of nodes $$P = (u_0, u_2, \dotsc, u_k)$$, such that $$(u_i, u_{i+1})\in E$$ for all $$i \in \{0, \dotsc, k-1\}$$. The number $$k$$ is called the length of the path, and will also be denoted $$l(P)$$. A further restriction can be set on the visited nodes, definining that each node can only be visited at most once. If the distinction is made, the term path is usually reserved for sequences of non-repeating nodes, and general sequence of adjacent nodes are then called walks. We will not make this distinction here.
Paths in networks can be used to model browsing behavior of people in hyperlink networks, navigation in transport networks, and other types of movement-like activities in a network. When considering navigation and browsing, an important problem is the search for shortest paths. Since the length of a path determines the number of steps needed to reach one node from another, it can be used as a measure of distance between nodes of a network. The distance defined in this way may also be called the shortest-path distance to distinguish it from other distance measures between nodes of a network. \begin{align} d(u, v) &= \left\{ \begin{array} {ll} \min_{P=(u, \dotsc, v)} l(P) & \text{when $$u$$ and $$v$$ are connected} \\ \infty & \text{when $$u$$ and $$v$$ are not connected} \end{array} \right. \end{align} In the case that a network is not connected, the distance is defined as infinite. In practice, only the largest connected component of a network may be used, making it unnecessary to deal with infinite values. The distribution of all $$|V|^2$$ values $$d(u,v)$$ for all $$u,v\in V$$ is called the distance distribution, and it too characterizes the network.
The eccentricity of a node can then be defined as the maximal distance from that node to any other node, defining a measure of non-centrality: \begin{align} \epsilon(u) &= \max_{v\in V} d(u,v) \end{align}
The diameter $$\delta$$ of a graph equals the longest shortest path in the network. It can be equivalently defined as the largest eccentricity of all nodes. \begin{align} \delta &= \max_{u \in V} \epsilon(u) = \max_{u,v \in V} d(u,v) \end{align}
Note that the diameter is undefined (or infinite) in unconnected networks, and thus in numbers reported for actual networks in KONECT we consider always the diameter of the network's largest connected component. Du to the high runtime complexity of computing the diameter, it may be estimated by various methods, in which case it is noted noted $$\tilde \delta$$.
A statistic related to the diameter is the radius, defined as the smallest eccentricity \begin{align} r &= \min_{u \in V} \epsilon(u) = \min_{u \in V} \max_{v \in V} d(u,v) \end{align}
The diameter is bounded from below by the radius, and from above by twice the radius. \begin{align*} r \leq \delta \leq 2r \end{align*} The first inequality follows directly from the definition of $$r$$ and $$\delta$$ as the minimal and maximal eccentricity. The second inequality follows from the fact that between any two nodes, the path joining them cannot be longer that the path joining them going through a node with minimal eccentricity, which has length of at most $$2r$$.
The radius and the diameter are not very expressive statistics: Adding or removing an edge will, in many cases, not change their values. Thus, a better statistic that reflects the typical distances in a network in given by the mean and average distance.
The mean path length $$\delta_{\mathrm m}$$ in a network is defined as as the mean distance over all node pairs, including the distance between a node and itself: \begin{align} \delta_{\mathrm m} &= \frac 1 {n^2} \sum_{u \in V} \sum_{v\in V} d(u,v) \end{align} The mean path length defined in this way is undefined when a graph is disconnected.
Likewise, the median path length $$\delta_{\mathrm M}$$ is the median length of shortest paths in the network. In KONECT, both the median and mean path lengths are computed taking into account node pairs of the form $$(u,u)$$.
Both the mean and median path length can be called the characteristic path length of the network.
A related statistic is the 90-percentile effective diameter $$\delta_{0.9}$$, which equals the number of edges needed on average to reach 90% of all other nodes.

 Code Name Category F. W. M. $$n$$ $$m$$ $$\delta$$ $$\delta_{0.9}$$ $$\delta_{\mathrm m}$$ $$\tilde \delta$$ $$\delta_{\mathrm M}$$ Mh Hens ⬤ Animal 32 496 1 0.90 0.97 MB Bison ⬤ Animal 26 314 2 1.70 1.30 MQ Macaques ⬤ Animal 62 1,187 2 1.75 1.38 MR Rhesus ⬤ Animal 16 111 2 1.77 1.37 Ms Sampson ⬤ HumanSocial 18 189 2 1.44 1.12 MX Seventh graders ⬤ HumanSocial 29 376 2 1.75 1.37 Mv Dutch college ⬤ HumanSocial 32 3,062 2 1.35 1.13 FD Florida ecosystem dry ⬤ Trophic 128 2,137 3 1.88 1.72 1.87305 × 100 FW Florida ecosystem wet ⬤ Trophic 128 2,106 3 1.88 1.73 1.85925 × 100 J2 Jester 150 ⬤ Rating 101,524 1,728,847 3 1.90 2.00 1.80000 × 100 RM Reality Mining ⬤ HumanContact 96 1,086,404 3 1.73 1.36 1.80158 × 100 MW Windsurfers ⬤ HumanContact 43 336 3 1.93 1.70 MA Cattle ⬤ Animal 28 217 3 1.83 1.47 MK Kangaroo ⬤ Animal 17 91 3 1.67 1.23 Mc Sheep ⬤ Animal 28 250 3 1.76 1.37 HY Hypertext 2009 ⬤ HumanContact 113 20,818 3 1.84 1.59 1.80786 × 100 HT Highland tribes ⬤ HumanSocial 16 58 3 1.83 1.45 1.87013 × 100 SC South African Companies ⬤ Affiliation 17 13 4 2.86 1.84 3.14286 × 100 HA Haggle ⬤ HumanContact 274 28,244 4 2.79 2.42 3.58535 × 100 DV Digg votes ⬤ Rating 282,371 3,018,197 4 3.88 3.71 Da Discogs artist–genre ⬤ Feature 3,509,661 19,033,891 4 3.84 3.23 3.66137 × 100 Dr Discogs label–genre ⬤ Feature 541,557 4,147,665 4 3.81 3.04 3.64596 × 100 EX Wikipedia (en) ⬤ Text 279,519 7,846,807 4 3.90 3.94 1.80000 × 100 J1 Jester 100 ⬤ Rating 146,942 4,136,360 4 1.90 2.00 1.80000 × 100 ML Little Rock Lake ⬤ Trophic 183 2,494 4 2.65 2.13 3.34534 × 100 MO Residence hall ⬤ HumanSocial 217 2,672 4 2.79 2.33 MZ Zebra ⬤ Animal 27 111 4 2.65 1.79 AN David Copperfield ⬤ Lexical 112 425 5 2.98 2.47 3.63005 × 100 BM Club membership ⬤ Affiliation 65 95 5 3.37 2.55 Sw Southern women 2 ⬤ Interaction 15 14 5 3.79 2.41 2.00000 × 100 YD Yahoo advertisers ⬤ Lexical 653,260 2,931,708 5 3.75 3.24 MI Physicians ⬤ HumanSocial 241 1,098 5 2.91 2.49 Ml Les Misérables ⬤ Misc 77 254 5 3.40 2.64 MT Taro exchange ⬤ HumanSocial 22 78 5 3.26 2.38 M1 MovieLens 100k ⬤ Rating 3,568 100,000 5 3.42 2.75 1.86195 × 100 NX Netflix ⬤ Rating 978,148 100,480,507 5 3.10 2.30 2.48467 × 100 SW Southern women 1 ⬤ Interaction 50 89 5 3.15 2.41 2.02581 × 100 RA Manufacturing emails ⬤ Communication 167 82,927 5 2.25 1.87 2.96854 × 100 ZA Zachary karate club ⬤ HumanSocial 34 78 5 3.44 2.44 3.56085 × 100 JZ Jazz musicians ⬤ HumanSocial 198 2,742 6 2.79 2.21 3.39274 × 100 BC Corporate Leadership ⬤ Affiliation 64 99 6 3.81 2.87 Ar American Revolution ⬤ Affiliation 277 160 6 3.83 3.11 Dt Discogs artist–style ⬤ Feature 3,236,269 24,085,580 6 3.89 3.83 3.77737 × 100 EA Edinburgh Associative Thesaurus ⬤ Lexical 23,132 511,764 6 3.85 3.43 3.87369 × 100 Lb Last.fm band ⬤ Interaction 176,061 19,150,868 6 3.90 3.92 1.84572 × 100 Ls Last.fm song ⬤ Interaction 1,086,604 19,150,868 6 3.90 3.95 1.85172 × 100 LI Libimseti.cz ⬤ Social 220,970 17,359,346 6 3.09 2.85 3.74581 × 100 LM Livemocha ⬤ Social 104,103 2,193,083 6 3.63 3.21 MH Highschool ⬤ HumanSocial 70 366 6 3.51 2.66 Mt Train bombing ⬤ HumanContact 64 243 6 3.63 2.63 M3 MovieLens 10M ⬤ Rating 150,433 10,000,054 6 2.86 2.39 1.99119 × 100 M2 MovieLens 1M ⬤ Rating 15,786 1,000,209 6 2.86 2.52 1.87867 × 100 RE Reuters ⬤ Text 1,846,441 96,903,520 6 3.33 2.69 2.04279 × 100 WU WebUni Magdeburg ⬤ Text 212,552 3,869,707 6 3.89 3.89 1.91809 × 100 Tar Wikipedia talk, Arabic ⬤ Communication 1,095,799 1,913,103 6 3.47 2.46 PM Caenorhabditis elegans ⬤ Metabolic 453 4,596 7 3.03 2.64 3.70451 × 100 GC Google.com internal ⬤ Hyperlink 15,763 171,206 7 2.93 2.56 3.54949 × 100 Ds Discogs label–style ⬤ Feature 487,911 5,255,950 7 3.88 3.72 3.76919 × 100 EL Wikipedia elections ⬤ OnlineContact 7,118 103,675 7 3.79 3.25 3.81374 × 100 Fr Filmtipset ⬤ Rating 225,153 19,554,219 7 3.52 2.84 1.99229 × 100 R2 Reuters-21578 ⬤ Text 81,791 1,464,182 7 3.85 3.45 1.88299 × 100 TR TREC (disks 4–5) ⬤ Text 2,285,379 151,632,178 7 3.81 3.40 1.90394 × 100 DJ JDK dependency ⬤ Software 6,434 150,985 7 2.47 2.19 2.34630 × 100 Dj JUNG dependency ⬤ Software 6,120 138,706 7 1.96 2.06 2.34963 × 100 Tnl Wikipedia talk, Dutch ⬤ Communication 225,749 1,554,699 7 3.64 3.12 A@ U. Rovira i Virgili ⬤ Communication 1,133 5,451 8 4.48 3.65 4.78497 × 100 DN DNC emails co-recipients ⬤ OnlineContact 2,029 136,602 8 3.31 2.71 DNc DNC emails ⬤ Communication 2,029 39,264 8 3.98 3.38 DO Dolphins ⬤ Animal 62 159 8 5.05 3.45 GP Google+ ⬤ Social 23,628 39,242 8 4.58 3.95 5.25975 × 100 FX Flixster ⬤ Social 2,523,386 7,918,801 8 5.38 4.82 FO FOLDOC ⬤ Hyperlink 13,356 125,207 8 4.58 3.99 Mg Blogs ⬤ Hyperlink 1,224 19,025 8 3.29 2.72 MN Bible ⬤ Lexical 1,773 16,401 8 3.94 3.38 Ws Twitter (ICWSM) ⬤ Social 465,017 834,797 8 4.96 4.59 5.64564 × 100 UF UC Irvine forum ⬤ Interaction 2,320 33,720 8 4.40 3.61 3.87810 × 100 UC UC Irvine messages ⬤ Communication 1,899 59,835 8 3.66 3.07 3.80312 × 100 AF US airports ⬤ Infrastructure 1,574 28,236 8 3.85 3.14 3.85761 × 100 PL Prosper loans ⬤ Interaction 89,269 3,394,979 8 3.73 3.28 UL Unicode languages ⬤ Feature 1,122 1,255 8 5.24 4.08 Tru Wikipedia talk, Russian ⬤ Communication 457,017 2,282,055 8 3.81 3.29 AD Advogato ⬤ Social 6,541 51,127 9 3.82 3.29 3.84727 × 100 AS Route views ⬤ Computer 6,474 13,895 9 4.45 3.67 4.87268 × 100 PH arXiv hep-ph ⬤ Coauthorship 28,093 4,596,803 9 3.22 2.83 3.71953 × 100 TH arXiv hep-th ⬤ Coauthorship 22,908 2,673,133 9 3.13 2.72 3.70230 × 100 DB Douban ⬤ Social 154,908 327,162 9 5.70 5.10 EF Facebook (NIPS) ⬤ Social 2,888 2,981 9 5.52 3.98 5.64376 × 100 Fc Filmtipset ⬤ Interaction 104,890 1,266,753 9 4.31 3.75 3.79660 × 100 FI Flickr ⬤ Misc 105,938 2,316,948 9 4.81 4.34 5.55490 × 100 Mui MovieLens u-i ⬤ Folksonomy 15,619 95,580 9 4.62 3.77 3.97870 × 100 If Infectious ⬤ HumanContact 410 17,298 9 4.78 3.57 5.28985 × 100 CR Chicago ⬤ Infrastructure 1,467 1,298 9 6.82 5.81 Tpt Wikipedia talk, Portuguese ⬤ Communication 541,355 2,424,962 9 3.25 2.74 Pi DBLP ⬤ Citation 12,591 49,743 10 5.20 4.42 5.62391 × 100 DBT TV Tropes ⬤ Feature 216,508 3,232,134 10 5.00 4.06 nfr Wikinews (fr) ⬤ Authorship 27,954 193,618 10 3.92 3.36 4.54390 × 100 mfr Wiktionary (fr) ⬤ Authorship 1,917,281 7,399,298 10 3.98 2.91 3.97772 × 100 HY Hyves ⬤ Social 1,402,673 2,777,419 10 6.65 5.76 Ug Wikipedia, de (dynamic) ⬤ Hyperlink 2,166,669 86,337,879 10 4.10 3.68 5.32535 × 100 MF Human protein (Figeys) ⬤ Metabolic 2,239 6,452 10 4.83 3.98 4.99348 × 100 MP PDZBase ⬤ Metabolic 212 244 10 7.21 5.11 1.04083 × 101 ME Adolescent health ⬤ HumanSocial 2,539 12,969 10 5.30 4.52 OR Orkut ⬤ Social 3,072,441 117,184,899 10 4.81 4.27 5.44887 × 100 Sc Catster ⬤ Social 149,700 5,449,275 10 2.94 2.65 3.68447 × 100 Sh Hamsterster full ⬤ Social 2,426 16,631 10 4.80 3.67 4.92681 × 100 PS Prosper.com ⬤ Affiliation 14,177 21,017 10 4.39 3.92 3.91787 × 100 TO Internet topology ⬤ Computer 34,761 171,403 10 4.37 3.78 4.59803 × 100 CO Wikipedia conflict ⬤ OnlineContact 118,100 2,917,785 10 3.89 3.36 3.85395 × 100 WP Wikipedia, English ⬤ Hyperlink 1,870,709 39,953,145 10 3.88 3.42 3.84935 × 100 Wen Wikipedia links, en ⬤ Hyperlink 12,150,976 378,142,420 10 4.70 4.06 Wfr Wikipedia links, fr ⬤ Hyperlink 3,023,165 102,382,410 10 4.28 3.67 3.91058 × 100 Wit Wikipedia links, it ⬤ Hyperlink 1,865,965 91,555,008 10 4.00 3.52 3.84710 × 100 Wja Wikipedia links, ja ⬤ Hyperlink 1,610,638 71,055,717 10 3.94 3.49 3.93629 × 100 Wpl Wikipedia links, pl ⬤ Hyperlink 1,529,135 57,489,447 10 3.80 3.24 3.91992 × 100 Wru Wikipedia links, ru ⬤ Hyperlink 2,853,118 82,056,101 10 4.41 3.78 4.36581 × 100 CU Contiguous USA ⬤ Infrastructure 49 107 11 6.98 4.26 7.05528 × 100 mde Wiktionary (de) ⬤ Authorship 157,806 1,229,501 11 3.84 3.08 4.03796 × 100 men Wiktionary (en) ⬤ Authorship 2,163,240 8,998,641 11 3.89 3.64 4.27707 × 100 GN Gnutella ⬤ Computer 62,586 147,892 11 6.75 5.96 7.32305 × 100 Sd Dogster ⬤ Social 426,820 8,546,581 11 3.87 3.40 3.86363 × 100 Wpt Wikipedia links, pt ⬤ Hyperlink 1,603,222 49,021,409 11 4.11 3.61 3.97093 × 100 WK Wikipedia, English ⬤ Communication 2,394,385 5,021,410 11 3.94 3.88 3.91515 × 100 But BibSonomy u-t ⬤ Folksonomy 216,261 2,555,080 12 4.01 4.05 3.87117 × 100 Cut CiteULike u-t ⬤ Folksonomy 198,707 2,411,819 12 5.23 4.26 3.84513 × 100 DL Wikipedia, English ⬤ Hyperlink 18,268,992 172,183,984 12 4.98 4.63 5.70199 × 100 nen Wikinews (en) ⬤ Authorship 184,536 901,416 12 5.33 4.11 5.15420 × 100 qen Wikiquote (en) ⬤ Authorship 137,970 549,210 12 4.62 3.91 4.16159 × 100 bfr Wikibooks (fr) ⬤ Authorship 33,881 201,727 12 4.26 3.72 5.09720 × 100 it Wikipedia (it) ⬤ Authorship 2,531,261 26,241,217 12 3.94 3.83 4.37600 × 100 ER Epinions ⬤ Rating 996,744 13,668,320 12 3.99 3.81 5.41520 × 100 Uf Wikipedia, fr (dynamic) ⬤ Hyperlink 2,212,682 59,008,831 12 4.45 3.83 5.35596 × 100 Us Wikipedia, simple en (dynamic) ⬤ Hyperlink 100,312 1,627,472 12 4.66 3.83 5.14954 × 100 LX Linux ⬤ Software 30,837 213,954 12 3.97 3.28 3.95472 × 100 DG Digg ⬤ Communication 30,398 87,627 12 5.40 4.68 5.75516 × 100 Vut vi.sualize.us u-t ⬤ Folksonomy 116,279 2,298,816 12 4.78 4.00 3.63601 × 100 SZ Slashdot Zoo ⬤ Social 79,120 515,397 12 4.58 3.99 5.21367 × 100 Wde Wikipedia links, de ⬤ Hyperlink 3,225,565 81,626,917 12 4.56 3.83 4.62005 × 100 CL Actor collaborations ⬤ Misc 382,219 33,115,812 13 4.31 3.70 CH Chess ⬤ Interaction 7,301 65,053 13 4.83 3.95 ben Wikibooks (en) ⬤ Authorship 200,108 1,164,576 13 4.73 3.91 5.15906 × 100 es Wikipedia (es) ⬤ Authorship 3,623,742 27,011,506 13 3.94 3.68 3.96108 × 100 fr Wikipedia (fr) ⬤ Authorship 4,598,826 46,168,355 13 3.99 3.93 4.65140 × 100 Ud Wikipedia, nl (dynamic) ⬤ Hyperlink 1,039,252 20,070,561 13 4.33 3.74 5.21084 × 100 MS Human protein (Stelzl) ⬤ Metabolic 1,706 6,207 13 6.97 5.09 6.58008 × 100 MV Human protein (Vidal) ⬤ Metabolic 3,133 6,726 13 5.87 4.80 5.96408 × 100 OF OpenFlights ⬤ Infrastructure 3,425 67,663 13 5.40 4.19 WD Wikipedia Threads (de) ⬤ Communication 91,340 2,435,731 13 3.95 3.65 AP arXiv astro-ph ⬤ Coauthorship 18,771 198,050 14 5.00 4.17 5.60237 × 100 PHc arXiv hep-ph ⬤ Citation 34,546 421,578 14 5.23 4.40 5.55413 × 100 Dut Delicious ut ⬤ Folksonomy 6,178,261 301,186,579 14 3.59863 × 100 EU EU institution ⬤ Communication 265,214 420,045 14 4.44 4.08 4.91815 × 100 EN Enron ⬤ Communication 87,273 1,148,072 14 5.79 4.90 5.89350 × 100 Up Wikipedia, pl (dynamic) ⬤ Hyperlink 1,033,050 25,026,208 14 4.00 3.55 4.62347 × 100 Mti MovieLens t-i ⬤ Folksonomy 40,657 95,580 14 5.69 4.78 5.68998 × 100 Mut MovieLens u-t ⬤ Folksonomy 24,546 95,580 14 5.52 4.41 5.24961 × 100 OF OpenFlights ⬤ Infrastructure 2,939 30,501 14 5.19 4.18 5.47332 × 100 Shf Hamsterster friendships ⬤ Social 1,858 12,534 14 3.97 3.39 4.29538 × 100 Vui vi.sualize.us u-i ⬤ Folksonomy 529,646 2,298,816 14 5.88 5.15 5.51741 × 100 PW Prosper.com ⬤ Interaction 25,697 35,377 14 5.98 5.48 5.97044 × 100 PL Pokec ⬤ Social 1,632,803 30,622,564 14 5.11 4.66 W2 WikiSigned ⬤ OnlineContact 138,592 740,397 14 4.19 3.81 4.72346 × 100 THc arXiv hep-th ⬤ Citation 27,770 352,807 15 5.36 4.27 5.72995 × 100 TL Twitter lists ⬤ Social 23,370 33,101 15 7.56 6.19 7.70245 × 100 Ol Facebook (WOSN) ⬤ Social 63,731 817,035 15 4.97 4.31 5.55810 × 100 OG Orkut ⬤ Affiliation 14,297,249 327,037,487 15 4.99 4.29 3.91337 × 100 Scd Catster/Dogster ⬤ Social 623,766 15,699,276 15 5.21 4.10 5.60717 × 100 ES Epinions ⬤ Social 75,879 508,837 15 5.26 4.40 Bui BibSonomy u-i ⬤ Folksonomy 779,035 2,555,080 16 5.79 4.70 5.94785 × 100 de Wikipedia (de) ⬤ Authorship 4,046,832 57,323,775 16 4.37 4.05 4.78906 × 100 en Wikipedia (en) ⬤ Authorship 29,143,573 266,769,613 16 4.48825 × 100 EP Epinions ⬤ Social 131,828 841,372 16 4.77 4.11 5.41331 × 100 Ui Wikipedia, it (dynamic) ⬤ Hyperlink 1,204,009 34,826,283 16 4.20 3.65 4.65712 × 100 GW Gowalla ⬤ Social 196,591 950,327 16 5.35 4.43 5.73938 × 100 Wut Twitter u-t ⬤ Folksonomy 880,846 4,664,605 16 5.89 5.32 4.78240 × 100 HUi Hudong internal ⬤ Hyperlink 1,984,484 14,869,484 16 4.80 4.16 5.30526 × 100 IN CAIDA ⬤ Computer 26,475 53,381 17 4.64 3.91 5.11354 × 100 SX Sexual escorts ⬤ Rating 26,836 50,632 17 7.20 5.79 6.95458 × 100 Ff Filmtipset ⬤ Social 39,199 87,415 17 7.17 5.87 7.54581 × 100 TC Air traffic control ⬤ Infrastructure 1,226 2,615 17 8.05 6.10 7.96372 × 100 Vti vi.sualize.us t-i ⬤ Folksonomy 659,472 2,298,816 17 4.92 3.89 5.90600 × 100 SD Slashdot ⬤ Communication 51,083 140,778 17 5.28 4.59 5.64290 × 100 YG YouTube ⬤ Affiliation 218,563 293,360 17 6.39 5.17 5.75121 × 100 CN Countries ⬤ Affiliation 1,182,526 637,134 18 5.70 4.50 5.04263 × 100 DF Digg friends ⬤ Social 279,630 1,731,653 18 4.96 4.31 Ow Facebook ⬤ Communication 46,952 876,993 18 6.84 5.71 7.38830 × 100 FG Flickr ⬤ Affiliation 895,589 8,545,307 18 5.62 4.44 5.33642 × 100 BK Brightkite ⬤ Social 58,228 214,078 18 5.76 4.86 5.97840 × 100 TF Twitter (MPI) ⬤ Social 52,579,682 1,963,263,821 18 BX BookCrossing (implicit) ⬤ Rating 551,079 1,149,739 19 5.78 4.82 5.81859 × 100 Mp Protein ⬤ Metabolic 1,870 2,277 19 9.59 7.07 Cui CiteULike u-i ⬤ Folksonomy 777,199 2,411,819 20 8.50 7.06 7.70698 × 100 LJ LiveJournal ⬤ Social 4,847,571 68,475,391 20 6.19 5.48 6.98389 × 100 SO Stack Overflow ⬤ Rating 1,187,072 1,301,942 20 6.42 5.58 5.85121 × 100 CC Cora citation ⬤ Citation 23,166 91,500 20 6.95 5.74 7.47811 × 100 BAi Baidu internal ⬤ Hyperlink 2,141,300 17,794,839 20 4.87 4.18 5.29254 × 100 WT Web trackers ⬤ Hyperlink 68,087,704 140,613,762 21 4.61 3.79 Bti BibSonomy t-i ⬤ Folksonomy 1,176,793 2,555,080 22 6.95 5.54 7.88356 × 100 Dl Discogs ⬤ Affiliation 3,780,417 14,414,659 22 5.75 4.68 5.43197 × 100 GH Github ⬤ Authorship 233,905 440,237 22 6.52 5.35 5.86213 × 100 LK Linux kernel mailing list threads ⬤ Interaction 421,599 1,565,683 22 5.66 4.61 Bx BookCrossing (ratings) ⬤ Rating 341,559 433,652 23 6.92 5.65 6.14910 × 100 CD DBLP co-authorship ⬤ Coauthorship 317,080 1,049,866 23 8.16 6.75 RL Record labels ⬤ Affiliation 355,095 233,286 23 6.44 5.33 6.28198 × 100 FL Flickr ⬤ Social 2,302,925 33,140,017 23 6.89 5.46 6.93319 × 100 Lj LiveJournal links ⬤ Social 5,204,176 49,174,464 23 6.19 5.44 6.54796 × 100 Wa Twitter ⬤ OnlineContact 2,919,613 12,887,063 23 5.91 5.45 5.89067 × 100 TW Twitter (WWW) ⬤ Social 41,652,230 1,468,365,182 23 PG Pretty Good Privacy ⬤ OnlineContact 10,680 24,316 24 10.07 7.65 Cti CiteULike t-i ⬤ Folksonomy 1,038,323 2,411,819 24 5.97 4.77 6.86211 × 100 CY Youtube friendship ⬤ Social 1,134,890 2,987,624 24 6.93 5.55 Pc DBLP ⬤ Coauthorship 1,314,050 18,986,618 24 7.14 6.09 7.47860 × 100 OC Occupation ⬤ Affiliation 356,884 250,945 24 6.77 5.20 5.42669 × 100 LF Flickr links ⬤ Social 1,715,255 15,551,250 24 6.36 5.19 6.97882 × 100 RC Reactome ⬤ Metabolic 6,327 147,547 24 5.39 4.14 5.62169 × 100 GO Google ⬤ Hyperlink 875,713 5,105,039 24 7.95 6.37 8.58817 × 100 LY Youtube links ⬤ Social 1,138,499 4,942,297 24 6.78 5.43 6.49555 × 100 Am Amazon (TWEB) ⬤ Misc 403,394 3,387,388 25 7.43 6.36 7.74822 × 100 Dti Delicious ti ⬤ Folksonomy 42,801,712 301,183,605 26 3.79872 × 100 PC US patents ⬤ Citation 3,774,768 16,518,947 26 9.48 8.24 9.52585 × 100 AM Actor movies ⬤ Affiliation 639,286 1,470,404 27 8.64 7.13 7.44619 × 100 LO Location ⬤ Feature 397,589 293,697 27 8.77 6.75 7.79400 × 100 AR Amazon ratings ⬤ Rating 5,523,029 5,838,041 28 8.04 6.63 7.57228 × 100 LG LiveJournal ⬤ Affiliation 13,891,479 112,307,385 28 5.70 4.73 3.76645 × 100 Dui Delicious ui ⬤ Folksonomy 35,444,383 301,186,579 29 4.67415 × 100 Wui Twitter u-i ⬤ Folksonomy 9,618,743 12,656,613 30 9.76 8.13 7.82933 × 100 SK Skitter ⬤ Computer 1,696,415 11,095,298 31 5.85 5.04 5.95944 × 100 Wti Twitter t-i ⬤ Folksonomy 1,773,193 2,635,885 31 7.67 5.91 7.75266 × 100 YT YouTube ⬤ Social 3,223,589 9,375,374 31 6.64 5.29 GE DBpedia genre ⬤ Feature 525,651 463,497 32 7.44 5.08 6.19932 × 100 MC Crime ⬤ Interaction 2,209 1,476 32 19.47 13.37 BAr Baidu related ⬤ Hyperlink 415,641 3,284,387 32 8.54 6.11 8.88541 × 100 CS CiteSeer ⬤ Citation 384,413 1,751,463 34 7.96 6.35 7.99549 × 100 AC arXiv cond-mat ⬤ Authorship 55,467 58,595 36 16.86 12.83 1.51815 × 101 ST Movies ⬤ Feature 233,283 281,396 38 12.54 9.43 1.09744 × 101 FR Friendster ⬤ Social 68,349,466 2,586,147,869 38 TM Teams ⬤ Affiliation 1,836,793 1,366,466 41 7.69 6.37 7.17361 × 100 UG US power grid ⬤ Infrastructure 4,941 6,594 46 28.17 20.09 2.83547 × 101 ND Notre Dame ⬤ Hyperlink 325,729 1,497,134 46 8.92 6.96 9.68814 × 100 WC Wikipedia (en) ⬤ Feature 3,889,933 3,795,796 46 15.31 11.75 1.37377 × 101 CA Amazon (MDS) ⬤ Misc 334,863 925,872 47 14.85 11.73 Pa DBLP ⬤ Authorship 6,851,776 8,649,016 50 13.93 11.47 1.39057 × 101 PR Producers ⬤ Authorship 236,510 207,268 50 17.20 11.31 1.86413 × 101 WR Writers ⬤ Authorship 224,925 144,340 60 20.95 15.10 2.09247 × 101 ET Euroroad ⬤ Infrastructure 1,174 1,417 62 33.34 19.18 3.23879 × 101 Lk Linux kernel mailing list replies ⬤ Communication 63,399 1,096,440 63 7.79 5.19 DB DBpedia ⬤ Misc 3,966,924 13,820,853 67 6.27 5.19 6.50821 × 100 HUr Hudong related ⬤ Hyperlink 2,452,715 18,854,882 108 4.96 4.41 YS Yahoo songs ⬤ Rating 2,626,941 256,804,235 3.03718 × 100 Tit Wikipedia talk, Italian ⬤ Communication 863,846 3,067,680 7 3.67 3.05 Tzh Wikipedia talk, Chinese ⬤ Communication 1,219,241 2,284,546 8 3.72 2.74 Ten Wikipedia talk, English ⬤ Communication 2,987,535 24,981,163 9 Tes Wikipedia talk, Spanish ⬤ Communication 497,446 2,702,879 10 3.74 3.22 Tfr Wikipedia talk, French ⬤ Communication 1,420,367 4,641,928 11 3.54 2.59 Tde Wikipedia talk, German ⬤ Communication 519,403 6,729,794 13 3.75 3.30 WO WordNet ⬤ Lexical 146,005 656,999 16 6.32 5.36 7.00881 × 100 WT TREC WT10g ⬤ Hyperlink 1,601,787 8,063,026 112 11.10 8.70 1.07196 × 101 SF Stanford ⬤ Hyperlink 281,903 2,312,497 164 8.79 6.36 9.40826 × 100 BS Berkeley/Stanford ⬤ Hyperlink 685,230 7,600,595 208 9.79 7.21 1.03080 × 101 RD Pennsylvania ⬤ Infrastructure 1,088,092 1,541,898 794 528.61 312.58 5.45006 × 102 RO California ⬤ Infrastructure 1,965,206 2,766,607 865 511.07 315.89 4.95040 × 102 R1 Texas ⬤ Infrastructure 1,379,917 1,921,660 1,064 698.83 451.40 5.98472 × 102