| This dissertation focuses on theoretical issues of modeling and solving problems on real-world networks where computational intractability limits our current analysis capabilities. We present work on percolation properties of random structures and pure combinatorial problems, as well as algorithms on networks. We also present work in socio-economic sciences: mechanism design in online auctions and game-theoretical analysis of games over large sets of players.;The first part of our work, on Geographical Threshold Graphs, provides a combinatorial analysis of a static model for networks that includes both geometric information and node weight information. The model allows properties such as diameter or degree distribution to be tuned. We derive conditions and bounds for the absence and existence of the giant component, as well as for connectivity, and give an explicit expression for the clustering coefficient. We also analyze a coloring algorithm together with the clique number, in order to derive bounds on the chromatic number.;We then consider a game-theoretical analysis of congestion games over large sets of players by studying the price of mediation, as well as mechanism design in online auctions in the presence of reputation management. We define the optimal gambler/seller problem and derive optimal player's strategies for it.;Finally, we study network synchronization, presenting near-optimal solutions to the problem of minimizing radio use in wireless network deployment. Improving upon previous results, we show optimal use of the radio for two processors and near-optimal use of the radio for synchronization of an arbitrary number of processors. |
