Unilateral vs. Bilateral link-formation: Bridging the gap

We provide a model that bridges the gap between two benchmark models of strategic network formation: Jackson and Wolinsky' s model based on bilateral formation of links, and Bala and Goyal's two-way fl ow model, where links can be unilaterally formed. In the model introduced and studied here a link can be created unilaterally. When it is only supported by one of the two players the fl ow through the link suffers a certain decay, but when it is supported by both the fl ow runs without friction. When the decay in links supported by only one player is maximal (i.e. there is no flow) we have Jackson and Wolinsky 's connections model without decay, while when flow in such links is perfect we have Bala and Goyal' s two-way flow model. We study Nash, strict Nash and pairwise stability for the intermediate models. Efficiency and dynamics are also examined.

From bilateral two-way to unilateral one-way flow link-formation

Documento de trabajo

A Unifying model of strategic network formation

Documento de trabajo

Efficiency vs. Stability in a Mixed Network Formation Model

Documentos de Trabajo

The impact of liberalizing cost-saharing on basic models of network formation

This paper studies the impact of "liberalizing " the cost-sharing of links on some basic models of network formation. This is done in a setting where both doubly supported and singly supported links are possible, and which includes the two seminal models of network formation by Jackson and Wolinsky and Bala and Goyal as extreme cases. In this setting, the notion of pairwise stability is extended and it is proved that liberalizing cost-sharing for doubly supported links widens the range of values of the parameters where the efficient networks formed by such type of links are pairwise stable, while the range of values of the parameters where the efficient networks formed by singly supported links are pairwise stable shrinks, but the region where the latter are e¢ cient and pairwise stable remains the same.

Stabilization of the i-motif structure by the intra-strand cross-link formation

The i-motif structures are formed by oligonucleotides containing cytosine tracts under acidic conditions. The folding of the i-motif under physiological conditions is of great interest because of its biological role. In this study, we investigated the effect of the intra-strand cross-link on the stability of the i-motif structure. The 4-vinyl-substituted analog of thymidine (T-vinyl) was incorporated into the 5′-end of the human telomere complementary strand, which formed the intra-strand cross-link with the internal adenine. The intra-strand cross-linked i-motif displayed CD spectra similar to that of the natural i-motif at acidic pH, which was transformed into a random coil with the increasing pH. The pH midpoint for the transition from the i-motif to random coil increased from pH 6.1 for the natural one to pH 6.8 for the cross-linked one. The thermodynamic parameters were obtained by measuring the thermal melting behaviors by CD and UV, and it was determined that the intra-strand cross-linked i-motif is stabilized due to a favorable entropy effect. Thus, this study has clearly indicated the validity of the intra-strand cross-linking for stabilization of the i-motif structure.

Nash equilibria of network formation games under consent

We investigate the Nash equilibria of game theoretic models of network formation based on explicit consent in link formation. These so-called “consent models” explicitly take account of link formation costs. We provide characterizations of Nash equilibria of such consent models under both one-sided and two-sided costs of link formation. We relate these equilibrium concepts to link-based stability concepts, in particular strong link deletion proofness.

Identity and Link Reliability in Social Networks

This paper considers a non-cooperative network formation game where identity is introduced as a single dimension to capture the characteristics of a player in the network. Players access to the benefits from the link through direct and indirect connections. We consider cases where cost of link formation paid by the initiator. Each player is allowed to choose their commitment level to their identities. The cost of link formation decreases as the players forming the link share the same identity and higher commitment levels. We then introduce link imperfections to the model. We characterize the Nash networks and we find that the set of Nash networks are either singletons with no links formed or separated blocks or components with mixed blocks or connected.

On the Emergence of Highly Variable Distributions in the Autonomous System Topology

Recent studies have noted that vertex degree in the autonomous system (AS) graph exhibits a highly variable distribution [15, 22]. The most prominent explanatory model for this phenomenon is the Barabási-Albert (B-A) model [5, 2]. A central feature of the B-A model is preferential connectivity—meaning that the likelihood a new node in a growing graph will connect to an existing node is proportional to the existing node’s degree. In this paper we ask whether a more general explanation than the B-A model, and absent the assumption of preferential connectivity, is consistent with empirical data. We are motivated by two observations: first, AS degree and AS size are highly correlated [11]; and second, highly variable AS size can arise simply through exponential growth. We construct a model incorporating exponential growth in the size of the Internet, and in the number of ASes. We then show via analysis that such a model yields a size distribution exhibiting a power-law tail. In such a model, if an AS’s link formation is roughly proportional to its size, then AS degree will also show high variability. We instantiate such a model with empirically derived estimates of growth rates and show that the resulting degree distribution is in good agreement with that of real AS graphs.

On the Geographic Location of Internet Resources

One relatively unexplored question about the Internet's physical structure concerns the geographical location of its components: routers, links and autonomous systems (ASes). We study this question using two large inventories of Internet routers and links, collected by different methods and about two years apart. We first map each router to its geographical location using two different state-of-the-art tools. We then study the relationship between router location and population density; between geographic distance and link density; and between the size and geographic extent of ASes. Our findings are consistent across the two datasets and both mapping methods. First, as expected, router density per person varies widely over different economic regions; however, in economically homogeneous regions, router density shows a strong superlinear relationship to population density. Second, the probability that two routers are directly connected is strongly dependent on distance; our data is consistent with a model in which a majority (up to 75-95%) of link formation is based on geographical distance (as in the Waxman topology generation method). Finally, we find that ASes show high variability in geographic size, which is correlated with other measures of AS size (degree and number of interfaces). Among small to medium ASes, ASes show wide variability in their geographic dispersal; however, all ASes exceeding a certain threshold in size are maximally dispersed geographically. These findings have many implications for the next generation of topology generators, which we envisage as producing router-level graphs annotated with attributes such as link latencies, AS identifiers and geographical locations.

