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.

On Network-Error Correcting Convolutional Codes under the BSC Edge Error Model

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error pe(0 <= p(e) < 0.5). We obtain bounds on the performance of such CNECCs based on a modified generating function (the transfer function) of the CNECCs. For a given network, we derive a mathematical condition on how small p(e) should be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low p(e) and high p(e) regimes. For the low p(e) regime, convolutional codes with good distance properties show good performance. For the high p(e) regime, convolutional codes that have a good slope ( the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate b/c convolutional code with a certain degree.

Multiple UAV Coalitions for a Search and Prosecute Mission

Unmanned aerial vehicles (UAVs) have the potential to carry resources in support of search and prosecute operations. Often to completely prosecute a target, UAVs may have to simultaneously attack the target with various resources with different capacities. However, the UAVs are capable of carrying only limited resources in small quantities, hence, a group of UAVs (coalition) needs to be assigned that satisfies the target resource requirement. The assigned coalition must be such that it minimizes the target prosecution delay and the size of the coalition. The problem of forming coalitions is computationally intensive due to the combinatorial nature of the problem, but for real-time applications computationally cheap solutions are required. In this paper, we propose decentralized sub-optimal (polynomial time) and decentralized optimal coalition formation algorithms that generate coalitions for a single target with low computational complexity. We compare the performance of the proposed algorithms to that of a global optimal solution for which we need to solve a centralized combinatorial optimization problem. This problem is computationally intensive because the solution has to (a) provide a coalition for each target, (b) design a sequence in which targets need to be prosecuted, and (c) take into account reduction of UAV resources with usage. To solve this problem we use the Particle Swarm Optimization (PSO) technique. Through simulations, we study the performance of the proposed algorithms in terms of mission performance, complexity of the algorithms and the time taken to form the coalition. The simulation results show that the solution provided by the proposed algorithms is close to the global optimal solution and requires far less computational resources.

Smart applications for energy harvested WSNs

A Wireless Sensor Network (WSN) powered using harvested energies is limited in its operation by instantaneous power. Since energy availability can be different across nodes in the network, network setup and collaboration is a non trivial task. At the same time, in the event of excess energy, exciting node collaboration possibilities exist; often not feasible with battery driven sensor networks. Operations such as sensing, computation, storage and communication are required to achieve the common goal for any sensor network. In this paper, we design and implement a smart application that uses a Decision Engine, and morphs itself into an energy matched application. The results are based on measurements using IRIS motes running on solar energy. We have done away with batteries; instead used low leakage super capacitors to store harvested energy. The Decision Engine utilizes two pieces of data to provide its recommendations. Firstly, a history based energy prediction model assists the engine with information about in-coming energy. The second input is the energy cost database for operations. The energy driven Decision Engine calculates the energy budgets and recommends the best possible set of operations. Under excess energy condition, the Decision Engine, promiscuously sniffs the neighborhood looking for all possible data from neighbors. This data includes neighbor's energy level and sensor data. Equipped with this data, nodes establish detailed data correlation and thus enhance collaboration such as filling up data gaps on behalf of nodes hibernating under low energy conditions. The results are encouraging. Node and network life time of the sensor nodes running the smart application is found to be significantly higher compared to the base application.

Wavelength/Time orthogonal codes with FEC offer dual advantage

To meet the growing demands of the high data rate applications, suitable asynchronous schemes such as Fiber-Optic Code Division Multiple Access (FO-CDMA) are required in the last mile. FO-CDMA scheme offers potential benefits and at the same time it faces many challenges. Wavelength/Time (W/T) 2-D codes for use in FO-CDMA, can be classified mainly into two types: 1) hybrid codes and 2) matrix codes, to reduce the 'time' like property, have been proposed. W/T single-pulse-per-row (SPR) are energy efficient codes as this family of codes have autocorrelation sidelobes of '0', which is unique to this family and the important feature of the W/T multiple-pulses-per-row (MPR) codes is that the aspect ratio can be varied by trade off between wavelength and temporal lengths. These W/T codes have improved cardinality and spectral efficiency over other W/T codes and at the same time have lowest crosscorrelation values. In this paper, we analyze the performances of the FO-CDMA networks using W/T SPR codes and W/T MPR codes, with and without forward error correction (FEC) coding and show that with FEC there is dual advantage of error correction and reduced spread sequence length.

