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.

Joint decoding of multiple speech patterns for robust speech recognition

We are addressing a new problem of improving automatic speech recognition performance, given multiple utterances of patterns from the same class. We have formulated the problem of jointly decoding K multiple patterns given a single Hidden Markov Model. It is shown that such a solution is possible by aligning the K patterns using the proposed Multi Pattern Dynamic Time Warping algorithm followed by the Constrained Multi Pattern Viterbi Algorithm The new formulation is tested in the context of speaker independent isolated word recognition for both clean and noisy patterns. When 10 percent of speech is affected by a burst noise at -5 dB Signal to Noise Ratio (local), it is shown that joint decoding using only two noisy patterns reduces the noisy speech recognition error rate to about 51 percent, when compared to the single pattern decoding using the Viterbi Algorithm. In contrast a simple maximization of individual pattern likelihoods, provides only about 7 percent reduction in error rate.

Multi Pattern Dynamic Time Warping For Automatic Speech Recognition

We are addressing the problem of jointly using multiple noisy speech patterns for automatic speech recognition (ASR), given that they come from the same class. If the user utters a word K times, the ASR system should try to use the information content in all the K patterns of the word simultaneously and improve its speech recognition accuracy compared to that of the single pattern based speech recognition. T address this problem, recently we proposed a Multi Pattern Dynamic Time Warping (MPDTW) algorithm to align the K patterns by finding the least distortion path between them. A Constrained Multi Pattern Viterbi algorithm was used on this aligned path for isolated word recognition (IWR). In this paper, we explore the possibility of using only the MPDTW algorithm for IWR. We also study the properties of the MPDTW algorithm. We show that using only 2 noisy test patterns (10 percent burst noise at -5 dB SNR) reduces the noisy speech recognition error rate by 37.66 percent when compared to the single pattern recognition using the Dynamic Time Warping algorithm.

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.

Mobile Base Stations Placement and Energy Aware Routing in Wireless Sensor Networks

Increasing network lifetime is important in wireless sensor/ad-hoc networks. In this paper, we are concerned with algorithms to increase network lifetime and amount of data delivered during the lifetime by deploying multiple mobile base stations in the sensor network field. Specifically, we allow multiple mobile base stations to be deployed along the periphery of the sensor network field and develop algorithms to dynamically choose the locations of these base stations so as to improve network lifetime. We propose energy efficient low-complexity algorithms to determine the locations of the base stations; they include i) Top-K-max algorithm, ii) maximizing the minimum residual energy (Max-Min-RE) algorithm, and iii) minimizing the residual energy difference (MinDiff-RE) algorithm. We show that the proposed base stations placement algorithms provide increased network lifetimes and amount of data delivered during the network lifetime compared to single base station scenario as well as multiple static base stations scenario, and close to those obtained by solving an integer linear program (ILP) to determine the locations of the mobile base stations. We also investigate the lifetime gain when an energy aware routing protocol is employed along with multiple base stations.

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.

On the variety of electron diffraction patterns from quasicrystals

A new exciting era in the study of rapidly solidified alloys has been ushered in by the discovery of a quasicrystalline phase in an Al-1O%Mn alloy by Shechtman et al. (l). The fact that a quasicrystal diffracts electrons and X-rays like a single crystal provides a powerful approach for exploring the atomic configuration in these alloys. Shechtman et al deduced the icosahedral point group symmetry exhibited by quasicrystals on the basis of a set of three electron diffraction patterns showing 5-fold, 3-fold and 2-fold axes of symmetry with appropriate angular relationships. The exotic crystallography of quasicrystals has been recently reviewed by Nelson and Halperin (2).

Metal-Nucleotide Interactions: Crystal Structures of Alkali (Li+, Na+, K+) and Alkaline Earth (Ca2+, Mg2+) Metal Complexes of Adenosine 2'-Monophosphate

