Social evolution - Has nature ever rewound the tape?

Social insects such as ants, bees, wasps and termites exhibit extreme forms of altruism where some individuals remain sterile and assist other individuals in reproduction. Hamilton's inclusive fitness theory provides a powerful framework for investigating the evolution of such altruism. Using the paper wasp Ropalidia marginata, we have quantified and delineated the role of ecological, physiological, genetic and demographic factors in social evolution. An interesting feature of the models we have developed is their symmetry so that either altruism or selfishness can evolve, depending on the numerical values of various parameters. This suggests that selfish/solitary behaviour must occasionally re-emerge even from the eusocial state, It is useful to contemplate expected intermediate states during such potential reversals. We can perhaps envisage three successive steps in such a hypothetical process: i) workers revolt against the hegemony of the queen and challenge her status as the sole reproductive, ii) workers stop producing queens and one or more of them function as egg layers (functional queen/s) capable of producing both haploid as well as diploid offspring and iii) social evolution reverses completely so that a eusocial species becomes solitary, at least facultatively. It appears that the third step, namely transition from eusociality to the solitary state, is rare and has been restricted to transitions from the primitively eusocial state only. The absence of transitions from the highly eusocial state to the solitary state may be attributed to a number of 'preventing mechanisms' such as (a) queen control of workers (b) loss of spermathecae and ability to mate (c) morphological specialization (d) caste polyethism and (e) homeostasis, which must each make the transition difficult and, taken together, perhaps very difficult. However, the discovery of a transition from the highly eusocial to the solitary state can hardly he ruled out, given that little or no effort has gone into its detection. In this paper I discuss social evolution and its possible reversal and cite potential examples of stages in the transition from the social to the solitary.

A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient. Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.

Influence limitation in multi-campaign social networks: A Shapley value based approach

We investigate the problem of influence limitation in the presence of competing campaigns in a social network. Given a negative campaign which starts propagating from a specified source and a positive/counter campaign that is initiated, after a certain time delay, to limit the the influence or spread of misinformation by the negative campaign, we are interested in finding the top k influential nodes at which the positive campaign may be triggered. This problem has numerous applications in situations such as limiting the propagation of rumor, arresting the spread of virus through inoculation, initiating a counter-campaign against malicious propaganda, etc. The influence function for the generic influence limitation problem is non-submodular. Restricted versions of the influence limitation problem, reported in the literature, assume submodularity of the influence function and do not capture the problem in a realistic setting. In this paper, we propose a novel computational approach for the influence limitation problem based on Shapley value, a solution concept in cooperative game theory. Our approach works equally effectively for both submodular and non-submodular influence functions. Experiments on standard real world social network datasets reveal that the proposed approach outperforms existing heuristics in the literature. As a non-trivial extension, we also address the problem of influence limitation in the presence of multiple competing campaigns.

Scalable Preference Aggregation in Social Networks

In social choice theory, preference aggregation refers to computing an aggregate preference over a set of alternatives given individual preferences of all the agents. In real-world scenarios, it may not be feasible to gather preferences from all the agents. Moreover, determining the aggregate preference is computationally intensive. In this paper, we show that the aggregate preference of the agents in a social network can be computed efficiently and with sufficient accuracy using preferences elicited from a small subset of critical nodes in the network. Our methodology uses a model developed based on real-world data obtained using a survey on human subjects, and exploits network structure and homophily of relationships. Our approach guarantees good performance for aggregation rules that satisfy a property which we call expected weak insensitivity. We demonstrate empirically that many practically relevant aggregation rules satisfy this property. We also show that two natural objective functions in this context satisfy certain properties, which makes our methodology attractive for scalable preference aggregation over large scale social networks. We conclude that our approach is superior to random polling while aggregating preferences related to individualistic metrics, whereas random polling is acceptable in the case of social metrics.

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.

Evolution of social behaviour in the primitively eusocial wasp Ropalidia marginata: do we need to look beyond kin selection?

Ropalidia marginata is a primitively eusocial wasp widely distributed in peninsular India. Although solitary females found a small proportion of nests, the vast majority of new nests are founded by small groups of females. In suchmultiple foundress nests, a single dominant female functions as the queen and lays eggs, while the rest function as sterile workers and care for the queen's brood. Previous attempts to understand the evolution of social behaviour and altruism in this species have employed inclusive fitness theory (kin selection) as a guiding framework. Although inclusive fitness theory is quite successful in explaining the high propensity of the wasps to found nests in groups, several features of their social organization suggest that forces other than kin selection may also have played a significant role in the evolution of this species. These features include lowering of genetic relatedness owing to polyandry and serial polygyny, nest foundation by unrelated individuals, acceptance of young non-nest-mates, a combination of well-developed nest-mate recognition and lack of intra-colony kin recognition, a combination of meek and docile queens and a decentralized self-organized work force, long reproductive queues with cryptic heir designates and conflict-free queen succession, all resulting in extreme intra-colony cooperation and inter-colony conflict.

Cost effective campaigning in social networks

Campaigners are increasingly using online social networking platforms for promoting products, ideas and information. A popular method of promoting a product or even an idea is incentivizing individuals to evangelize the idea vigorously by providing them with referral rewards in the form of discounts, cash backs, or social recognition. Due to budget constraints on scarce resources such as money and manpower, it may not be possible to provide incentives for the entire population, and hence incentives need to be allocated judiciously to appropriate individuals for ensuring the highest possible outreach size. We aim to do the same by formulating and solving an optimization problem using percolation theory. In particular, we compute the set of individuals that are provided incentives for minimizing the expected cost while ensuring a given outreach size. We also solve the problem of computing the set of individuals to be incentivized for maximizing the outreach size for given cost budget. The optimization problem turns out to be non trivial; it involves quantities that need to be computed by numerically solving a fixed point equation. Our primary contribution is, that for a fairly general cost structure, we show that the optimization problems can be solved by solving a simple linear program. We believe that our approach of using percolation theory to formulate an optimization problem is the first of its kind. (C) 2016 Elsevier B.V. All rights reserved.