GNSS Signal Detection Under Noise Uncertainty

High sensitivity detection techniques are required for indoor navigation using Global Navigation Satellite System (GNSS) receivers, and typically, a combination of coherent and non- coherent integration is used as the test statistic for detection. The coherent integration exploits the deterministic part of the signal and is limited due to the residual frequency error, navigation data bits and user dynamics, which are not known apriori. So, non- coherent integration, which involves squaring of the coherent integration output, is used to improve the detection sensitivity. Due to this squaring, it is robust against the artifacts introduced due to data bits and/or frequency error. However, it is susceptible to uncertainty in the noise variance, and this can lead to fundamental sensitivity limits in detecting weak signals. In this work, the performance of the conventional non-coherent integration-based GNSS signal detection is studied in the presence of noise uncertainty. It is shown that the performance of the current state of the art GNSS receivers is close to the theoretical SNR limit for reliable detection at moderate levels of noise uncertainty. Alternate robust post-coherent detectors are also analyzed, and are shown to alleviate the noise uncertainty problem. Monte-Carlo simulations are used to confirm the theoretical predictions.

Training and Voids in Receive Antenna Subset Selection in Time-Varying Channels

Receive antenna selection (AS) provides many benefits of multiple-antenna systems at drastically reduced hardware costs. In it, the receiver connects a dynamically selected subset of N available antennas to the L available RF chains. Due to the nature of AS, the channel estimates at different antennas, which are required to determine the best subset for data reception, are obtained from different transmissions of the pilot sequence. Consequently, they are outdated by different amounts in a time-varying channel. We show that a linear weighting of the estimates is necessary and optimum for the subset selection process, where the weights are related to the temporal correlation of the channel variations. When L is not an integer divisor of N , we highlight a new issue of ``training voids'', in which the last pilot transmission is not fully exploited by the receiver. We then present new ``void-filling'' methods that exploit these voids and greatly improve the performance of AS. The optimal subset selection rules with void-filling, in which different antennas turn out to have different numbers of estimates, are also explicitly characterized. Closed-form equations for the symbol error probability with and without void-filling are also developed.

Crystal structure of Rv2118c: an AdoMet-dependent methyltransferase from Mycobacterium tuberculosis H37Rv

Rv2118c belongs to the class of conserved hypothetical proteins from Mycobacterium tuberculosis H37Rv. The crystal structure of Rv2118c in complex with S-adenosyl-Image -methionine (AdoMet) has been determined at 1.98 Å resolution. The crystallographic asymmetric unit consists of a monomer, but symmetry-related subunits interact extensively, leading to a tetrameric structure. The structure of the monomer can be divided functionally into two domains: the larger catalytic C-terminal domain that binds the cofactor AdoMet and is involved in the transfer of methyl group from AdoMet to the substrate and a smaller N-terminal domain. The structure of the catalytic domain is very similar to that of other AdoMet-dependent methyltransferases. The N-terminal domain is primarily a β-structure with a fold not found in other methyltransferases of known structure. Database searches reveal a conserved family of Rv2118c-like proteins from various organisms. Multiple sequence alignments show several regions of high sequence similarity (motifs) in this family of proteins. Structure analysis and homology to yeast Gcd14p suggest that Rv2118c could be an RNA methyltransferase, but further studies are required to establish its functional role conclusively.

Measurement of Heat Transfer Rate on Backward-Facing Steps at Hypersonic Mach Number

Two backward-facing models with step heights of 2 and 3 mm are used to measure the convective surface heat transfer rates by using platinum thin-film gauges, deposited on Macor inserts. Heat transfer rates have been theoretically calculated along the flat plate portion of a model using the Eckert reference temperature method. The experimentally determined surface heat transfer rate distributions are compared with theoretical and numerical estimations. Experimental heat flux distribution over a flat plate model showed good agreement with the reference temperature method at stagnation enthalpy range of 0.8-2 MJ/kg. Theoretical analysis has been used for downstream of a backward-facing step using Gai's nondimensional analysis. It has been found from the present study that approximately 10 and 8 step heights are required for the flow to reattach for 2 and 3 mm step height backward-facing step models, respectively, at a nominal Mach number of 7.6.

