Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTopologies and Price of Stability of Complex Strategic Networks with Localized Payoffs : Analytical and Simulation Studies
123
0
0.0
(
0
)
Added by
Rohith Vallam D
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. We call these payoffs as localized payoffs. In this game, the payoff of each individual captures (1) the gain from immediate neighbors, (2) the bridging benefits, and (3) the cost to form links. This implies that the payoff of each individual can be computed using only its single-hop neighbourhood information. Based on this simple model of network formation, our study explores the structure of networks that form, satisfying one or both of the properties, namely, pairwise stability and efficiency. We analytically prove the pairwise stability of several interesting network structures, notably, the complete bi-partite network, complete equi-k-partite network, complete network and cycle network, under various configurations of the model. We validate and extend these results through extensive simulations. We characterize topologies of efficient networks by drawing upon classical results from extremal graph theory and discover that the Turan graph (or the complete equi-bi-partite network) is the unique efficient network under many configurations of parameters. We examine the tradeoffs between topologies of pairwise stable networks and efficient networks using the notion of price of stability, which is the ratio of the sum of payoffs of the players in an optimal pairwise stable network to that of an efficient network. Interestingly, we find that price of stability is equal to 1 for almost all configurations of parameters in the proposed model; and for the rest of the configurations of the parameters, we obtain a lower bound of 0.5 on the price of stability. This leads to another key insight of this paper: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized payoffs.
rate research
Read More
Many real-world networks such as social networks consist of strategic agents. The topology of these networks often plays a crucial role in determining the ease and speed with which certain information driven tasks can be accomplished. Consequently, growing a stable network having a certain desired topology is of interest. Motivated by this, we study the following important problem: given a certain desired topology, under what conditions would best response link alteration strategies adopted by strategic agents, uniquely lead to formation of a stable network having the given topology. This problem is the inverse of the classical network formation problem where we are concerned with determining stable topologies, given the conditions on the network parameters. We study this interesting inverse problem by proposing (1) a recursive model of network formation and (2) a utility model that captures key determinants of network formation. Building upon these models, we explore relevant topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers. We derive a set of sufficient conditions under which these topologies uniquely emerge, study their social welfare properties, and investigate the effects of deviating from the derived conditions.
Networks are versatile representations of the interactions between entities in complex systems. Cycles on such networks represent feedback processes which play a central role in system dynamics. In this work, we introduce a measure of the importance of any individual cycle, as the fraction of the total information flow of the network passing through the cycle. This measure is computationally cheap, numerically well-conditioned, induces a centrality measure on arbitrary subgraphs and reduces to the eigenvector centrality on vertices. We demonstrate that this measure accurately reflects the impact of events on strategic ensembles of economic sectors, notably in the US economy. As a second example, we show that in the protein-interaction network of the plant Arabidopsis thaliana, a model based on cycle-centrality better accounts for pathogen activity than the state-of-art one. This translates into pathogen-targeted-proteins being concentrated in a small number of triads with high cycle-centrality. Algorithms for computing the centrality of cycles and subgraphs are available for download.
Transmission of disease, spread of information and rumors, adoption of new products, and many other network phenomena can be fruitfully modeled as cascading processes, where actions chosen by nodes influence the subsequent behavior of neighbors in the network graph. Current literature on cascades tends to assume nodes choose myopically based on the state of choices already taken by other nodes. We examine the possibility of strategic choice, where agents representing nodes anticipate the choices of others who have not yet decided, and take into account their own influence on such choices. Our study employs the framework of Chierichetti et al. [2012], who (under assumption of myopic node behavior) investigate the scheduling of node decisions to promote cascades of product adoptions preferred by the scheduler. We show that when nodes behave strategically, outcomes can be extremely different. We exhibit cases where in the strategic setting 100% of agents adopt, but in the myopic setting only an arbitrarily small epsilon % do. Conversely, we present cases where in the strategic setting 0% of agents adopt, but in the myopic setting (100-epsilon)% do, for any constant epsilon > 0. Additionally, we prove some properties of cascade processes with strategic agents, both in general and for particular classes of graphs.
While social interactions are critical to understanding consumer behavior, the relationship between social and commerce networks has not been explored on a large scale. We analyze Taobao, a Chinese consumer marketplace that is the worlds largest e-commerce website. What sets Taobao apart from its competitors is its integrated instant messaging tool, which buyers can use to ask sellers about products or ask other buyers for advice. In our study, we focus on how an individuals commercial transactions are embedded in their social graphs. By studying triads and the directed closure process, we quantify the presence of information passing and gain insights into when different types of links form in the network. Using seller ratings and review information, we then quantify a price of trust. How much will a consumer pay for transaction with a trusted seller? We conclude by modeling this consumer choice problem: if a buyer wishes to purchase a particular product, how does (s)he decide which store to purchase it from? By analyzing the performance of various feature sets in an information retrieval setting, we demonstrate how the social graph factors into understanding consumer behavior.
Stochastic processes can model many emerging phenomena on networks, like the spread of computer viruses, rumors, or infectious diseases. Understanding the dynamics of such stochastic spreading processes is therefore of fundamental interest. In this work we consider the wide-spread compartment model where each node is in one of several states (or compartments). Nodes change their state randomly after an exponentially distributed waiting time and according to a given set of rules. For networks of realistic size, even the generation of only a single stochastic trajectory of a spreading process is computationally very expensive. Here, we propose a novel simulation approach, which combines the advantages of event-based simulation and rejection sampling. Our method outperforms state-of-the-art methods in terms of absolute run-time and scales significantly better, while being statistically equivalent.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
