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.

An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction-Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity. Note to Practitioners-The advertiser-supported web site is one of the successful business models in the emerging web landscape. When an Internet user enters a keyword (i.e., a search phrase) into a search engine, the user gets back a page with results, containing the links most relevant to the query and also sponsored links, (also called paid advertisement links). When a sponsored link is clicked, the user is directed to the corresponding advertiser's web page. The advertiser pays the search engine in some appropriate manner for sending the user to its web page. Against every search performed by any user on any keyword, the search engine faces the problem of matching a set of advertisers to the sponsored slots. In addition, the search engine also needs to decide on a price to be charged to each advertiser. Due to increasing demands for Internet advertising space, most search engines currently use auction mechanisms for this purpose. These are called sponsored search auctions. A significant percentage of the revenue of Internet giants such as Google, Yahoo!, MSN, etc., comes from sponsored search auctions. In this paper, we study two auction mechanisms, GSP and VCG, which are quite popular in the sponsored auction context, and pursue the objective of designing a mechanism that is superior to these two mechanisms. In particular, we propose a new mechanism which we call the OPT mechanism. This mechanism maximizes the search engine's expected revenue subject to achieving Bayesian incentive compatibility and individual rationality. Bayesian incentive compatibility guarantees that it is optimal for each advertiser to bid his/her true value provided that all other agents also bid their respective true values. Individual rationality ensures that the agents participate voluntarily in the auction since they are assured of gaining a non-negative payoff by doing so.

Cascade PSI-BLAST web server: a remote homology search tool for relating protein domains

Owing to high evolutionary divergence, it is not always possible to identify distantly related protein domains by sequence search techniques. Intermediate sequences possess sequence features of more than one protein and facilitate detection of remotely related proteins. We have demonstrated recently the employment of Cascade PSI-BLAST where we perform PSI-BLAST for many 'generations', initiating searches from new homologues as well. Such a rigorous propagation through generations of PSI-BLAST employs effectively the role of intermediates in detecting distant similarities between proteins. This approach has been tested on a large number of folds and its performance in detecting superfamily level relationships is similar to 35% better than simple PSI-BLAST searches. We present a web server for this search method that permits users to perform Cascade PSI-BLAST searches against the Pfam, SCOP and SwissProt databases. The URL for this server is http://crick.mbu.iisc.ernet.in/similar to CASCADE/CascadeBlast.html.

Bidding Dynamics of Rational Advertisers in Sponsored Search Auctions on the Web

In this paper, we address a key problem faced by advertisers in sponsored search auctions on the web: how much to bid, given the bids of the other advertisers, so as to maximize individual payoffs? Assuming the generalized second price auction as the auction mechanism, we formulate this problem in the framework of an infinite horizon alternative-move game of advertiser bidding behavior. For a sponsored search auction involving two advertisers, we characterize all the pure strategy and mixed strategy Nash equilibria. We also prove that the bid prices will lead to a Nash equilibrium, if the advertisers follow a myopic best response bidding strategy. Following this, we investigate the bidding behavior of the advertisers if they use Q-learning. We discover empirically an interesting trend that the Q-values converge even if both the advertisers learn simultaneously.

Swelling behaviour of soil-bentonite mixtures

Studies on the swelling behaviour of mixtures of bentonite clay and nonswelling coarser fractions of different sizes and shapes reveal that observed swelling occurs only after the voids of the nonswelling particles are filled up with swollen clay particles. The magnitude of the swell within the voids, called intervoid swelling is large when the size and percentage of the nonswelling coarser fraction is large. The observable swell, after intervoid swelling, is called primary swelling and follows a rectangular hyperbolic relationship with time. The total swell per gram of the clay decreases with an increase in the size of the nonswelling fraction and with a decrease in the percentage of swelling clay. Time-swell relationships show that swelling continues to occur for a long time after the primary swelling, and this is called secondary swelling.

High temperature time-dependent low cycle fatigue behaviour of a type 316L(N) stainless steel