Crystal structure of quenched and in-field electroluminescent phosphors

Electroluminescent zinc sulfide doped with copper and chloride (ZnS:Cu, Cl) powder was heated to 400°C and rapidly quenched to room temperature. Comparison between the quenched and non-quenched phosphors using synchrotron radiation X-ray powder diffraction (XRPD) (λ = 0.828692 Å) and X-ray absorption spectroscopy (XAS) was made. XRPD shows that the expected highly faulted structure is observed with excellent resolution out to 150° 2θ (or to (12 2 2) of the sphalerite phase). The quenched sample compared to the unheated sample shows a large change in peak ratios between 46.7° and 46.9°, which is thought to correspond to the wurtzite (0 0 6), (0 3 2) and sphalerite (3 3 3)/(5 1 1) peaks. Hence, a large proportion of this sphalerite diffraction is lost from the material upon rapid quenching, but not when the material is allowed to cool slowly. The Zn K-edge XAS data indicate that the crystalline structures are indistinguishable using this technique, but do give an indication that the electronic structure has altered due to changing intensity of the white line. It is noted that the blue electroluminescence (EL) emission bands are lost upon quenching: however, a large amount of total EL emission intensity is also removed, which is consistent with our findings. We report the XRPD of a working alternating-current electroluminescence device in the synchrotron X-ray beam, which exhibits a new diffraction pattern when the device is powered in an AC field even though the phosphor is fixed in the binder. Significantly, only a few crystals are required to yield the diffraction data because of the high flux X-ray source. These in panel data show multiple sharp diffraction lines spread out under the region, where capillary data show broad diffraction intensity indicating that the phosphor powder is comprised of unique crystals, each having different structures.

Geographic Resources Decision Support System – an Open Source GIS

