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-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.

SPSA Based Feature Relevance Estimation For Video Retrieval

With the availability of a huge amount of video data on various sources, efficient video retrieval tools are increasingly in demand. Video being a multi-modal data, the perceptions of ``relevance'' between the user provided query video (in case of Query-By-Example type of video search) and retrieved video clips are subjective in nature. We present an efficient video retrieval method that takes user's feedback on the relevance of retrieved videos and iteratively reformulates the input query feature vectors (QFV) for improved video retrieval. The QFV reformulation is done by a simple, but powerful feature weight optimization method based on Simultaneous Perturbation Stochastic Approximation (SPSA) technique. A video retrieval system with video indexing, searching and relevance feedback (RF) phases is built for demonstrating the performance of the proposed method. The query and database videos are indexed using the conventional video features like color, texture, etc. However, we use the comprehensive and novel methods of feature representations, and a spatio-temporal distance measure to retrieve the top M videos that are similar to the query. In feedback phase, the user activated iterative on the previously retrieved videos is used to reformulate the QFV weights (measure of importance) that reflect the user's preference, automatically. It is our observation that a few iterations of such feedback are generally sufficient for retrieving the desired video clips. The novel application of SPSA based RF for user-oriented feature weights optimization makes the proposed method to be distinct from the existing ones. The experimental results show that the proposed RF based video retrieval exhibit good performance.

Secondary attribute retrieval using tree data structures

Several techniques are known for searching an ordered collection of data. The techniques and analyses of retrieval methods based on primary attributes are straightforward. Retrieval using secondary attributes depends on several factors. For secondary attribute retrieval, the linear structures—inverted lists, multilists, doubly linked lists—and the recently proposed nonlinear tree structures—multiple attribute tree (MAT), K-d tree (kdT)—have their individual merits. It is shown in this paper that, of the two tree structures, MAT possesses several features of a systematic data structure for external file organisation which make it superior to kdT. Analytic estimates for the complexity of node searchers, in MAT and kdT for several types of queries, are developed and compared.

How Good is the Assumption About Visible Surface Reflectance in MODIS Aerosol Retrieval Over Land? A Comparison With Aircraft Measurements Over an Urban Site in India

In this paper, we discuss the measurements of spectral surface reflectance (rho(s)(lambda)) in the wavelength range 350-2500 nm measured using a spectroradiometer onboard a low-flying aircraft over Bangalore (12.95 degrees N, 77.65 degrees E), an urban site in southern India. The large discrepancies in the retrieval of aerosol propertiesover land by the Moderate-Resolution Imaging Spectroradiometer (MODIS), which could be attributed to the inaccurate estimation of surface reflectance at many sites in India and elsewhere, provided motivation for this paper. The aim of this paper was to verify the surface reflectance relationships assumed by the MODIS aerosol algorithm for the estimation of surface reflectance in the visible channels (470 and 660 nm) from the surface reflectance at 2100 nm for aerosol retrieval over land. The variety of surfaces observed in this paper includes green and dry vegetations, bare land, and urban surfaces. The measuredreflectance data were first corrected for the radiative effects of atmosphere lying between the ground and aircraft using the Second Simulation of Satellite Signal in the Solar Spectrum (6S) radiative transfer code. The corrected surface reflectance in the MODIS's blue (rho(s)(470)), red (rho(s)(660)), and shortwave-infrared (SWIR) channel (rho(s)(2100)) was linearly correlated. We found that the slope of reflectance relationship between 660 and 2100 nm derived from the forward scattering data was 0.53 with an intercept of 0.07, whereas the slope for the relationship between the reflectance at 470 and 660 nm was 0.85. These values are much higher than the slope (similar to 0.49) for either wavelengths assumed by the MODIS aerosol algorithm over this region. The reflectance relationship for the backward scattering data has a slope of 0.39, with an intercept of 0.08 for 660 nm, and 0.65, with an intercept of 0.08 for 470 nm. The large values of the intercept (which is very small in the MODIS reflectance relationships) result in larger values of absolute surface reflectance in the visible channels. The discrepancy between the measured and assumed surface reflectances could lead to error in the aerosol retrieval. The reflectance ratio (rho(s)(660)/rho(s)(2100)) showed a clear dependence on the N D V I-SWIR where the ratio increased from 0.5 to 1 with an increase in N V I-SWIR from 0 to 0.5. The high correlation between the reflectance at SWIR wavelengths (2100, 1640, and 1240 nm) indicated an opportunity to derive the surface reflectance and, possibly, aerosol properties at these wavelengths. We need more experiments to characterize the surface reflectance and associated inhomogeneity of land surfaces, which play a critical role in the remote sensing of aerosols over land.

Systematic bias in MODIS dust aerosol retrieval at Kanpur (AERONET), Indo-Gangetic Basin - art.no.640816

