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.

Achieving universal rural energy access in india: A low carbon pathway

India's energy challenges are three pronged: presence of majority energy poor lacking access to modern energy; need for expanding energy system to bridge this access gap as well as to meet the requirements of fast-growing economy; and the desire to partner with global economies in mitigating the threat of climate change. The presence of 364 million people without access to electricity and 726 million relying on biomass for cooking out of a total rural population of 809 million indicate the seriousness of challenge. In this paper, we discuss an innovative approach to address this challenge, which intends to take advantage of recent global developments and untapped capabilities possessed by India. Intention is to use climate change mitigation imperative as a stimulus and adopt a public-private-partnership-driven ‘business model' with innovative institutional, regulatory, financing, and delivery mechanisms. Some of the innovations are: creation of rural energy access authorities within the government system as leadership institutions; establishment of energy access funds to enable transitions from the regime of "investment/fuel subsidies" to "incentive-linked" delivery of energy services; integration of business principles to facilitate affordable and equitable energy sales and carbon trade; and treatment of entrepreneurs as implementation targets. This proposal targets 100% access to modern energy carriers by 2030 through a judicious mix of conventional and biomass energy systems with an investment of US$35 billion over 20 years. The estimated annual cost of universal energy access is about US$9 billion for a GHG mitigation potential of 213Tg CO2e at an abatement cost of US$41/tCO2e. It is a win-win situation for all stakeholders. Households benefit from modern energy carriers at affordable cost; entrepreneurs run profitable energy enterprises; carbon markets have access to CERs; the government has the satisfaction of securing energy access to rural people; and globally, there is a benefit of climate change mitigation.

Innovation and growth of engineering SMEs in Bangalore: Why do only some innovate and only some grow faster?

This paper probes two research questions by ascertaining the factors which distinguish (i) innovative SMEs from those which are not, and (ii) SMEs which experienced a higher sales growth from those which experienced a lower sales growth, with reference to 197 engineering industry SMEs in Bangalore city. The differentiating factors between innovative and non-innovative SMEs brought out that SMEs must have ``own resources and capabilities'' in the form of internal strength and definite internal strategy if they have to innovate successfully. Younger and smaller firms which are ``entrepreneurial'' in nature and which are innovative contributed to higher sales growth of SMEs compared to older and larger firms which are ``salary-substitute firms'' in nature and which are not innovative. (C) 2015 Elsevier B.V. All rights reserved.

Susceptibility Of strength development by lime in gypsiferous soil-A micro mechanistic study

The role of gypsum on the strength of lime treated soils after a long period of interaction is not well understood yet. The present study is performed to scrutinize the physical and strength behavior of lime treated soil with varying gypsum content. Lime and gypsum contents varying from 0 to 6% are considered in the present study for curing periods up to 28 days. To understand the long-term effects, the work has been extended up to 365 days, particularly with the use of 6% lime content and varying gypsum contents. Atterberg's limits turned out to be marginally affected by cation exchange. Unconfined compressive strength behavior of lime treated soil varies considerably with gypsum content and curing period. However, trivial alteration in strength is observed in the soil treated with lower lime content (up to 4%) and gypsum content up to 6%. On the contrary, strength of soil-6% lime mixture with addition of varying gypsum content shows acceleration in early strength at 14 days curing period. However, the strength at 28 days of curing declines but regains afterwards for 90 days. The trend at longer curing period for 180 and 365 days is, however, not unique but varies with gypsum contents. An attempt has been made to explain these changes on the basis of the form of gypsum, formation and conversion of reacted compounds (CASHH, CASH, MI and Ettringite). The proposed explanations were supported by detailed characterization through thermal analysis, XRD, SEM and EDAX studies of soil-lime-gypsum mixtures. (C) 2015 Elsevier B.V. All rights reserved.

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.