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.

AB-initio study of alpha-silyl and beta-silyl substituent effects on vinyl radicals

The geometries of alpha- and beta-silyl substituted vinyl radicals and of alpha,beta-disilylvinyl radical have been optimised with the STO-3G and the STO-3G* basis sets. The relative stabilities of various conformers have been determined at the UMP2/6-31G* level. The stabilisation of vinyl radicals through alpha-silyl substitution is larger than that due to corresponding alkyl groups. The presence of an alpha-silyl group also leads to a tendency towards linearisation of the vinyl radical centre and a corresponding reduction in the inversion barrier. In marked contrast, the beta-silyl effect is negligible. The geometric, conformational and energetic consequences are insignificant. Overall, the silyl substituent effect at vinyl radicals is very different from that computed earlier for the vinyl cations, but qualitatively similar to that found in carbanions.

Construction of energy-level diagram of oriented benzene using connectivity information obtained by modified z-cosy experiment

Experiments involving selective perturbation of a transition yield information about the directly connected transitions, which in turn yield information for deriving the parameters of the spin Hamiltonian of oriented molecules. Problems involved with selective perturbation are removed by the use of a two-dimensional experiment, namely, the modified Z-COSY-experiment, The use of this experiment is demonstrated for obtaining the connectivity information and for determining the parameters of the spin Hamiltonian of oriented benzene, a strongly coupled six-spin system

A Sub-Nyquist Sampling Method For Computing The Level-crossing-times Of An Analog Signal: Theory And Applications

We address the problem of computing the level-crossings of an analog signal from samples measured on a uniform grid. Such a problem is important, for example, in multilevel analog-to-digital (A/D) converters. The first operation in such sampling modalities is a comparator, which gives rise to a bilevel waveform. Since bilevel signals are not bandlimited, measuring the level-crossing times exactly becomes impractical within the conventional framework of Shannon sampling. In this paper, we propose a novel sub-Nyquist sampling technique for making measurements on a uniform grid and thereby for exactly computing the level-crossing times from those samples. The computational complexity of the technique is low and comprises simple arithmetic operations. We also present a finite-rate-of-innovation sampling perspective of the proposed approach and also show how exponential splines fit in naturally into the proposed sampling framework. We also discuss some concrete practical applications of the sampling technique.

High level stable expression of rat brain type IIA sodium channel ?-subunit in CHO cells

The neuronal sodium channels are responsible for the rising phase of action potential and are composed of three subunits, of which the alpha-subunit has been shown to be adequate for most of its functional properties. We have stably expressed the rat brain type IIA sodium channel alpha-subunit in CHO cell tine using a CMV promoter-based vector. The expression was confirmed by detecting a 6.5 kb RNA corresponding to sodium channel alpha-subunit using Northern hybridization. The cells stably expressing the alpha-subunit, yield isolated sodium currents of amplitudes greater than 4nA when studied in whole-cell configuration of the patch-clamp technique. The sodium currents are characterized by activation and inactivation properties similar to neuronal sodium channels, and are blocked by the voltage gated sodium channel blocker tetrodotoxin (TTX).

Intracellular free calcium level and its response to cAMP stimulation in developing Dictyostelium cells transformed with jellyfish apoaequorin CDNA

A new method is described for measuring intracellular free calcium concentrations, [(Ca2+)(i)], in the cells of Dictyostelium discoideum transformed with apoaequorin cDNA of the jellyfish, Aequorea victoria. Aequorin, a calcium-specific indicator, was regenerated in vivo from apoaequorin produced in the cells by incubation with coelenterazine. The results showed that [(Ca2+)(i)] in developing cells markedly increases at the aggregation stage and again at the culmination stage after a temporary drop at the migration stage. Except for the vegetative stage, the cells al all stages of development exhibit a sharp transient increase in [(Ca2+)(i)] upon stimulation with a cAMP (50 nM) pulse, high responses being observed at the migration and culmination stages. Separated prestalk cells of migrating slugs contain more than twice as much [(Ca2+)(i)] and show three times as large a response to cAMP stimulation as prespore cells.

Five-level inverter scheme for an open-end winding induction machine with less number of switches

Higher level of inversion is achieved with a less number of switches in the proposed scheme. The scheme proposes a five-level inverter for an open-end winding induction motor which uses only two DC-link rectifiers of voltage rating of Vdc/4, a neutral-point clamped (NPC) three-level inverter and a two-level inverter. Even though the two-level inverter is connected to the high-voltage side, it is always in square-wave operation. Since the two-level inverter is not switching in a pulse width modulated fashion and the magnitude of switching transient is only half compared to the convention three-level NPC inverter, the switching losses and electromagnetic interference is not so high. The scheme is experimentally verified on a 2.5 kW induction machine.

Symmetry-breaking transition in a two-level system coupled to an Ohmic bath: A squeezed-state approach

Displaced squeezed states are proposed as variational ground states for phonons (Bose fields) coupled to two-level systems (spin systems). We have investigated the zero-temperature phase diagram for the localization-delocalization transition of a tunneling particle interacting with an Ohmic heat bath. Our results are compared with known existing approximate treatments. A modified phase diagram using the displaced squeezed state is presented.

The level of sequestered calcium in vegetative amoebae of Dictyostelium discoideum can predict post-aggregative cell fate

