Geometric Selfish Network Creation (GEONET)

点击翻译按钮获取中文摘要

Many important networks, most prominently the Internet or (online) social networks, have not been created by central design and there is no central authority governing them. Instead, such networks emerged from the uncoordinated interaction of many selfish agents which may modify parts of the networks to suit their individual needs. A recent research trend in the intersection of Theoretical Computer Science, Mathematics and Economics is to model and analyze the creation of such networks from a game-theoretic point of view. The network creation process is considered as a non-cooperative strategic game and the emerging networks are derived from the game's equilibrium states. In the last two decades many such models have been proposed and analyzed but all of them incorporate strong simplifying assumptions and some of their predictions are not in line with empirical observations from real-world networks. One of the main reasons for this is that previous work neglected that nodes in real-world networks are located in some underlying (usually metric) space and that this geometric setting has a strong influence on the created networks. The hereby proposed project aims at taking the next step towards more realistic models for selfish network creation by investigating the impact of an underlying geometry as novel feature. This allows to model and to analyze the creation of diverse networks ranging from fiber-optic communication networks to (online) social networks.The insights gained in this research project shall lead to an improved understanding of various types of real-world networks and they shall be valuable for designing new (distributed) algorithms for the decentralized creation of efficient and robust communication networks.