Fully structured and matured open source spatial and temporal analysis technology seems to be the official carrier of the future for planning of the natural resources especially in the developing nations. This technology has gained enormous momentum because of technical superiority, affordability and ability to join expertise from all sections of the society. Sustainable development of a region depends on the integrated planning approaches adopted in decision making which requires timely and accurate spatial data. With the increased developmental programmes, the need for appropriate decision support system has increased in order to analyse and visualise the decisions associated with spatial and temporal aspects of natural resources. In this regard Geographic Information System (GIS) along with remote sensing data support the applications that involve spatial and temporal analysis on digital thematic maps and the remotely sensed images. Open source GIS would help in wide scale applications involving decisions at various hierarchical levels (for example from village panchayat to planning commission) on economic viability, social acceptance apart from technical feasibility. GRASS (Geographic Resources Analysis Support System, http://wgbis.ces.iisc.ernet.in/grass) is an open source GIS that works on Linux platform (freeware), but most of the applications are in command line argument, necessitating a user friendly and cost effective graphical user interface (GUI). Keeping these aspects in mind, Geographic Resources Decision Support System (GRDSS) has been developed with functionality such as raster, topological vector, image processing, statistical analysis, geographical analysis, graphics production, etc. This operates through a GUI developed in Tcltk (Tool command language / Tool kit) under Linux as well as with a shell in X-Windows. GRDSS include options such as Import /Export of different data formats, Display, Digital Image processing, Map editing, Raster Analysis, Vector Analysis, Point Analysis, Spatial Query, which are required for regional planning such as watershed Analysis, Landscape Analysis etc. This is customised to Indian context with an option to extract individual band from the IRS (Indian Remote Sensing Satellites) data, which is in BIL (Band Interleaved by Lines) format. The integration of PostgreSQL (a freeware) in GRDSS aids as an efficient database management system.

Fusion of multi resolution remote sensing data for urban sprawl analysis

Urban population is growing at around 2.3 percent per annum in India. This is leading to urbanisation and often fuelling the dispersed development in the outskirts of urban and village centres with impacts such as loss of agricultural land, open space, and ecologically sensitive habitats. This type of upsurge is very much prevalent and persistent in most places, often inferred as sprawl. The direct implication of such urban sprawl is the change in land use and land cover of the region and lack of basic amenities, since planners are unable to visualise this type of growth patterns. This growth is normally left out in all government surveys (even in national population census), as this cannot be grouped under either urban or rural centre. The investigation of patterns of growth is very crucial from regional planning point of view to provide basic amenities in the region. The growth patterns of urban sprawl can be analysed and understood with the availability of temporal multi-sensor, multi-resolution spatial data. In order to optimise these spectral and spatial resolutions, image fusion techniques are required. This aids in integrating a lower spatial resolution multispectral (MSS) image (for example, IKONOS MSS bands of 4m spatial resolution) with a higher spatial resolution panchromatic (PAN) image (IKONOS PAN band of 1m spatial resolution) based on a simple spectral preservation fusion technique - the Smoothing Filter-based Intensity Modulation (SFIM). Spatial details are modulated to a co-registered lower resolution MSS image without altering its spectral properties and contrast by using a ratio between a higher resolution image and its low pass filtered (smoothing filter) image. The visual evaluation and statistical analysis confirms that SFIM is a superior fusion technique for improving spatial detail of MSS images with the preservation of spectral properties.

Strength of lime-fly ash compacts using different curing techniques and gypsum additive

Lime-fly ash mixtures are exploited for the manufacture of fly ash bricks finding applications in load bearing masonry. Lime-pozzolana reactions take place at a slow pace under ambient temperature conditions and hence very long curing durations are required to achieve meaningful strength values. The present investigation examines the improvements in strength development in lime-fly ash compacts through low temperature steam curing and use of additives like gypsum. Results of density-strength-moulding water content relationships, influence of lime-fly ash ratio, steam curing and role of gypsum on strength development, and characteristics of compacted lime-fly ash-gypsum bricks have been discussed. The test results reveal that (a) strength increases with increase in density irrespective of lime content, type of curing and moulding water content, (b) optimum lime-fly ash ratio yielding maximum strength is about 0.75 in the normal curing conditions, (c) 24 h of steam curing (at 80A degrees C) is sufficient to achieve nearly possible maximum strength, (d) optimum gypsum content yielding maximum compressive strength is at 2%, (e) with gypsum additive it is possible to obtain lime-fly ash bricks or blocks having sufficient strength (> 10 MPa) at 28 days of normal wet burlap curing.

Molecular profile of oligodendrogliomas in young patients

Several studies on molecular profiling of oligodendrogliomas (OGs) in adults have shown a distinctive genetic pattern characterized by combined deletions of chromosome arms 1 p and 19q, O6-methylguanine-methyltransferase (MGMT) methylation, and isocitrate dehydrogenase 1 (IDH1) mutation, which have potential diagnostic, prognostic, and even therapeutic relevance. OGs in pediatric and young adult patients are rare and have been poorly characterized on a molecular and biological basis, and it remains uncertain whether markers with prognostic significance in adults also have predictive value in these patients. Fourteen cases of OGs in young patients (age, <= 25 years) who received a diagnosis over 7 years were selected (7 pediatric patients age <= 18 years and 7 young adults aged 19-25 years). The cases were evaluated for 1p/19q status, MGMT promoter methylation, p53 mutation, and IDH1 mutation. None of the pediatric cases showed 1p/19q deletion. In young adults, combined 1p/19q loss was observed in 57% and isolated 1p loss in 14% of cases. The majority of cases in both subgroups (71% in each) harbored MGMT gene promoter methylation. TP53 and IDH1 mutations were not seen in any of the cases in both the groups. To our knowledge, this is the first study to show that molecular profile of OGs in pediatric and young adult patients is distinct. Further large-scale studies are required to identify additional clinically relevant genetic alterations in this group of patients.

The Thermodynamics of Oxygen in Reactive Metals

For some new applications of metals in functional devices, metals of high purity are required. In recent years, many high-purity metals have been produced commercially for use in electronics, but the demand for ultra-high-purity metals is increasing rapidly because of more stringent specifications for materials used in high-performance information devices.