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.

NUcache: A Multicore Cache Organization Based on Next-Use Distance

In this work, we propose a new organization for the last level shared cache of a rnulticore system. Our design is based on the observation that the Next-Use distance, measured in terms of intervening misses between the eviction of a line and its next use, for lines brought in by a given delinquent PC falls within a predictable range of values. We exploit this correlation to improve the performance of shared caches in multi-core architectures by proposing the NUcache organization.

Kinetic evolution studies of silver nanoparticles in a bio-based green synthesis process

Silver nanoparticles are being extensively studied due to their widespread applications and unique properties. In the present study, the growth kinetics of silver nanoparticles as synthesized on reduction of silver nitrate solution by aqueous extract of Azadirachta indica leaves was investigated. The formation of silver nanoparticles was preliminarily monitored by measuring the absorption maxima at different time intervals after adding the reducing agent to the silver salt solution (0.5, 1, 1.5, 2, 2.5, 3, 3.5 and 4 h). At different time points characterization studies were conducted using X-ray diffraction studies, FT-IR techniques, zeta potential studies and transmission electron microscopy. The total available silver in the reaction medium was determined at different durations using ICP-OES. The changes in reduction potential in the medium were also monitored using potentiometric analysis. The results confirm a definite change in the medium pertaining to formation of the stable nanoparticles after 2 h, and a significant increase in the agglomeration tendency after 4 h of interaction. The growth kinetic data of the nanoparticles till 3.5 h was found to fit the LSW model confirming diffusion limited growth. (C) 2011 Elsevier B.V. All rights reserved.

Reduced Order Suboptimal Control Design for a Class of Nonlinear Distributed Parameter Systems Using POD and /spl thetas/-D Techniques

A new computational tool is presented in this paper for suboptimal control design of a class of nonlinear distributed parameter systems. First proper orthogonal decomposition based problem-oriented basis functions are designed, which are then used in a Galerkin projection to come up with a low-order lumped parameter approximation. Next, a suboptimal controller is designed using the emerging /spl thetas/-D technique for lumped parameter systems. This time domain sub-optimal control solution is then mapped back to the distributed domain using the same basis functions, which essentially leads to a closed form solution for the controller in a state feedback form. Numerical results for a real-life nonlinear temperature control problem indicate that the proposed method holds promise as a good suboptimal control design technique for distributed parameter systems.

Synthesis and Antioxidant Activity of Peptide-Based Ebselen Analogues

A series of di- and tripeptide-based ebselen analogues has been synthesized. The compounds were characterized by H-1, C-13, and Se-77 NMR spectroscopy and mass spectral techniques. The glutathione peroxidase (GPx)-like antioxidant activity has been studied by using H2O2, tert-butyl hydroperoxide (tBuOOH), and cumene hydroperoxide (Cum-OOH) as substrates, and glutathione (GSH) as a co-substrate. Although all the peptide-based compounds have a selenazole ring similar to that of ebselen, the GPx activity of these compounds highly depends on the nature of the peptide moiety attached to the nitrogen atom of the selenazole ring. It was observed that the introduction of a phenylalanine (Phe) amino acid residue in the N-terminal reduces the activity in all three peroxide systems. On the other hand, the introduction of aliphatic amino acid residues such as valine (Val) significantly enhances the GPx activity of the ebselen analogues. The difference in the catalytic activity of dipeptide-based ebselen derivatives can be ascribed mainly to the change in the reactivity of these compounds toward GSH and peroxide. Although the presence of the Val-Ala-CO2Me moiety facilitates the formation of a catalytically active selenol species, the reaction of ebselen analogues that has a Phe-Ile-CO2Me residue with GSH does not generate the corresponding selenol. To understand the antioxidant activity of the peptide-based ebselen analogues in the absence of GSH, these compounds were studied for their ability to inhibit peroxynitrite (PN)-mediated nitration of bovine serum albumin (BSA) and oxidation of dihydrorhodamine 123. In contrast to the GPx activity, the PN-scavenging activity of the Phe-based peptide analogues was found to be comparable to that of the Val-based compounds. However, the introduction of an additional Phe residue to the ebselen analogue that had a Val-Ala dipeptide significantly reduced the potency of the parent compound in PN-mediated nitration.

Study of Carbon Nanocapsules (Onions) and Spherulitic Graphite by Stm and Other Techniques

A scanning tunneling microscopy study of carbon nanocapsules (onions) is reported for the first time. Spherulitic graphite is shown to be purely crystalline graphite based on X-ray diffraction and electron microscopy studies.

Petri net-based modeling of a class of complex digital systems

We present through the use of Petri Nets, modeling techniques for digital systems realizable using FPGAs. These Petri Net models are used for logic validation at the logic design phase. The technique is illustrated by modeling practical circuits. Further, the utility of the technique with respect to timing analysis of the modeled digital systems is considered. Copyright (C) 1997 Elsevier Science Ltd

Signal compression through spatial frequency-based motion estimation

The interest in low bit rate video coding has increased considerably. Despite rapid progress in storage density and digital communication system performance, demand for data-transmission bandwidth and storage capacity continue to exceed the capabilities of available technologies. The growth of data-intensive digital audio, video applications and the increased use of bandwidth-limited media such as video conferencing and full motion video have not only sustained the need for efficient ways to encode analog signals, but made signal compression central to digital communication and data-storage technology. In this paper we explore techniques for compression of image sequences in a manner that optimizes the results for the human receiver. We propose a new motion estimator using two novel block match algorithms which are based on human perception. Simulations with image sequences have shown an improved bit rate while maintaining ''image quality'' when compared to conventional motion estimation techniques using the MAD block match criteria.

Classification of microwatersheds based on morphological characteristics

Three classification techniques, namely, K-means Cluster Analysis (KCA), Fuzzy Cluster Analysis (FCA), and Kohonen Neural Networks (KNN) were employed to group 25 microwatersheds of Kherthal watershed, Rajasthan into homogeneous groups for formulating the basis for suitable conservation and management practices. Ten parameters, mainly, morphological, namely, drainage density (D-d), bifurcation ratio (R-b), stream frequency (F-u), length of overland flow (L-o), form factor (R-f), shape factor (B-s), elongation ratio (R-e), circulatory ratio (R-c), compactness coefficient (C-c) and texture ratio (T) are used for the classification. Optimal number of groups is chosen, based on two cluster validation indices Davies-Bouldin and Dunn's. Comparative analysis of various clustering techniques revealed that 13 microwatersheds out of 25 are commonly suggested by KCA, FCA and KNN i.e., 52%; 17 microwatersheds out of 25 i.e., 68% are commonly suggested by KCA and FCA whereas these are 16 out of 25 in FCA and KNN (64%) and 15 out of 25 in KNN and CA (60%). It is observed from KNN sensitivity analysis that effect of various number of epochs (1000, 3000, 5000) and learning rates (0.01, 0.1-0.9) on total squared error values is significant even though no fixed trend is observed. Sensitivity analysis studies revealed that microwatershecls have occupied all the groups even though their number in each group is different in case of further increase in the number of groups from 5 to 6, 7 and 8. (C) 2010 International Association of Hydro-environment Engineering and Research, Asia Pacific Division. Published by Elsevier B.V. All rights reserved.

Enhanced lithium-ion transport in PEG-based composite polymer electrolyte with Mn0.03Zn0.97Al2O4 nanoparticles

The ion conduction and thermal properties of composite solid polymer electrolyte (SPE) comprising Poly(ethylene) Glycol (PEG, mol wt. 2000), lithium perchlorate (LiClO4) and insulating Mn0.03Zn0.97Al2O4 nanoparticle fillers were studied by complex impedance analysis and DSC techniques. The average size of the nanoparticles was determined by powder X-ray diffraction (XRD) using Scherrer's equation and was found to be similar to 8 nm. The same was also determined by TEM imaging and found to be similar to 12 nm. The glass transition temperature T, as measured by differential scanning calorimeter (DSC), showed a minimum at 5 mol% of narroparticles. Fractional crystallinity was determined using DSC. NMR was used to deter-mine crystallinity of a pure PEG sample, which was then used as the standard. Fractional crystallinity X. was the lowest for 5 mol% and beyond. The ionic conductivity of the composite polymer electrolyte containing 5 mol% Mn0.03Zn0.97Al2O4 nanoparticles was found to be 1.82 x 10(-5) S/cm, while for the pristine one, it was 7.27 x 10(-7) S/cm at room temperature. As a function of nanoparticle content, conductivity was observed to go through two maxima, one at around 5 mol% and another shallower one at around 12 mol%. The temperature dependence of conductivity could be divided into two regions, one consistent with Arrhenius behaviour and the other with VTF. We conclude that the enhancement of ionic conductivity on the addition of Mn0.03Zn0.97Al2O4 nanoparticles is a result of reduction in both the T, and the crystallinity. (C) 2002 Elsevier Science B.V. All rights reserved.

