Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A game theoretic model for the formation of navigable small-world networks--the tradeoff between distance and reciprocity
Yang Z., Chen W. ACM Transactions on Internet Technology18 (4):1-38,2018.Type:Article
Date Reviewed: Apr 25 2019

The concept of small-world networks has been developed to help explain how real whole-world social networks manage to be “navigable.” By navigable I mean the ease with which any two people can be connected with seemingly few intermediate hops. One challenge with small-world networks is explaining what drives their formation. Game theoretic models are useful simulation tools that show how equilibria can develop across a multitude of actors, each trying to optimize some cost function. The authors use a game theoretic model to create a navigable small-world network, showing that the navigable network is a natural equilibrium state for their selected agent strategy.

Agents independently control their own connection preference parameter, which defines the relative probability that an agent will choose to connect to other agents far away versus agents in close geographic proximity. The payoff function developed by the authors is the product of the average distance of nodes to their long-range contacts (creating a preference for connecting with agents geographically remote) and the probability of forming reciprocal relationships with these long-range contacts. It is this latter probability factor that drives the model toward uniformity.

The authors show that under this payoff function the game has only two equilibria. The first is the navigable small-world network, which is resistant to both permutations and agent collusion. The second equilibrium is the random network that is shown to be unstable, where any permutations will steer it toward the navigable small-world network.

The paper presents an altogether intuitive result given the choice of payoff function, which the authors illustrate in detail through various tests and simulations.

Reviewer:  Bernard Kuc Review #: CR146546 (1907-0281)
Bookmark and Share
  Editor Recommended
Featured Reviewer
 
 
Network Problems (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Network Problems": Date
The complexity of the residual node connectedness reliability problem
Sutner K., Satyanarayana A., Suffel C. SIAM Journal on Computing 20(1): 149-155, 1991. Type: Article
Mar 1 1992
Fast approximation algorithms for multicommodity flow problems
Leighton T., Stein C., Makedon F., Tardos É., Plotkin S., Tragoudas S.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1111991. Type: Proceedings
Jul 1 1992
Computing the strength of a graph
Gusfield D. SIAM Journal on Computing 20(4): 639-654, 1991. Type: Article
Apr 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy