%0 Journal Article %1 Orsini2013Evolution %A Orsini, Chiara %A Gregori, Enrico %A Lenzini, Luciano %A Krioukov, Dmitri %D 2013 %J IEEE/ACM Transactions on Networking %K k-dense internet clustering %P 1 %R 10.1109/TNET.2013.2282756 %T Evolution of the Internet k-Dense Structure %U http://dx.doi.org/10.1109/TNET.2013.2282756 %X As the Internet AS-level topology grows over time, some of its structural properties remain unchanged. Such time- invariant properties are generally interesting, because they tend to reflect some fundamental processes or constraints behind Internet growth. As has been shown before, the time-invariant structural properties of the Internet include some most basic ones, such as the degree distribution or clustering. Here we add to this time-invariant list a non-trivial property - k-dense decomposition. This property is derived from a recursive form of edge multiplicity, defined as the number of triangles that share a given edge. We show that after proper normalization, the k- dense decomposition of the Internet has remained stable over the last decade, even though the Internet size has approximately doubled, and so has the k-density of its k-densest core. This core consists mostly of content providers peering at Internet eXchange Points, and it only loosely overlaps with the high-degree or high-rank AS core, consisting mostly of tier-1 transit providers. We thus show that high degrees and high k-densities reflect two different Internet-specific properties of ASes (transit versus content providers), thus explaining strong fluctuations between degrees and k-densities, and the related observation that random graphs with the same degree distribution or even degree correlations as in the Internet, do not reproduce its k- dense decomposition. Therefore an interesting open question is what Internet topology models or generators can fully explain or at least reproduce the k-dense properties of the Internet.

@article{Orsini2013Evolution, abstract = {{As the Internet AS-level topology grows over time, some of its structural properties remain unchanged. Such time- invariant properties are generally interesting, because they tend to reflect some fundamental processes or constraints behind Internet growth. As has been shown before, the time-invariant structural properties of the Internet include some most basic ones, such as the degree distribution or clustering. Here we add to this time-invariant list a non-trivial property - k-dense decomposition. This property is derived from a recursive form of edge multiplicity, defined as the number of triangles that share a given edge. We show that after proper normalization, the k- dense decomposition of the Internet has remained stable over the last decade, even though the Internet size has approximately doubled, and so has the k-density of its k-densest core. This core consists mostly of content providers peering at Internet eXchange Points, and it only loosely overlaps with the high-degree or high-rank AS core, consisting mostly of tier-1 transit providers. We thus show that high degrees and high k-densities reflect two different Internet-specific properties of ASes (transit versus content providers), thus explaining strong fluctuations between degrees and k-densities, and the related observation that random graphs with the same degree distribution or even degree correlations as in the Internet, do not reproduce its k- dense decomposition. Therefore an interesting open question is what Internet topology models or generators can fully explain or at least reproduce the k-dense properties of the Internet.}}, added-at = {2019-06-10T14:53:09.000+0200}, archiveprefix = {arXiv}, author = {Orsini, Chiara and Gregori, Enrico and Lenzini, Luciano and Krioukov, Dmitri}, biburl = {https://www.bibsonomy.org/bibtex/2d6f9b968f5be454d43747747e56bdc33/nonancourt}, citeulike-article-id = {11966159}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/TNET.2013.2282756}, citeulike-linkout-1 = {http://arxiv.org/abs/1301.5938}, citeulike-linkout-2 = {http://arxiv.org/pdf/1301.5938}, day = 25, doi = {10.1109/TNET.2013.2282756}, eprint = {1301.5938}, interhash = {893e7b98eb513d86045a4d0bb3edbe36}, intrahash = {d6f9b968f5be454d43747747e56bdc33}, issn = {1558-2566}, journal = {IEEE/ACM Transactions on Networking}, keywords = {k-dense internet clustering}, month = jan, pages = 1, posted-at = {2013-01-28 10:48:02}, priority = {2}, timestamp = {2019-08-01T16:10:21.000+0200}, title = {{Evolution of the Internet k-Dense Structure}}, url = {http://dx.doi.org/10.1109/TNET.2013.2282756}, year = 2013 }