Renewable surface electrodes based on dopamine functionalized exfoliated graphite: NADH oxidation and ethanol biosensing

Exfoliated graphite (EG) was modified by covalently attaching dopamine (DA) (3,4-dihydroxyphenethylamine) through amide linkages, using -COOH groups introduced on the EG surface. The modified material was characterized by FT-IR spectroscopy, Xray photoelectron spectroscopy and electrochemical techniques. Composites of DA modified EG dispersed in organically modified silicates were prepared by a sol-get process. Electrodes were fabricated by casting the composites in glass tubes. The sol-gel based electrodes were found to be active for the electrocatalytic oxidation of NADH and biosensing of ethanol in presence of NAD(+) and alcohol dehydrogenase enzyme. The modified composite electrodes were found to be stable for several months. The surface of the electrode could be renewed just by mechanically polishing the electrode using emery sheets. The modified EG was also pressed and restacked in the form of a pellet and the use of this material as a binderless bulk-modified electrode was also demonstrated. The performance of sol-gel derived composite EG electrodes with binderless bulk-modified EG electrodes was compared. (C) 2002 Elsevier Science B.V. All rights reserved.

Sol-gel derived, magnesium based ionically conducting composites

Composite ionic conductors based on magnesium salts and sol-gel derived silicate-tetraethylene glycol hybrids have been synthesized. The structure of these materials has been studied by FT-IR, FT-Raman, Si-29 and C-13 NMR and XRD techniques. The composite systems can be best described as diphasic with silicate as filters in the organic phase that provides solubility of the ionic dispersants. The ionic interactions in the matrix are clearly observed in the FT-Raman spectra. The ionic conductivity is determined to be of the order of 10(-7) to 10(-5) S cm(-1) at room temperature for MgCl2 and Mg(ClO4)(2) salts respectively. The conductivity reaches 10(-4) and 10(-3) S cm(-1) at 80degreesC respectively.

Strip based coding for large images using wavelets

Thanks to advances in sensor technology, today we have many applications (space-borne imaging, medical imaging, etc.) where images of large sizes are generated. Straightforward application of wavelet techniques for above images involves certain difficulties. Embedded coders such as EZW and SPIHT require that the wavelet transform of the full image be buffered for coding. Since the transform coefficients also require storing in high precision, buffering requirements for large images become prohibitively high. In this paper, we first devise a technique for embedded coding of large images using zero trees with reduced memory requirements. A 'strip buffer' capable of holding few lines of wavelet coefficients from all the subbands belonging to the same spatial location is employed. A pipeline architecure for a line implementation of above technique is then proposed. Further, an efficient algorithm to extract an encoded bitstream corresponding to a region of interest in the image has also been developed. Finally, the paper describes a strip based non-embedded coding which uses a single pass algorithm. This is to handle high-input data rates. (C) 2002 Elsevier Science B.V. All rights reserved.

Techniques for realistic visualization of fluids: A survey

Visualization of fluids has wide applications in science, engineering and entertainment. Various methodologies Of visualizing fluids have evolved which emphasize on capturing different aspects of the fluids accurately. In this survey the existing methods for realistic visualization of fluids are reviewed. The approaches are classified based on the key concept they rely on for fluid modeling. This classification allows for easy selection of the method to be adopted for visualization given an application. It also enables identification of alternative techniques for fluid modeling.

Online character recognition using regression techniques

This paper introduces a scheme for classification of online handwritten characters based on polynomial regression of the sampled points of the sub-strokes in a character. The segmentation is done based on the velocity profile of the written character and this requires a smoothening of the velocity profile. We propose a novel scheme for smoothening the velocity profile curve and identification of the critical points to segment the character. We also porpose another method for segmentation based on the human eye perception. We then extract two sets of features for recognition of handwritten characters. Each sub-stroke is a simple curve, a part of the character, and is represented by the distance measure of each point from the first point. This forms the first set of feature vector for each character. The second feature vector are the coeficients obtained from the B-splines fitted to the control knots obtained from the segmentation algorithm. The feature vector is fed to the SVM classifier and it indicates an efficiency of 68% using the polynomial regression technique and 74% using the spline fitting method.