Endogenous Two-Sided Markets with Repeated Transactions

We consider homogeneous two-sided markets, in which connected buyer-seller pairs bargain and trade repeatedly. In this infinite market game with exogenous matching probabilities and a common discount factor, we prove the existence of equilibria in stationary strategies. The equilibrium payoffs are given implicitly as a solution to a system of linear equations. Then, we endogenize the matching mechanism in a link formation stage that precedes the market game. When agents are sufficiently patient and link costs are low, we provide an algorithm to construct minimally connected networks that are pairwise stable with respect to the expected payoffs in the trading stage. The constructed networks are essentially efficient and consist of components with a constant buyer-seller ratio. The latter ratio increases (decreases) for a buyer (seller) that deletes one of her links in a pairwise stable component.

Percolation in a network with long-range connections: Implications for cytoskeletal structure and function

Cell shape, signaling, and integrity depend on cytoskeletal organization. In this study we describe the cytoskeleton as a simple network of filamentary proteins (links) anchored by complex protein structures (nodes). The structure of this network is regulated by a distance-dependent probability of link formation as P = p/d(s), where p regulates the network density and s controls how fast the probability for link formation decays with node distance (d). It was previously shown that the regulation of the link lengths is crucial for the mechanical behavior of the cells. Here we examined the ability of the two-dimensional network to percolate (i.e. to have end-to-end connectivity), and found that the percolation threshold depends strongly on s. The system undergoes a transition around s = 2. The percolation threshold of networks with s < 2 decreases with increasing system size L, while the percolation threshold for networks with s > 2 converges to a finite value. We speculate that s < 2 may represent a condition in which cells can accommodate deformation while still preserving their mechanical integrity. Additionally, we measured the length distribution of F-actin filaments from publicly available images of a variety of cell types. In agreement with model predictions, cells originating from more deformable tissues show longer F-actin cytoskeletal filaments. (C) 2008 Elsevier B.V. All rights reserved.

Interacting helical faces of subunits a and c in the F1Fo ATP synthase of Escherichia coli defined by disulfide cross-linking

Subunits a and c of Fo are thought to cooperatively catalyze proton translocation during ATP synthesis by the Escherichia coli F1Fo ATP synthase. Optimizing mutations in subunit a at residues A217, I221, and L224 improves the partial function of the cA24D/cD61G double mutant and, on this basis, these three residues were proposed to lie on one face of a transmembrane helix of subunit a, which then interacted with the transmembrane helix of subunit c anchoring the essential aspartyl group. To test this model, in the present work Cys residues were introduced into the second transmembrane helix of subunit c and the predicted fourth transmembrane helix of subunit a. After treating the membrane vesicles of these mutants with Cu(1,10-phenanthroline)2SO4 at 0°, 10°, or 20°C, strong a–c dimer formation was observed at all three temperatures in membranes of 7 of the 65 double mutants constructed, i.e., in the aS207C/cI55C, aN214C/cA62C, aN214C/cM65C, aI221C/cG69C, aI223C/cL72C, aL224C/cY73C, and aI225C/cY73C double mutant proteins. The pattern of cross-linking aligns the helices in a parallel fashion over a span of 19 residues with the aN214C residue lying close to the cA62C and cM65C residues in the middle of the membrane. Lesser a–c dimer formation was observed in nine other double mutants after treatment at 20°C in a pattern generally supporting that indicated by the seven landmark residues cited above. Cross-link formation was not observed between helix-1 of subunit c and helix-4 of subunit a in 19 additional combinations of doubly Cys-substituted proteins. These results provide direct chemical evidence that helix-2 of subunit c and helix-4 of subunit a pack close enough to each other in the membrane to interact during function. The proximity of helices supports the possibility of an interaction between Arg210 in helix-4 of subunit a and Asp61 in helix-2 of subunit c during proton translocation, as has been suggested previously.

A comprehensive study of multiplicative attribute graph model

Graphs are powerful tools to describe social, technological and biological networks, with nodes representing agents (people, websites, gene, etc.) and edges (or links) representing relations (or interactions) between agents. Examples of real-world networks include social networks, the World Wide Web, collaboration networks, protein networks, etc. Researchers often model these networks as random graphs. In this dissertation, we study a recently introduced social network model, named the Multiplicative Attribute Graph model (MAG), which takes into account the randomness of nodal attributes in the process of link formation (i.e., the probability of a link existing between two nodes depends on their attributes). Kim and Lesckovec, who defined the model, have claimed that this model exhibit some of the properties a real world social network is expected to have. Focusing on a homogeneous version of this model, we investigate the existence of zero-one laws for graph properties, e.g., the absence of isolated nodes, graph connectivity and the emergence of triangles. We obtain conditions on the parameters of the model, so that these properties occur with high or vanishingly probability as the number of nodes becomes unboundedly large. In that regime, we also investigate the property of triadic closure and the nodal degree distribution.