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.

Energy-Efficient Fault Tolerance in Chip Multiprocessors Using Critical Value Forwarding

Relentless CMOS scaling coupled with lower design tolerances is making ICs increasingly susceptible to wear-out related permanent faults and transient faults, necessitating on-chip fault tolerance in future chip microprocessors (CMPs). In this paper we introduce a new energy-efficient fault-tolerant CMP architecture known as Redundant Execution using Critical Value Forwarding (RECVF). RECVF is based on two observations: (i) forwarding critical instruction results from the leading to the trailing core enables the latter to execute faster, and (ii) this speedup can be exploited to reduce energy consumption by operating the trailing core at a lower voltage-frequency level. Our evaluation shows that RECVF consumes 37% less energy than conventional dual modular redundant (DMR) execution of a program. It consumes only 1.26 times the energy of a non-fault-tolerant baseline and has a performance overhead of just 1.2%.

Triaxial A-value versus swell or collapse for compacted soil - Discussion

A discussion of a technical note with the aforementioned title by Day and Marsh, published in this journal (Volume 121, Number 7, July 1995), is presented. Discussers Robinson and Allam assert that the authors' application of the pore-pressure parameter A to predict and quantify swell or collapse of compacted soils is hard to use because the authors visualize the collapse-swell phenomenon to occur in compacted soils broadly classified as sands and clays. The literature demonstrates that mineralogy has an important role in the volume change behavior of fine-grained soils. Robinson and Allam state that the A-value measurements may not completely predict the type of volume change anticipated in compacted soils on soaking without soil clay mineralogy details. Discussion is followed by closure from the authors.

Synthesis and vesicle formation from dimeric pseudoglyceryl lipids with (CH2)(m) spacers: pronounced m-value dependence of thermal properties, vesicle fusion, and cholesterol complexation

Eight new dimeric lipids, in which the two Me2N+ ion headgroups are separated by a variable number of polymethylene units [-(CH2)(m)-], have been synthesized. The electron micrograph (TEM) and dynamic light scattering (DLS) of their aqueous dispersions confirmed the formation of vesicular-type aggregates. The vesicle sizes and morphologies were found to depend strongly on the m value, the method, and thermal history of the vesicle preparation. Information on the thermotropic properties of the resulting vesicles was obtained from microcalorimetry and temperature-dependent fluorescence anisotropy measurements. Interestingly, the T-m values for these vesicles revealed a nonlinear dependence on spacer chain length (m value). These vesicles were able to entrap riboflavin. The rates of permeation of the OH- ion under an imposed transmembrane pH gradient were also found to depend significantly on the m value. X-Ray diffraction of the cast films of the lipid dispersions elucidated the nature and the thickness of these membrane organizations, and it was revealed that these lipids organize in three different ways depending on the m value. The EPR spin-probe method with the doxylstearic acids 5NS, 12NS, and 16NS, spin-labeled at various positions of stearic acid, was used to establish, the chain-flexibility gradient and homogeneity of these bilayer assemblies. The apparent fusogenic propensities of these bipolar tetraether lipids were investigated in the presence of Na2SO4 with fluorescence-resonance energy-transfer fusion assay. Small unilamellar vesicles formed from 1 and three representative biscationic lipids were also studied with fluorescence anisotropy and H-1 NMR spectroscopic techniques in the absence and the presence of varying amounts of cholesterol.

The Wiener-Hopf solution of a class of mixed boundary value problems arising in surface water wave phenomena

Two mixed boundary value problems associated with two-dimensional Laplace equation, arising in the study of scattering of surface waves in deep water (or interface waves in two superposed fluids) in the linearised set up, by discontinuities in the surface (or interface) boundary conditions, are handled for solution by the aid of the Weiner-Hopf technique applied to a slightly more general differential equation to be solved under general boundary conditions and passing on to the limit in a manner so as to finally give rise to the solutions of the original problems. The first problem involves one discontinuity while the second problem involves two discontinuities. The reflection coefficient is obtained in closed form for the first problem and approximately for the second. The behaviour of the reflection coefficient for both the problems involving deep water against the incident wave number is depicted in a number of figures. It is observed that while the reflection coefficient for the first problem steadily increases with the wave number, that for the second problem exhibits oscillatory behaviour and vanishes at some discrete values of the wave number. Thus, there exist incident wave numbers for which total transmission takes place for the second problem. (C) 1999 Elsevier Science B.V. All rights reserved.

Determining Top K Nodes in Social Networks using the Shapley Value

In this paper, we consider the problem of selecting, for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the social network. This problem is relevant in many settings such as analysis of co-authorship networks, diffusion of information, viral marketing, etc. However, in most situations, this problem turns out to be NP-hard. The existing approaches for solving this problem are based on approximation algorithms and assume that the objective function is sub-modular. In this paper, we propose a novel and intuitive algorithm based on the Shapley value, for efficiently computing an approximate solution to this problem. Our proposed algorithm does not use the sub-modularity of the underlying objective function and hence it is a general approach. We demonstrate the efficacy of the algorithm using a co-authorship data set from e-print arXiv (www.arxiv.org), having 8361 authors.

A Shapley Value Analysis to Coordinate the Formation of Procurement Networks

In this paper we address the problem of forming procurement networks for items with value adding stages that are linearly arranged. Formation of such procurement networks involves a bottom-up assembly of complex production, assembly, and exchange relationships through supplier selection and contracting decisions. Research in supply chain management has emphasized that such decisions need to take into account the fact that suppliers and buyers are intelligent and rational agents who act strategically. In this paper, we view the problem of procurement network formation (PNF) for multiple units of a single item as a cooperative game where agents cooperate to form a surplus maximizing procurement network and then share the surplus in a fair manner. We study the implications of using the Shapley value as a solution concept for forming such procurement networks. We also present a protocol, based on the extensive form game realization of the Shapley value, for forming these networks.

An experimental study on cracking evolution in concrete and cement mortar by the b-value analysis of acoustic emission technique

Notched three point bend (TPB) specimens made with plain concrete and cement mortar were tested under crack mouth opening displacement (CMOD) control at a rate of 0.0004 mm/s and simultaneously acoustic emissions (AE) released were recorded during the experiments. Amplitude distribution analysis of AE released during concrete was carried out to study the development of fracture process in concrete and mortar specimens. The slope of the log-linear frequency-amplitude distribution of AE is known as the AE based b-value. The AE based b-value was computed in terms of physical process of time varying applied load using cumulative frequency distribution (Gutenberg-Richter relationship) and discrete frequency distribution (Aki's method) of AE released during concrete fracture. AE characteristics of plain concrete and cement mortar were studied and discussed and it was observed that the AE based b-value analysis serves as a tool to identify the damage in concrete structural members. (C) 2012 Elsevier Ltd. All rights reserved.

Existence of Value in Stochastic Differential Games of Mixed Type

In this article, we address stochastic differential games of mixed type with both control and stopping times. Under standard assumptions, we show that the value of the game can be characterized as the unique viscosity solution of corresponding Hamilton-Jacobi-Isaacs (HJI) variational inequalities.

A QUADRATIC C degrees INTERIOR PENALTY METHOD FOR LINEAR FOURTH ORDER BOUNDARY VALUE PROBLEMS WITH BOUNDARY CONDITIONS OF THE CAHN-HILLIARD TYPE

We develop a quadratic C degrees interior penalty method for linear fourth order boundary value problems with essential and natural boundary conditions of the Cahn-Hilliard type. Both a priori and a posteriori error estimates are derived. The performance of the method is illustrated by numerical experiments.

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.