Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Network formation in the presence of contagious risk
Blume L., Easley D., Kleinberg J., Kleinberg R., Tardos É. ACM Transactions on Economics and Computation1 (2):1-20,2013.Type:Article
Date Reviewed: Nov 7 2013

All interconnected networks may reap the benefits of neighboring nodes. But these complex networks, some of which have millions of nodes and edges, risk failure due to a very few compromised or flawed nodes. For example, replica attacks in mobile ad hoc networks (MANETs) can compromise an entire network with one replicated node [1]. This paper presents formulations for strategic network formation and provides asymptotically tight bounds on welfare for both the optimal and stable networks. The authors examine cascading failures in socially optimal networks where stable graphs are found beyond the transition phase from optimal to stable, where most losses in the network occur. The paper also identifies the risk of over-linking in the networks, which involves high and complex connectivity between the nodes. The entire model is applied to clusters and anonymized market structures to identify the trade-offs.

The authors propose a model that uses the Rawlsian notion (ranking social states) [2] of welfare. The model creates payoffs as well as failures through a random process in the network, where the payoff (or active) probability is p and the failure (or blocked) probability is 1-p. The model calculates the minimum payoff of any node in the network through a notion of minimum welfare, which is particularly convenient when a noncooperative model is employed by the network. The authors set two standards for the model to work: 1) a node should not lose all its incident links to obtain higher payoff, and 2) there should be no pair of nodes without a connecting edge when adding this edge would increase the nodes’ payoffs. These two standards become the basic rules for the strategic network formation model.

The authors adopt random graph techniques to apply to a random subgraph of an arbitrary graph to derive the upper bound for the optimal minimum welfare, where active-edge paths are calculated based on the number of reachable active nodes. Theorems and lemmas support the upper bound values of the model. The authors also present an analysis of payoff and failure rates in cluster versus anonymized networks under their model. They prove that disjoint cluster networks achieve higher payoff than anonymous networks because the clusters are constructed beyond the transition phase at which the anonymous networks will have negative effects on the payoffs. Finally, the authors derive an upper bound for the minimum welfare of stable networks.

The paper is missing any example of a real-life application of the model. Other than that, the paper derives important theoretical results and upper bounds for an efficient strategic network formation with clear risk analyses. The upper bound derivations and analyses prove that the model is efficient in strategic network formation. Although the authors present the comparative network analysis for cluster and anonymous networks as a generic case for their model, the applicability of the model is yet to be seen.

Reviewer:  Ganapathy Mani Review #: CR141709 (1401-0083)
1) Xing, K.; Cheng, X. From time domain to space domain: detecting replica attacks in mobile ad hoc networks. In Proc. of INFOCOM 2010. IEEE, 2010, 1–9.
2) Michelman, F. I. In pursuit of constitutional welfare rights: one view of Rawls’ theory of justice. University of Pennsylvania Law Review 121, 5(1973), 962–1019.
Bookmark and Share
General (F.0 )
Economics (J.4 ... )
Graph Theory (G.2.2 )
Network Architecture And Design (C.2.1 )
Would you recommend this review?
Other reviews under "General": Date
Introduction to computer theory (revised ed.)
Cohen D., John Wiley & Sons, Inc., New York, NY, 1991. Type: Book (9780471510109)
Feb 1 1993
Introduction to computer theory
Cohen D., John Wiley & Sons, Inc., New York, NY, 1986. Type: Book (9789780471802716)
Feb 1 1987
Theory of computation: formal languages, automata, and complexity
Brookshear J., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1989. Type: Book (9789780805301434)
Jan 1 1990

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