• internet AS-topology
• graph theory
• dk-graphs
• community detection

The study of the structural characteristics of the Internet topology at the Autonomous System (AS) level of abstraction is an important and interesting subject that has attracted significant interest over the last few years. Above all, a deep knowledge of the Internet underlying structure helps researchers in designing a more accurate model of the network; as a result, engineers can design applications and protocols that can take into account the underlying structure and test their projects on synthetic graphs, thereby developing more efficient algorithms. A significant challenge for researchers analyzing the Internet is how to interpret the global organization of the graph as the coexistence of its structural blocks associated with more highly interconnected parts, namely communities. While a huge number of papers have already been published on the issue of community detection, very little attention has so far been devoted to the discovery and interpretation of Internet communities.
The contribution of this work is twofold. First, we study the evolution of the Internet AS-level topology over the last 9 years by means of two innovative approaches: the k-dense method and the dK-analysis. Second, we focus on substructures that play a key role in the Internet connectivity, and we investigate the classes of the ASes and the nature of the connections that create such communities. We find that as the Internet grows over time, some of its structural properties remain unchanged. Although the size of the network, as well as the kMAX -dense index (an index of the maximum level of density reached in a network), has doubled over the last 9 years, we show that after proper normalizations the k-dense decomposition has remained stable. Besides, we provided a clear evidence that the formation of denser and denser sub-graphs over time has been triggered by the proliferation of Internet eXchange Points (IXP) and public peering connections. We found that ASes within most densely-connected substructures are usually Network Service Providers, Content Providers, or Content Delivery Networks; in addition, all of them participate to at least one IXP.