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.

PIB: Profiling Influential Blogger in Online Social Networks, A Knowledge Driven Data Mining Approach

Online Social Networks (OSNs) facilitate to create and spread information easily and rapidly, influencing others to participate and propagandize. This work proposes a novel method of profiling Influential Blogger (IB) based on the activities performed on one's blog documents who influences various other bloggers in Social Blog Network (SBN). After constructing a social blogging site, a SBN is analyzed with appropriate parameters to get the Influential Blog Power (IBP) of each blogger in the network and demonstrate that profiling IB is adequate and accurate. The proposed Profiling Influential Blogger (PIB) Algorithm survival rate of IB is high and stable. (C) 2015 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

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.

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.

The evolution of complexity in social organization-A model using dominance-subordinate behavior in two social wasp species

Dominance and subordinate behaviors are important ingredients in the social organizations of group living animals. Behavioral observations on the two eusocial species Ropalidia marginata and Ropalidia cyathiformis suggest varying complexities in their social systems. The queen of R. cyathiformis is an aggressive individual who usually holds the top position in the dominance hierarchy although she does not necessarily show the maximum number of acts of dominance, while the R. marginata queen rarely shows aggression and usually does not hold the top position in the dominance hierarchy of her colony. In R. marginata, more workers are involved in dominance-subordinate interactions as compared to R. cyathiformis. These differences are reflected in the distribution of dominance-subordinate interactions among the hierarchically ranked individuals in both the species. The percentage of dominance interactions decreases gradually with hierarchical ranks in R. marginata while in R. cyathiformis it first increases and then decreases. We use an agent-based model to investigate the underlying mechanism that could give rise to the observed patterns for both the species. The model assumes, besides some non-interacting individuals, the interaction probabilities of the agents depend on their pre-differentiated winning abilities. Our simulations show that if the queen takes up a strategy of being involved in a moderate number of dominance interactions, one could get the pattern similar to R. cyathiformis, while taking up the strategy of very low interactions by the queen could lead to the pattern of R. marginata. We infer that both the species follow a common interaction pattern, while the differences in their social organization are due to the slight changes in queen as well as worker strategies. These changes in strategies are expected to accompany the evolution of more complex societies from simpler ones.

Ovarian development in a primitively eusocial wasp: Social interactions affect behaviorally dominant and subordinate wasps in opposite directions relative to solitary females

In many primitively eusocial wasp species new nests are founded either by a single female or by a small group of females. In the single foundress nests, the lone female develops her ovaries, lays eggs as well as tends her brood. In multiple foundress nests social interactions, especially dominance-subordinate interactions, result in only one `dominant' female developing her ovaries and laying eggs. Ovaries of the remaining `subordinate' cofoundresses remain suppressed and these individuals function as workers and tend the dominant's brood. Using the tropical, primitively eusocial polistine wasp Ropalidia marginata and by comparing wasps held in isolation and those kept as pairs in the laboratory, we demonstrate that social interactions affect ovarian development of dominant and subordinate wasps among the pairs in opposite directions, suppressing the ovaries of the subordinate member of the pair below that of solitary wasps and boosting the ovaries of dominant member of the pair above that of solitary females. In addition to being of physiological interest, such mirror image effects of aggression on the ovaries of the aggressors and their victims, suggest yet another mechanism by which subordinates can enhance their indirect fitness and facilitate the evolution of worker behavior by kin selection. (C) 2014 Elsevier B.V. All rights reserved.

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.