Computer Science – Computer Science and Game Theory
Scientific paper
2012-01-09
Computer Science
Computer Science and Game Theory
Preprint submitted in International Colloquium on Automata, Languages and Programming (ICALP 2012). Preliminary version presen
Scientific paper
One of the key problems addressed in the literature on social network formation is: given a set of self-interested nodes and a model of social network formation, what topologies would be pairwise stable and hence are likely to emerge. A pairwise stable network is one in which the nodes do not have any incentive to delete any of their links and no two unconnected nodes would want to create a link between them. In this paper, we study the following reverse problem: given a desired network topology, what conditions are required so that best response strategies played by self-interested agents will lead to formation of a network with that topology. We propose a model of recursive network formation in which nodes enter the network sequentially and a utility model that captures principal determinants of network formation, namely (1) benefits from immediate neighbors, (2) costs of maintaining links with immediate neighbors, (3) benefits from indirect neighbors, (4) bridging benefits, and (5) network entry fee. Based on this model, we analyze three common network topologies, namely star graph, complete graph, and bipartite Tur\'an graph, and derive a set of sufficient conditions under which these network topologies emerge.
Dhamal Swapnil
Narahari Yadati
No associations
LandOfFree
Sufficient Conditions for Formation of Social Networks with a Desired Topology does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sufficient Conditions for Formation of Social Networks with a Desired Topology, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sufficient Conditions for Formation of Social Networks with a Desired Topology will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-641897