Crystal structures of lithium, sodium, potassium, calcium and magnesium salts of adenosine 2'-monophosphate (2'-AMP) have been obtained at atomic resolution by X-ray crystallographic methods. 2'-AMP.Li belongs to the monoclinic space group P21 with a = 7.472(3)Å, b = 26.853(6) Å, c = 9.184(1)Å, b = 113.36(1)Å and Z= 4. 2'-AMP.Na and 2'-AMP.K crystallize in the trigonal space groups P31 and P3121 with a = 8.762(1)Å, c = 34.630(5)Å, Z= 6 and a = 8.931(4), Åc = 34.852(9)Å and Z= 6 respectively while 2'-AMP.Ca and 2'-AMP.Mg belong to space groups P6522 and P21 with cell parameters a = 9.487(2), c = 74.622(13), Z = 12 and a = 4.973(1), b = 10.023(2), c = 16.506(2), beta = 91.1(0) and Z = 2 respectively. All the structures were solved by direct methods and refined by full matrix least-squares to final R factors of 0.033, 0.028, 0.075, 0.069 and 0.030 for 2'-AMP.Li, 2'-AMP.Na, 2'- AMP.K, 2'-AMP.Ca and 2'-AMP.Mg, respectively. The neutral adenine bases in all the structures are in syn conformation stabilized by the O5'-N3 intramolecular hydrogen bond as in free acid and ammonium complex reported earlier. In striking contrast, the adenine base is in the anti geometry (cCN = -156.4(2)°) in 2'-AMP.Mg. Ribose moieties adopt C2'-endo puckering in 2'-AMP.Li and 2'-AMP.Ca, C2'-endo-C3'-exo twist puckering in 2'-AMP.Na and 2'-AMP.K and a C3'-endo-C2'-exo twist puckering in 2'-AMP.Mg structure. The conformation about the exocyclic C4'-C5' bond is the commonly observed gauche-gauche (g+) in all the structures except the gauche- trans (g-) conformation observed in 2'-AMP.Mg structure. Lithium ions coordinate with water, ribose and phosphate oxygens at distances 1.88 to 1.99Å. Na+ ions and K+ ions interact with phosphate and ribose oxygens directly and with N7 indirectly through a water oxygen. A distinct feature of 2'-AMP.Na and 2'-AMP.K structures is the involvement of ribose O4' in metal coordination. The calcium ion situated on a two-fold axis coordinates directly with three oxygens OW1, OW2 and O2 and their symmetry mates at distances 2.18 to 2.42Å forming an octahedron. A classic example of an exception to the existence of the O5'-N3 intramolecular hydorgen bond is the 2'-AMP.Mg strucure. Magnesium ion forms an octahedral coordination with three water and three phosphate oxygens at distances ranging from 2.02 to 2.11Å. A noteworthy feature of its coordination is the indirect link with N3 through OW3 oxygen resulting in macrochelation between the base and the phosphate group. Greater affnity of metal clays towards 5' compared to 2' and 3' nucleotides (J. Lawless, E. Edelson, and L. Manring, Am. Chem. Soc. Northwest Region Meeting, Seattle. 1978) due to macrochelation infered from solution studies (S. S. Massoud, H. Sigel, Eur. J. Biochem. 179, 451-458 (1989)) and interligand hydrogen bonding induced by metals postulated from metal-nucleotide structures in solid state (V. Swaminathan and M. Sundaralingam, CRC. Crit. Rev. Biochem. 6, 245-336 (1979)) are borne out by our structures also. The stacking patterns of adenine bases of both 2'-AMP.Na and 2'-AMP.K structures resemble the 2'-AMP.NH4 structure reported in the previous article. 2'-AMP.Li, 2'-AMP.Ca and 2'-AMP.Mg structures display base-ribose O4' stacking. An overview of interaction of monovalent and divalent cations with 2' and 5'-nucleotides has been presented.

Electron diffraction patterns from the Al-Mn decagonal phase

The variety of electron diffraction patterns arising from the decagonal phase has been explored using a stereographic analysis for generating the important zone axes as intersection points corresponding to important relvectors. An indexing scheme employing a set of five vectors and an orthogonal vector has been followed. A systematic tilting from the decagonal axis to one of the twofold axes has been adopted to generate a set of experimental diffraction patterns corresponding to the expected patterns from the stereographic analysis with excellent agreement.

Probing top-gated field effect transistor of reduced graphene oxide monolayer made by dielectrophoresis

We demonstrate a top-gated field effect transistor made of a reduced graphene oxide (RGO) monolayer (graphene) by dielectrophoresis. The Raman spectrum of RGO flakes of typical size of 5 mu m x 5 mu m shows a single 2D band at 2687 cm(-1), characteristic of single-layer graphene.The two-probe current-voltage measurements of RGO flakes, deposited in between the patterned electrodes with a gap of 2.5 mu m using ac dielectrophoresis, show ohmic behavior with a resistance of similar to 37 k Omega. The temperature dependence of the resistance (R) of RGO measured between 305 K and 393 K yields a temperature coefficient of resistance [dR/dT]/R similar to -9.5 x 10(-4)/K, the same as that of mechanically exfoliated single-layer graphene. The field-effect transistor action was obtained by electrochemical top-gating using a solid polymer electrolyte (PEO + LiClO4) and Pt wire. The ambipolar nature of graphene flakes is observed up to a doping level of similar to 6 x 10(12)/cm(2) and carrier mobility of similar to 50 cm(2)/V s. The source-drain current characteristics show a tendency of current saturation at high source-drain voltage which is analyzed quantitatively by a diffusive transport model. (C) 2010 Elsevier Ltd. All rights reserved.

