English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Kleinberg proposed a family of small-world networks to explain thenavigability of large-scale real-world social networks. However, the underlyingmechanism that drives real networks to be navigable is not yet well understood.In this paper, we present a game theoretic model for the formation of navigablesmall world networks. We model the network formation as a Distance-ReciprocityBalanced (DRB) game in which people seek for both high reciprocity andlong-distance relationships. We show that the game has only two Nashequilibria: One is the navigable small-world network, and the other is therandom network in which each node connects with each other node with equalprobability. We further show that the navigable small world is very stable ---(a) no collusion of any size would benefit from deviating from it; and (b)after an arbitrary deviations of a large random set of nodes, the network wouldreturn to the navigable small world as soon as every node takes onebest-response step. In contrast, for the random network, a small groupcollusion or random perturbations is guaranteed to move the network to thenavigable network as soon as every node takes one best-response step. Moreover,we show that navigable small world has much better social welfare than therandom network, and provide the price-of-anarchy and price-of-stability resultsof the game. Our empirical evaluation demonstrates that the system alwaysconverges to the navigable network even when limited or no information aboutother players' strategies is available, and the DRB game simulated on thereal-world network leads to navigability characteristic that is very close tothat of the real network. Our theoretical and empirical analyses provideimportant new insight on the connection between distance, reciprocity andnavigability in social networks.

A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity