Models for Routing and Social Complex Networks

Georgios Amanatidis (Milena Mihail) - Models for complex communication and social networks are the object of intense study due to their simulation and predictive power. The first generation of such network models consisted of random graphs with skewed degree
distributions. However, in the last few years, objections have been raised concerning the generality of such models.

The Networking Conext: In networks designed under optimization, including many technological networks, fundamental metrics disagree with random graph models. Most notably, [ADGW03, LAWD04] (see also [New02, New03]), argued that several Internet topologies, which are highly optimized for cost and performance, are sharply different than power law random graphs. In particular, random graphs construct a dense core of nodes with very high degrees, while nodes of smaller degree are in periphery of the network. On the other hand, highly optimized topologies place low degree/high bandwidth routers at the center of the network, while high degree nodes are placed in the periphery to split the signal manyways towards the end users. Going one step further, [MKF+06, MKFV06] argued that a determining metric for a graph of given degrees to resemblea real network topology, is the specific number of of links between vertices of different degree classes.