Top polarization as a probe of new physics

We investigate the effects of new physics scenarios containing a high mass vector resonance on top pair production at the LHC, using the polarization of the produced top. In particular we use kinematic distributions of the secondary lepton coming from top decay, which depends on top polarization, as it has been shown that the angular distribution of the decay lepton is insensitive to the anomalous tbW vertex and hence is a pure probe of new physics in top quark production. Spin sensitive variables involving the decay lepton are used to reconstruct the top polarization. Some sensitivity is found for the new couplings of the top.

On measurement of top polarization as a probe of t(t)over-bar production mechanisms at the LHC

In this note we demonstrate the use of top polarization in the study of t (t) over bar resonances at the LHC, in the possible case where the dynamics implies a non-zero top polarization. As a probe of top polarization we construct an asymmetry in the decay-lepton azimuthal angle distribution (corresponding to the sign of cos phi(l)) in the laboratory. The asymmetry is non-vanishing even for a symmetric collider like the LHC, where a positive z axis is not uniquely defined. The angular distribution of the leptons has the advantage of being a faithful top-spin analyzer, unaffected by possible anomalous tbW couplings, to linear order. We study, for purposes of demonstration, the case of a Z' as might exist in the little Higgs models. We identify kinematic cuts which ensure that our asymmetry reflects the polarization in sign and magnitude. We investigate possibilities at the LHC with two energy options: root s = 14TeV and root s = 7TeV, as well as at the Tevatron. At the LHC the model predicts net top quark polarization of the order of a few per cent for M-Z' similar or equal to 1200GeV, being as high as 10% for a smaller mass of the Z' of 700GeV and for the largest allowed coupling in the model, the values being higher for the 7TeV option. These polarizations translate to a deviation from the standard-model value of azimuthal asymmetry of up to about 4% (7%) for 14 (7) TeV LHC, whereas for the Tevatron, values as high as 12% are attained. For the 14TeV LHC with an integrated luminosity of 10 fb(-1), these numbers translate into a 3 sigma sensitivity over a large part of the range 500 less than or similar to M-Z' less than or similar to 1500GeV.

Missile battery placement for air defense: A dynamic programming approach

A procedure to evaluate surface-to-air missile battery placement patterns for air defense is presented. A measure of defense effectiveness is defined as a function of kill probability of the defense missiles and the nature of the surrounding terrain features. The concept of cumulative danger index is used to select the best path for a penetrating hostile aircraft for any given pattern of placement. The aircraft is assumed to be intelligent and well-informed. The path is generated using a dynamic programming methodology. The software package so developed can be used off-line to choose the best among a number of possible battery placement patterns.

Wind loading over the top portions of tall stacks with and without external landing platforms

The variation of the drag force near the top portions of tall stacks with and without external landing platforms, and with the exit open and closed, has been examined by model studies in a wind tunnel at Reynolds numbers of about 10(5). Pressure measurements on three models of different height to diameter ratios have been supplemented by flow visualisation studies. Observations confirm that when there is no platform, significant load enhancement over the top three to four diameters occurs, due to the high suction caused by the sharp separation of the flow over the top from the rim, in the aft regions of the stack. The enhanced loading is found to be greater if the exit is closed. A platform at the top, of less than twice the exit diameter, further increases the drag force near the top, but a still larger platform at the top, of about three times the exit diameter, decreases the drag force to values less than those much further below, effectively nullifying the enhanced drag force. It was found that such a reduction of the enhanced drag force in the top regions can also be achieved by a smaller platform of 1.1 to 1.3 times the local diameter, located at about three to five diameters below the top.

Rayleigh-Benard convection during solidification of an eutectic solution cooled from the top

The interaction between laminar Rayleigh-Benard convection and directional solidification is studied for the case of an eutectic solution kept in a rectangular cavity cooled from the top. Experiments and numerical simulations are carried out using an NH4Cl-H2O solution as the model fluid. The flow is visualized using a sheet of laser light scattered by neutrally buoyant, hollow-glass spheres seeded in the fluid. The numerical modeling is performed using a pressure-based finite-volume method according to the SIMPLER algorithm. The present configuration enables us to visualize flow vortices in the presence of a continuously evolving solid/liquid interface. Clear visualization of the Rayleigh-Benard convective cells and their interaction with the solidification front are obtained. It is observed that the convective cells are characterized by zones of up-flow and down-flow, resulting in the development of a nonplanar interface. Because of the continuous advancement of the solid/liquid interface, the effective liquid height of the cavity keeps decreasing. Once the height of the fluid layer falls below a critical value, the convective cells become weaker and eventually die out, leading to the growth of a planar solidification front. Results of flow visualization and temperature measurement are compared with those from the numerical simulation, and a good agreement is found.