When freshly starved amoebae of Dictyostelium discoideum are stained with chlortetracycline (CTC), a cell type-specific fluorescent probe for membrane-associated calcium (Ca2+) the resulting fluorescence distribution falls into two functional classes. Fluorescence-activated cell sorting shows that highly fluorescing amoebae tend to enter the prestalk pathway while those with low fluorescence tend to become prespores. In the light of previous findings, these results indicate that in addition to cell cycle phase at starvation, phenotypic variation in the level of sequestered calcium is an early correlate of cell fate.

Levitation Effect: Role of Symmetry and Dependence of Diffusivity on the Bond Length of Homonuclear and Heteronuclear Diatomic Species

Molecular dynamics investigation of model diatomic species confined to the alpha-cages of zeolite NaY is reported. The dependence of self-diffusivity on the bond length of the diatomic species has been investigated. Three different sets of runs have been carried out. In the first set, the two atoms of the diatomic molecule interact with the zeolite atoms with equal strength (example, O-2, the symmetric case). In the second and third sets which correspond to asymmetric cases, the two atoms of the diatomic molecule interact with unequal strengths (example, CO). The result for the symmetric case exhibits a well-defined maximum in self-diffusivity for an intermediate bond length. In contrast to this, the intermediate asymmetry leads to a less pronounced maximum. For the large asymmetric case, the maximum is completely absent. These findings are analyzed by computing a number of related properties. These results provide a direct confirmation at the microscopic level of the suggestion by Derouane that the supermobility observed experimentally by Kemball has its origin in the mutual cancellation of forces. The maximum in diffusivity from molecular dynamics is seen at the value predicted by the levitation effect. Further, these findings suggest a role for symmetry in the existence of a diffusivity maximum as a function of diameter of the diffusant often referred to as the levitation effect. The nature of the required symmetry for the existence of anomalous diffusivity is interaction symmetry which is different from that normally encountered in crystallography.

Cell versus message level performances in ATM networks

The goal of this paper is to provide some insight into the relations that exist between cell level and message level performance guarantees in the context of ATM networks. Cell level guarantees are typically what the network is capable of providing, while message level guarantees are the ones of interest to users. It is, therefore, important to understand how the two are related, and which factors influence this relation. There are many different performance measures that are of importance, and in this paper we try to touch on the (three) most relevant ones. This includes comparing cell and message loss probabilities, average cell and message delays, and cell and message jitter. Specifically, we show that cell and message loss probabilities can exhibit significant differences, which strongly depend on traffic characteristics such as peak rate and burst size, i.e., for a fixed cell loss probability, the message loss probability can greatly vary when peak rate and burst size change. One reason for this sensitivity, is that message loss depends on what happen to all the cells in a message. For delay and jitter, we also find that peak rate and burst size play a role in determining the relation between cell and message performance. However, this sensitivity is not as acute as with losses since message delay and jitter are typically determined by the performance seen by only one cell, the last cell in a message. In the paper, we provide quantitative examples that illustrate the range of behaviors and identify the impact of different parameters.

Cu 2p core-level photoemission spectrum of Sr2CuO3

We measure the Cu 2p X-ray photoemission spectrum (XPS) of Sr2CuO3 and analyze it by means of exact diagonalization calculations for (CunO3n)(4n-) clusters. In Sr2CuO3, the intensity ratio of the 3d(y) satellite to the 3d(10)(L) under bar main line is 0.35-0.4, which is evidently smaller than that in the other high-T-c related cuprates. We ascribe it as the smaller charge-transfer energy between the Cu 3d and O 2p. The origin of the broad main-line of Sr2CuO3 is also discussed.

Electronic structure of early 3d-transition-metal oxides by analysis of the 2p core-level photoemission spectra

The electronic structures of a wide range of early transition-metal (TM) compounds, including Ti and V oxides with metal valences ranging from 2+ to 5+ and formal d-electron numbers ranging from 0 to 2, have been investigated by a configuration-interaction cluster model analysis of the core-level metal 2p x-ray photoemission spectra (XPS). Inelastic energy-loss backgrounds calculated from experimentally measured electron-energy-loss spectra (EELS) were subtracted from the XPS spectra to remove extrinsic loss features. Parameter values deduced for the charge-transfer energy Delta and the d-d Coulomb repulsion energy U are shown to continue the systematic trends established previously for the late TM compounds, giving support to a charge-transfer mechanism for the satellite structures. The early TM compounds are characterized by a large metal d-ligand p hybridization energy, resulting in strong covalency in these compounds. Values for Delta and U suggest that many early TM compounds should be reclassified as intermediate between the charge-transfer regime and the Mott-Hubbard regime.

Baculovirus mediated high-level expression of luciferase in silkworm cells and larvae

Bombyx mori nuclear polyhedrosis virus (BmNPV)-based baculovirus expression system exploits silkworm larvae as an economical alternative to large-scale cell cultures for production of biomolecules. To generate recombinant BmNPV at high efficiency, we have achieved high efficiency transfection of B. mori cells, BmN, through lipofection. Optimal conditions for lipofection were standardized by quantification of the transient expression level of firefly luciferase (luc) reporter gene under control of an immediate early gene promoter of BmNPV Lipofection was 50-fold and 100-fold more efficient than the calcium phosphate method for transfecting BmN and Sf9 cells, respectively. Lipofection enabled us to generate a recombinant BmNPV (vBmluc), harboring luc under control of the strong polyhedrin promoter On infection with vBmluc, luciferase was expressed at very high levels, 170 mu g/10(6) BmN cells or 13 mg/larva. Expression of luciferase in vBmluc-infected larvae was visualized by luminescence emission instantaneously following luciferin injection generating ''glowing silkworms''.