We have compared the spectral aerosol optical depth (AOD) and aerosol fine mode fraction (AFMF) derived from Moderate Resolution Imaging Spectroradiometer (MODIS) with those of Aerosol Robotic Network (AERONET) at Kanpur (26.45N, 80.35E), northern India for the pre-monsoon season (March to June, 2001-2005). We found that MODIS systematically overestimates AOD during pre-monsoon season (known to be influenced by dust transport from north-west of India). The errors in AOD were correlated with the MODIS top-of-atmosphere apparent surface reflectance in 2.1 mu m channel (rho*(2.1)). MODIS aerosol algorithm uses p*(2.1) to derive the surface reflectance in visible channels (rho(0.47), rho(0.66)) using an empirical mid IR-visible correlation (rho(0.47) = rho(2.1)/4, rho(0.66) = rho(2.1)/2). The large uncertainty in estimating surface reflectance in visible channels (Delta rho(0.66)+/- 0.04, Delta rho(0.47)+/- 0.02) at higher values of p*(2.1) (p*(2.1) > 0.18) leads to higher aerosol contribution in the total reflected radiance at top-of atmosphere to compensate for the reduced surface reflectance in visible channels and thus leads to overestimation of AOD. This was also reflected in the very low values of AFMF during pre-monsoon whose accuracy depends on the aerosol path radiance in 0.47 and 0.66 mu m channels and aerosol models. The errors in AOD were also high in the scattering angle range 110 degrees-140 degrees, where the effect of dust non-spherity on its optical properties is significant. The direct measurements of spectral surface reflectance are required over the Indo-Gangetic basin in order to validate the mid IR-visible relationship. MODIS aerosol models should also be modified to incorporate the effect of non-spherity of dust aerosols.

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.

Retrieval of dust aerosols during night: improved assessment of long wave dust radiative forcing over Afro-Asian regions

Several investigators in the past have used the radiance depression (with respect to clear-sky infrared radiance), resulting from the presence of mineral dust aerosols in the atmosphere, as an index of dust aerosol load in the atmosphere during local noon. Here, we have used a modified approach to retrieve dust index during night since assessment of diurnal average infrared dust forcing essentially requires information on dust aerosols during night. For this purpose, we used infrared radiance (10.5-12.5 mu m), acquired from the METEOSAT-5 satellite (similar to 5 km resolution). We found that the `dust index' algorithm, valid for daytime, will no longer hold during the night because dust is then hotter than the theoretical dust-free reference. Hence we followed a `minimum reference' approach instead of a conventional `maximum reference' approach. A detailed analysis suggests that the maximum dust load occurs during the daytime. Over the desert regions of India and Africa, maximum change in dust load is as much as a factor of four between day and night and factor of two variations are commonly observed. By realizing the consequent impact on long wave dust forcing, sensitivity studies were carried out, which indicate that utilizing day time data for estimating the diurnally averaged long-wave dust radiative forcing results in significant errors (as much as 50 to 70%). Annually and regionally averaged long wave dust radiative forcing (which account for the diurnal variation of dust) at the top of the atmosphere over Afro-Asian region is 2.6 +/- 1.8 W m(-2), which is 30 to 50% lower than those reported earlier. Our studies indicate that neglecting diurnal variation of dust while assessing its radiative impact leads to an overestimation of dust radiative forcing, which in turn result in underestimation of the radiative impact of anthropogenic aerosols.

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.

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.

Tar characterisation in new generation agro-residue gasifiers - Cyclone and downdraft open top twin air entry systems

This paper deals with the characterisation of tar from two configurations of bioresidue thermochemical conversion reactors designed for producer gas based power generation systems. The pulverised fuel reactor is a cyclone system (R1) and the solid bioresidue reactor (denoted R2) is an open top twin air entry system both at 75-90 kg/h capacity (to generate electricity similar to 100 kVA). The reactor, R2, has undergone rigorous test in a major Indo-Swiss programme for the tar quantity at various conditions. The former is a recent technology development. Tars collected from these systems by a standard tar collection apparatus at the laboratory at Indian Institute of Science have been analysed at the Royal Institute of Technology (KTH), Sweden. The results of these analyses show that these thermochemical conversion reactors behave differently from the earlier reactors reported in literature in so far as tar generation is concerned. The extent of tar in hot gas is about 700-800 ppm for R1 and 70-100 ppm for R2. The amounts of the major compounds - naphthalene and phenol-are much lower that what is generally understood to happen in the gasifiers in Europe. It is suggested that the longer residence times at high temperatures allowed for in these reactors is responsible for this behavior. It is concluded the new generation reactor concepts extensively tried out at lower power levels hold promise for high power atmospheric gasification systems for woody as well as pulverisable bioresidues.