Game theoretic, decentralized, local information based algorithm for community detection in social graphs

Motivated by the observation that communities in real world social networks form due to actions of rational individuals in networks, we propose a novel game theory inspired algorithm to determine communities in networks. The algorithm is decentralized and only uses local information at each node. We show the efficacy of the proposed algorithm through extensive experimentation on several real world social network data sets.

Identifying services from Legacy batch applications

Transaction processing is a key constituent of the IT workload of commercial enterprises (e.g., banks, insurance companies). Even today, in many large enterprises, transaction processing is done by legacy "batch" applications, which run offline and process accumulated transactions. Developers acknowledge the presence of multiple loosely coupled pieces of functionality within individual applications. Identifying such pieces of functionality (which we call "services") is desirable for the maintenance and evolution of these legacy applications. This is a hard problem, which enterprises grapple with, and one without satisfactory automated solutions. In this paper, we propose a novel static-analysis-based solution to the problem of identifying services within transaction-processing programs. We provide a formal characterization of services in terms of control-flow and data-flow properties, which is well-suited to the idioms commonly exhibited by business applications. Our technique combines program slicing with the detection of conditional code regions to identify services in accordance with our characterization. A preliminary evaluation, based on a manual analysis of three real business programs, indicates that our approach can be effective in identifying useful services from batch applications.

Sustaining cooperation on networks: an analytical study based on evolutionary game theory

We analytically study the role played by the network topology in sustaining cooperation in a society of myopic agents in an evolutionary setting. In our model, each agent plays the Prisoner's Dilemma (PD) game with its neighbors, as specified by a network. Cooperation is the incumbent strategy, whereas defectors are the mutants. Starting with a population of cooperators, some agents are switched to defection. The agents then play the PD game with their neighbors and compute their fitness. After this, an evolutionary rule, or imitation dynamic is used to update the agent strategy. A defector switches back to cooperation if it has a cooperator neighbor with higher fitness. The network is said to sustain cooperation if almost all defectors switch to cooperation. Earlier work on the sustenance of cooperation has largely consisted of simulation studies, and we seek to complement this body of work by providing analytical insight for the same. We find that in order to sustain cooperation, a network should satisfy some properties such as small average diameter, densification, and irregularity. Real-world networks have been empirically shown to exhibit these properties, and are thus candidates for the sustenance of cooperation. We also analyze some specific graphs to determine whether or not they sustain cooperation. In particular, we find that scale-free graphs belonging to a certain family sustain cooperation, whereas Erdos-Renyi random graphs do not. To the best of our knowledge, ours is the first analytical attempt to determine which networks sustain cooperation in a population of myopic agents in an evolutionary setting.

Game theoretic analysis of collusions in nonneutral networks

This paper studies the impact of exclusive contracts between a content provider (CP) and an internet service provider (ISP) in a nonneutral network. We consider a simple linear demand function for the CPs. We studywhen an exclusive contract is benefcial to the colluding pair and evaluate its impact on the noncolluding players at equilibrium. For the case of two CPs and one ISP we show that collusion may not always be benefcial. We derive an explicit condition in terms of the advertisement revenues of the CPs that tells when a collusion is proftable to the colluding entities.

Loss of frugivore seed dispersal services under climate change

The capacity of species to track shifting climates into the future will strongly influence outcomes for biodiversity under a rapidly changing climate. However, we know remarkably little about the dispersal abilities of most species and how these may be influenced by climate change. Here we show that climate change is projected to substantially reduce the seed dispersal services provided by frugivorous vertebrates in rainforests across the Australian Wet Tropics. Our model projections show reductions in both median and long-distance seed dispersal, which may markedly reduce the capacity of many rainforest plant species to track shifts in suitable habitat under climate change. However, our analyses suggest that active management to maintain the abundances of a small set of important frugivores under climate change could markedly reduce the projected loss of seed dispersal services and facilitate shifting distributions of rainforest plant species.

Context dependency of rewards and services in an Indian ant-plant interaction: southern sites favour the mutualism between plants and ants

Protection-based ant-plant mutualisms may vary in strength due to differences in ant rewards, abundance of protective ants and herbivory pressure. We investigated geographical and temporal variation in host plant traits and herbivory pressure at five sites spanning the distribution range of the myrmecophyte Humboldtia brunonis (Fabaceae) in the Indian Western Ghats. Southern siteshad, onaverage, 2.4 times greater abundance of domatia-bearing individuals, 1.6 times greater extrafloral nectary numbers per leaf, 1.2 times larger extrafloral nectary sizes, 2.2 times greater extrafloral nectar (EFN) volumes and a two-fold increase in total amino acid and total sugar concentrations in EFN compared with northern sites. Astrong protection-based mutualismwith ants occurred at only one southern site where herbivory was highest, suggesting that investments in attracting ants correlate with anti-herbivore benefits gained from the presence of protective ants. Our results confirm a temporally stable north-south gradient in myrmecophytic traits in this ant-plant as several of these traits were re-sampled after a 5-y interval. However, the chemical composition of EFN varied at both spatial and short-term temporal scales suggesting that only repeated measurements of rewards such as EFN can reveal the real spectrum of trait variation in an ant-plant mutualistic system.

PriDyn: Enabling Differentiated I/O Services in Cloud Using Dynamic Priorities

Virtualization is one of the key enabling technologies for Cloud computing. Although it facilitates improved utilization of resources, virtualization can lead to performance degradation due to the sharing of physical resources like CPU, memory, network interfaces, disk controllers, etc. Multi-tenancy can cause highly unpredictable performance for concurrent I/O applications running inside virtual machines that share local disk storage in Cloud. Disk I/O requests in a typical Cloud setup may have varied requirements in terms of latency and throughput as they arise from a range of heterogeneous applications having diverse performance goals. This necessitates providing differential performance services to different I/O applications. In this paper, we present PriDyn, a novel scheduling framework which is designed to consider I/O performance metrics of applications such as acceptable latency and convert them to an appropriate priority value for disk access based on the current system state. This framework aims to provide differentiated I/O service to various applications and ensures predictable performance for critical applications in multi-tenant Cloud environment. We demonstrate through experimental validations on real world I/O traces that this framework achieves appreciable enhancements in I/O performance, indicating that this approach is a promising step towards enabling QoS guarantees on Cloud storage.

Novel Biobjective Clustering (BiGC) Based on Cooperative Game Theory

We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Pricing and Power allocation in Femtocells using Stackelberg Game Theory

We consider a system with multiple Femtocells operating in a Macrocell. The transmissions in one Femtocell interfere with its neighboring Femtocells as well as with the Macrocell Base Station. We model Femtocells as selfish nodes and the Macrocell Base Station protects itself by pricing subchannels for each usage. We use Stackelberg game model to study this scenario and obtain equilibrium policies that satisfy certain quality of service.