Total strain controlled low cycle fatigue tests on 316L(N) stainless steel have been conducted in air at various strain rates in the temperature range of 773-873 K to identify the operative time-dependent mechanisms and to understand their influence on the cyclic deformation and fracture behaviour of the alloy. The cyclic stress response at all the testing conditions was marked by an initial hardening followed by stress saturation. A negative strain rate stress response is observed under specific testing conditions which is attributed to dynamic strain ageing (DSA). Transmission electron microscopy studies reveal that there is an increase in the dislocation density and enhanced slip planarity in the DSA regime. Fatigue life is found to decrease with a decrease in strain rate. The degradation in fatigue resistance is attributed to the detrimental effects associated with DSA and oxidation. Quantitative measurement of secondary cracks indicate that both transgranular and intergranular cracking are accelerated predominantly under conditions conducive to DSA.

Pressure transitions and electron transport behaviour of crystalline Se-Te alloys

Pressure transitions of Se-Te alloys have been studied over the entire range of compositions. Conductivities have also been measured as a function of temperature and alloy composition. Transition pressures, activation barriers and isothermal conductivities exhibit distinct changes of slope in their variation as a function of composition at about 8 at % of Te. Transition pressures change slope at not, vert, similar 35% Te also. An attempt has been made to explain these observations on the basis of the size effect of Te which, in turn, affects the electron energy dispersions in the band structure.

Numerical simulation of conductive particle behaviour at the surface of a plate electrode affected by a DC corona field

The electric field in certain electrostatic devices can be modeled by a grounded plate electrode affected by a corona discharge generated by a series of parallel wires connected to a DC high-voltage supply. The system of differential equations that describe the behaviour (i.e., charging and motion) of the conductive particle in such an electric field has been numerically solved, using several simplifying assumptions. Thus, it was possible to investigate the effect of various electrical and mechanical factors on the trajectories of conductive particles. This model has been employed to study the behaviour of coalparticles in fly-ash corona separators.

Macromechanical behaviour of composite laminates

An improved higher order transverse shear deformation theory is employed to arrive at modified constitutive relations which can be used in the flexural, buckling and vibration analysis of laminated plates and shells. The strain energy for such systems is then expressed in terms of the displacements and the rotations for ready reference and use. Numerical values of vibration frequencies are obtained using this formulation employing Ritz's method of analysis. The results are compared with those available in the literature to validate the analysis presented.

Weak rectifying behaviour of p-SnS/n-ITO heterojunctions

This work explores the electrical properties of p-SnS/n-ITO heterojunction at different temperatures. The p-type SnS film was deposited on n-type ITO substrate using the thermal evaporation technique and its junction properties were studied using two probe method. The as-grown p-n junction exhibited weak rectifying behaviour with a low Saturation current of the order of similar to 10(-6) A. While increasing temperature, the saturation current of the junction is increased and however, its series resistance decreased. At all temperatures the junction exhibited three types of transport mechanisms depending on applied bias-voltage. At lower voltages the junction showed nearly ideal diode characteristics. The junction behaviour with respect to bias-voltage and temperature is discussed with the help of existing theories and energy band diagram.

Behaviour of methylmethacrylate-acrylonitrile random copolymers in dilute solution

Studies on the dilute solution properties of methylmethacrylate-acrylonitrile random copolymers of three different compositions, 0.236, 0.5 and 0.74 mole fraction (m.f.) of acrylonitrile (AN) designated as MAa, MAb and MAc, respectively, have been made in good solvents and theta solvents. MAa has been studied in benzene (Bz) and ethylacetate (EAc). MAb in acetonitrile (MeCN), dimethyl sulphoxide (DMSO) and a binary solvent mixture of Bz and dimentyl formamide (DMF) in the volume ratio 6.5:1 designated as BM1 and MAc in MeCN, DMSO and Bz + DMF in the volume ratio 1.667:1 designated as BM2. The Mark-Houwink exponent ‘a’ reveals that Bz is a theta solvent for MAa at 20°C. For MAb and MAc, BM1 and BM2, respectively have ‘a’ values of 0.5 at all three temperatures studied (30°, 40° and 50°C). It is not clear whether they represent theta states or preferential adsorption plays a role complicating the behaviour in solution. The values of A2 are very low in MeCN considering that it is a very good solvent for the copolymer, ‘a’ values for MAb and MAc being 0.75 and 0.7, respectively.

