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.

A perspective of biological supramolecular electron transfer

Electron transfer is an essential activity in biological systems. The migrating electron originates from water-oxygen in photosynthesis and reverts to dioxygen in respiration. In this cycle two metal porphyrin complexes possessing circular conjugated system and macrocyclic pi-clouds, chlorophyll and hems, play a decisive role in mobilising electrons for travel over biological structures as extraneous electrons. Transport of electrons within proteins (as in cytochromes) and within DNA (during oxidative damage and repair) is known to occur. Initial evaluations did not favour formation of semiconducting pathways of delocalized electrons of the peptide bonds in proteins and of the bases in nucleic acids. Direct measurement of conductivity of bulk material and quantum chemical calculations of their polymeric structures also did not support electron transfer in both proteins and nucleic acids. New experimental approaches have revived interest in the process of charge transfer through DNA duplex. The fluorescence on photoexcitation of Ru-complex was found to be quenched by Rh-complex, when both were tethered to DNA and intercalated in the base stack. Similar experiments showed that damage to G-bases and repair of T-T dimers in DNA can occur by possible long range electron transfer through the base stack. The novelty of this phenomenon prompted the apt name, chemistry at a distance. Based on experiments with ruthenium modified proteins, intramolecular electron transfer in proteins is now proposed to use pathways that include C-C sigma-bonds and surprisingly hydrogen bonds which remained out of favour for a long time. In support of this, some experimental evidence is now available showing that hydrogen bond-bridges facilitate transfer of electrons between metal-porphyrin complexes. By molecular orbital calculations over 20 years ago. we found that "delocalization of an extraneous electron is pronounced when it enters low-lying virtual orbitals of the electronic structures of peptide units linked by hydrogen bonds". This review focuses on supramolecular electron transfer pathways that can emerge on interlinking by hydrogen bonds and metal coordination of some unnoticed structures with pi-clouds in proteins and nucleic acids, potentially useful in catalysis and energy missions.

Systems biology of tuberculosis

Systems biology seeks to study biological systems as a whole, by adopting an integrated approach to study and understand the function of biological systems, particularly, the response of such systems to various perturbations. In this article, we focus on the Indian efforts towards systems-level studies of Mycobacterium tuberculosis and its interaction with the host. Availability of a variety of genome-scale experimental data, providing first level `omics' descriptions of the pathogen, render it feasible to study it at a systems level. Various aspects of the pathogen, from metabolic pathways to protein-protein interaction networks have been modelled and simulated, while host-pathogen interactions have been studied experimentally using siRNA-based techniques. These studies have been useful in obtaining a global perspective of the pathogen and its interactions with the host in many ways. For example, significant insights have been gained about different aspects such as proteins essential for bacterial survival, proteins that are highly influential in the network, pathways that are highly connected, host factors responsible for maintaining the TB infection and key factors involved in autophagy and pathogenesis. A rational pipeline developed for drug target identification incorporating analyses of the interactome, reactome, genome, pocketome and the transcriptome is discussed. Finally, exploring host factors as drug targets and insights about the emergence of drug resistance are also discussed. (C) 2011 Elsevier Ltd. All rights reserved.

Optimal incentive timing strategies for product marketing on social networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.

Hydrogen energy future with formic acid: a renewable chemical hydrogen storage system

Formic acid, the simplest carboxylic acid, is found in nature or can be easily synthesized in the laboratory (major by-product of some second generation biorefinery processes); it is also an important chemical due to its myriad applications in pharmaceuticals and industry. In recent years, formic acid has been used as an important fuel either without reformation (in direct formic acid fuel cells, DFAFCs) or with reformation (as a potential chemical hydrogen storage material). Owing to the better efficiency of DFAFCs compared to several other PEMFCs and reversible hydrogen storage systems, formic acid could serve as one of the better fuels for portable devices, vehicles and other energy-related applications in the future. This perspective is focused on recent developments in the use of formic acid as a reversible source for hydrogen storage. Recent developments in this direction will likely give access to a variety of low-cost and highly efficient rechargeable hydrogen fuel cells within the next few years by the use of suitable homogeneous metal complex/heterogeneous metal nanoparticle-based catalysts under ambient reaction conditions. The production of formic acid from atmospheric CO2 (a greenhouse gas) will decrease the CO2 content and may be helpful in reducing global warming.