Impression creep behaviour of magnesium alloy-based hybrid composites in the transverse direction

The creep behaviour of a creep-resistant AE42 magnesium alloy reinforced with Saffil short fibres and SiC particulates in various combinations has been investigated in the transverse direction, i.e., the plane containing random fibre orientation was perpendicular to the loading direction, in the temperature range of 175-300 degrees C at the stress levels ranging from 60 to 140 MPa using impression creep test technique. Normal creep behaviour, i.e., strain rate decreasing with strain and then reaching a steady state, is observed at 175 degrees C at all the stresses employed, and up to 80 MPa stress at 240 degrees C. A reverse creep behaviour, i.e., strain rate increasing with strain, then reaching a steady state and then decreasing, is observed above 80 MPa stress at 240 degrees C and at all the stress levels at 300 degrees C. This pattern remains the same for all the composites employed. The reverse creep behaviour is found to be associated with fibre breakage. The apparent stress exponent is found to be very high for all the composites. However, after taking the threshold stress into account, the true stress exponent is found to range between 4 and 7, which suggests viscous glide and dislocation climb being the dominant creep mechanisms. The apparent activation energy Q(C) was not calculated due to insufficient data at any stress level either for normal or reverse creep behaviour. The creep resistance of the hybrid composites is found to be comparable to that of the composite reinforced with 20% Saffil short fibres alone at all the temperatures and stress levels investigated. The creep rate of the composites in the transverse direction is found to be higher than the creep rate in the longitudinal direction reported in a previous paper.

Low cycle fatigue behaviour of a low interstitial Ni-base superalloy

The low cycle fatigue behaviour of precipitation strengthened nickel-base superalloy 720Li containing a low concentration of interstitial carbon and boron was studied at 25, 400 and 650 degrees C. Cyclic stress response at all temperatures was stable under fully reversed constant total strain amplitude (Delta epsilon/2) when Delta epsilon/2 <= 0.6%. At Delta epsilon/2 > 0.6%, cyclic hardening was followed by softening, until fracture at 25 and 650 degrees C. At 400 degrees C, however, cyclic stress plateaued after initial hardening. Dislocation-dislocation interactions and precipitate shearing were the micromechanisms responsible for the cyclic hardening and softening, respectively. The number of reversals to failure vs. plastic strain amplitude plot exhibits a bilinear Coffin-Manson relation. Transmission electron microscopy substructures revealed that planar slip was the major deformation mode under the conditions examined. However, differences in its distribution were observed to be the cause for the bilinearity in fatigue lives. The presence of fine deformation twins at low Delta epsilon/2 at 650 degrees C suggests the role of twinning in homogenization of cyclic deformation.

AILaNb2O7:A new series of layered perovskites exhibiting ion exchange and intercalation behaviour

A new series of layered perovskite oxides, AILaNb2O7 (A = Li, Na, K, Rb, Cs, NH4) constituting n = 2 members of the family A A′n−1BnO3n+1, has been prepared. Their structure consists of double perovskite slabs interleaved by A atoms. Hydrated HLaNb2O7 is formed by topotactic proton exchange of the A atoms in ALaNb2O7 (A = K, Rb, Cs). The hydrate readily loses water to give anhydrous HLaNb2O7 which is isostructural with RbLaNb2O7. HLaNb2O7 exhibits Bronsted acidity forming intercalation compounds with bases such as n-octylamine and pyridine.

BSDD-2.0: Biomolecules Segment Display Device - An updated web accessible computing resource

The existing internet computing resource, Biomolecules Segment Display Device (BSDD), has been updated with several additional useful features. An advanced option is provided to superpose the structural motifs obtained from a search on the Protein Data Bank (PDB) in order to see if the three-dimensional structures adopted by identical or similar sequence motifs are the same. Furthermore, the options to display structural aspects like inter- and intra-molecular interactions, ion-pairs, disulphide bonds, etc. have been provided.The updated resource is interfaced with an up-to-date copy of the public domain PDB as well as 25 and 90% non-redundant protein structures. Further, users can upload the three-dimensional atomic coordinates (PDB format) from the client machine. A free molecular graphics program, JMol, is interfaced with it to display the three-dimensional structures.