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.

Quenching across quantum critical points: Role of topological patterns

We introduce a one-dimensional version of the Kitaev model consisting of spins on a two-legged ladder and characterized by Z(2) invariants on the plaquettes of the ladder. We map the model to a fermionic system and identify the topological sectors associated with different Z2 patterns in terms of fermion occupation numbers. Within these different sectors, we investigate the effect of a linear quench across a quantum critical point. We study the dominant behavior of the system by employing a Landau-Zener-type analysis of the effective Hamiltonian in the low-energy subspace for which the effective quenching can sometimes be non-linear. We show that the quenching leads to a residual energy which scales as a power of the quenching rate, and that the power depends on the topological sectors and their symmetry properties in a non-trivial way. This behavior is consistent with the general theory of quantum quenching, but with the correlation length exponent nu being different in different sectors. Copyright (C) EPLA, 2010

A study of the synthetic methods and properties of graphenes

Graphenes with varying number of layers can be synthesized by using different strategies. Thus, single-layer graphene is prepared by micromechanical cleavage, reduction of single-layer graphene oxide, chemical vapor deposition and other methods. Few-layer graphenes are synthesized by conversion of nanodiamond, arc discharge of graphite and other methods. In this article, we briefly overview the various synthetic methods and the surface, magnetic and electrical properties of the produced graphenes. Few-layer graphenes exhibit ferromagnetic features along with antiferromagnetic properties, independent of the method of preparation. Aside from the data on electrical conductivity of graphenes and graphene-polymer composites, we also present the field-effect transistor characteristics of graphenes. Only single-layer reduced graphene oxide exhibits ambipolar properties. The interaction of electron donor and acceptor molecules with few-layer graphene samples is examined in detail.

Electron paramagnetic resonance studies on Mn doped GaSb

We report on the X-band (similar to 9.43 GHz) electron paramagnetic resonance (EPR) investigations carried out on polycrystalline Ga1-xMnxSb (x=0.02). A strong EPR signal with an effective g factor (g(eff)) close to 2.00 was observed, suggesting that the ionic state of Mn which replaces Ga ion in the lattice, is Mn2+ attributable to Delta M=1 transition of the ionized Mn acceptor A(-), Mn (3d(5)). The apparent absence of EPR signal, typical for neutral Mn acceptor at g=2.7 suggests either no such centers are present or the signal broadens beyond detection limit. The temperature dependent EPR studies combined with dc magnetization data suggest the possible coexistence of antiferromagnetic and ferromagnetic phases at very low temperatures. (C) 2011 American Institute of Physics. doi:10.1063/1.3543983]

Optimal pulse spacing for dynamical decoupling in the presence of a purely dephasing spin bath

Maintaining quantum coherence is a crucial requirement for quantum computation; hence protecting quantum systems against their irreversible corruption due to environmental noise is an important open problem. Dynamical decoupling (DD) is an effective method for reducing decoherence with a low control overhead. It also plays an important role in quantum metrology, where, for instance, it is employed in multiparameter estimation. While a sequence of equidistant control pulses the Carr-Purcell-Meiboom-Gill (CPMG) sequence] has been ubiquitously used for decoupling, Uhrig recently proposed that a nonequidistant pulse sequence the Uhrig dynamic decoupling (UDD) sequence] may enhance DD performance, especially for systems where the spectral density of the environment has a sharp frequency cutoff. On the other hand, equidistant sequences outperform UDD for soft cutoffs. The relative advantage provided by UDD for intermediate regimes is not clear. In this paper, we analyze the relative DD performance in this regime experimentally, using solid-state nuclear magnetic resonance. Our system qubits are C-13 nuclear spins and the environment consists of a H-1 nuclear spin bath whose spectral density is close to a normal (Gaussian) distribution. We find that in the presence of such a bath, the CPMG sequence outperforms the UDD sequence. An analogy between dynamical decoupling and interference effects in optics provides an intuitive explanation as to why the CPMG sequence performs better than any nonequidistant DD sequence in the presence of this kind of environmental noise.

Effective action and adiabatic expansions for the 1-D and 2-D hubbard models at half-filling

We analyze here the occurrence of antiferromagnetic (AFM) correlations in the half-filled Hubbard model in one and two space dimensions using a natural fermionic representation of the model and a newly proposed way of implementing the half-filling constraint. We find that our way of implementing the constraint is capable of enforcing it exactly already at the lowest levels of approximation. We discuss how to develop a systematic adiabatic expansion for the model and how Berry's phase contributions arise quite naturally from the adiabatic expansion. At low temperatures and in the continuum limit the model gets mapped onto an O(3) nonlinear sigma model (NLsigma). A topological, Wess-Zumino term is present in the effective action of the ID NLsigma as expected, while no topological terms are present in 2D. Some specific difficulties that arise in connection with the implementation of an adiabatic expansion scheme within a thermodynamic context are also discussed, and we hint at possible solutions.

Effect of substitution of Y on the structural, magnetic, and thermal properties of hexagonal DyMnO3 single crystals

We investigate the structural, magnetic, and specific heat behavior of the hexagonal manganite Dy0.5Y0.5MnO3 in order to understand the effect of dilution of Dy magnetism with nonmagnetic yttrium. In this compound, the triangular Mn lattice orders antiferromagnetic at T-N(Mn) approximate to 68 K observed experimentally in the derivative of magnetic susceptibility as well as in specific heat. In addition, a low-temperature peak at T-N(Dy) similar to 3 K is observed in specific heat which is attributed to rare earth order. The T-N(Mn) increases by 9 K compared to that of hexagonal (h) DyMnO3 while T-N(Dy) is unchanged. A change in slope of thermal evolution of lattice parameters is observed to occur at temperature close to T-N(Mn). This hints at strong magnetoelastic coupling in this geometric multiferroic. In magnetization measurements, steplike features are observed when the magnetic field is applied along the c axis which shift to higher fields with temperature and vanish completely above 40 K. The presence of different magnetic phases at low temperature and strong magnetoelastic effects can lead to such field-induced transitions which resemble metamagnetic transitions. This indicates the possibility of strong field-induced effects in dielectric properties of this material, which is unexplored to date.

Magnetic properties of rare earth nickelates of the Ln(2)BaNiO(5) family

Rare-earth nickelates Ln(2)BaNi(1-x)Cu(2)O(5), Ln = Nd and Dy, and Dy2-xYxBaNiO5 have been synthesized in order to investigate the effect of substitution of Ni by Cu and Dy by nonmagnetic Y on the magnetic properties of the nickelates. In Ln(2)BaNi(1-x)Cu(x)O(5), the nickelate structure (x=0.0) changes to the cuprate structure (x=1.0) at a specific composition (x=0.3). The Neel temperature of Nd2BaNi1-xCuxO5 decreases continuously with increase in x upto x=0.3 (T-N = 18K); when x > 0.3, the materials are paramagnetic down to 20K. The mu(eff) in Nd2BaNi1-xCxO5 essentially corresponds to the contribution of the Nd ions. In Dy2-xYxBaNiO5, the Neel temperature decreases from 40K when x=0.0 to 24K when x=1.5. The compositions with 1.5 less than or equal to x less than or equal to 2 (including the x=1.95 composition) are paramagnetic down to 20K, unlike Y2BaNiO5 (x=2.0) which exhibits a T-N of 370K. Even the smallest concentration of paramagnetic Dy seems to destroy the antiferromagnetic Ni-O-Ni chains in Y2BaNiO5.

Density-matrix renormalization-group studies of the spin-1/2 Heisenberg system with dimerization and frustration

Using the density-matrix renormalization-group technique, we study the ground-state phase diagram and other low-energy properties of an isotropic antiferromagnetic spin-1/2 chain with both dimerization and frustration, i.e., an alternation delta of the nearest-neighbor exchanges and a next-nearest-neighbor exchange J(2). For delta = 0, the system is gapless for J(2) < J(2c) and has a gap for J(2) > J(2c) where J(2c) is about 0.241. For J(2) = J(2c) the gap above the ground state grows as delta to the power 0.667 +/- 0.001. In the J(2)-delta plane, there is a disorder line 2J(2) + delta = 1. To the left of this line, the peak in the static structure factor S(q) is at q(max) = pi (Neel phase), while to the right of the line, q(max) decreases from pi to pi/2 as J(2) is increased to large values (spiral phase). For delta = 1, the system is equivalent to two coupled chains as on a ladder and it is gapped for all values of the interchain coupling.

Enhanced charge and spin currents in the one-dimensional disordered mesoscopic Hubbard ring

We consider a one-dimensional mesoscopic Hubbard ring with and without disorder and compute charge and spin stiffness as a measure of the permanent currents. For finite disorder we identify critical disorder strength beyond which the charge currents in a system with repulsive interactions are larger than those for a free system. The spin currents in the disordered repulsive Hubbard model are enhanced only for small U, where the magnetic state of the system corresponds to a charge-density wave pinned to the impurities. For large U, the state of the system corresponds to localized isolated spins and the spin currents are found to be suppressed. For the attractive Hubbard model we find that the charge currents are always suppressed compared to the free system at all length scales.

Charge-ordering in manganates

Ordering of Mn3+ and Mn4+ ions occurs in the rare earth manganates of the general composition Ln(1-x)A(x)MnO(3) (Ln rare earth, A = Ca, Sr). Such charge-ordering is associated with antiferromagnetic and insulating properties. This phenomenon is to be contrasted with the ferromagnetic metallic behavior that occurs when double-exchange between the Mn3+ and Mn4+ ions predominates. Two distinct types of charge-ordering can be delineated. In one, a ferromagnetic metallic (FMM) state transforms to the charge-ordered (CO) state on cooling. In the other scenario, the CO state is found in the paramagnetic ground stale and there is no ferromagnetism down to the lowest temperatures. Magnetic fields transform the CO state to the FMM state, when the average radius of the A-site cations is sufficiently large ([r(A)] > 1.17 Angstrom). Chemical melting of the CO state by Cr3+ substitution in the Mn site is also found only when [r(A)] greater than or similar to 1.17 Angstrom. The effect of the size of the A-cations on the Mn-O-Mn angle is not enough to explain the observed variations of the charge-ordering temperature as well as the ferromagnetic Curie temperature T-c. An explanation based on a competition between the Mn and A-cation orbitals for sigma-bonding with the oxygen rho(sigma) orbitals is considered to account for the large changes in T-c and hence the true bandwidth, with [r(A]). Effects of radiation, electric field, and other factors on the CO state are discussed along with charge-ordering in other manganate systems. Complex phase transitions, accompanied by changes in electronic and magnetic properties, occur in manganates with critical values of(rA) Or bandwidth. Charge-ordering is found in layered manganates, BixCa1-xMnO3 and CaMnO3-delta.

Mott insulator high T-c bipolaronic superconductor transition in cuprates - Discussion

All ‘undoped’ cuprates are antiferromagnetic Mott insulators. We argue that with doping they remain to be insulators including the ‘overdoped’ samples. Hence, there is no clear dividing line between non–metallic cuprates and high–temperature superconductors. Based on the generic Hamiltonian including the electron–phonon interaction and the direct Coulomb repulsion the ground state of doped cuprates is shown to be a charged 2e Bose liquid of small bipolarons. A theory of the normal state transport of copper oxides is developed. The temperature dependence of the resistivity and of the Hall effect agrees remarkably well with the experimental data in La2–xSrxCuO4 for the entire temperature regime including unusual ‘logarithmic’ low–temperature region. The violation of Kohler's rule in magnetoresistivity is explained. The resistive and thermodynamic superconducting transitions in a magnetic field are quantitatively described.

Regular versus alternating (FeS4)(n) chains: Magnetism in KFeS2 and CsFeS2

We report crystal magnetic susceptibility results of two S = 1/2 one-dimensional Heisenberg antiferromagnets, KFeS2 and CsFeS2. Both compounds consist of (FeS4)(n) chains with an average Fe-Fe distance of 2.7 Angstrom. In KFeS2, all intrachain Fe-Fe distances are identical. Its magnetic susceptibility is typical of a regular antiferromagnetic chain with spin-spin exchange parameter J = -440.7 K. In CsFeS2, however, the Fe-Fe distances alternate between 2.61 and 2.82 Angstrom. This is reflected in its magnetic susceptibility, which could be fitted with J = -640 K, and the degree of alternation, alpha = 0.3. These compounds form a unique pair, and allow for a convenient experimental comparison of the magnetic properties of regular versus alternating Heisenberg chains.

Spin state and exchange in the quasi-one-dimensional antiferromagnet KFeS2

We report the optical spectra and single crystal magnetic susceptibility of the one-dimensional antiferromagnet KFeS2. Measurements have been carried out to ascertain the spin state of Fe3+ and the nature of the magnetic interactions in this compound. The optical spectra and magnetic susceptibility could be consistently interpreted using a S = 1/2 spin ground state for the Fe3+ ion. The features in the optical spectra have been assigned to transitions within the d-electron manifold of the Fe3+ ion, and analysed in the strong field limit of the ligand field theory. The high temperature isotropic magnetic susceptibility is typical of a low-dimensional system and exhibits a broad maximum at similar to 565 K. The susceptibility shows a well defined transition to a three dimensionally ordered antiferromagnetic state at T-N = 250 K. The intra and interchain exchange constants, J and J', have been evaluated from the experimental susceptibilities using the relationship between these quantities, and chi(max), T-max, and T-N for a spin 1/2 one-dimensional chain. The values are J = -440.71 K, and J' = 53.94 K. Using these values of J and J', the susceptibility of a spin 1/2 Heisenberg chain was calculated. A non-interacting spin wave model was used below T-N. The susceptibility in the paramagnetic region was calculated from the theoretical curves for an infinite S = 1/2 chain. The calculated susceptibility compares well with the experimental data of KFeS2. Further support for a one-dimensional spin 1/2 model comes from the fact that the calculated perpendicular susceptibility at 0K (2.75 x 10(-4) emu/mol) evaluated considering the zero point reduction in magnetization from spin wave theory is close to the projected value (2.7 x 10(-4) emu/mol) obtained from the experimental data.

The nature of charge ordering in rare earth manganates and its strong dependence on the size of the A-site cations

Charge ordering in rare earth manganates of the type Ln(0.5)A(0.5)MnO(3) (Ln = rare earth, A = alkaline earth) is highly sensitive to the average radius of the A-site cations, [r(A)]. Tn the small [r(A)] regime (e.g., Y0.5Ca0.5MnO3), charge ordering occurs in the paramagnetic state, the transformation to an antiferromagnetic state occurring at still lower temperatures. At moderate [r(A)] values (e.g., Nd0.5Sr0.5MnO3), a ferromagnetic metallic state transforms to a charge-ordered antiferromagnetic state with cooling. These two distinct types of charge ordering and associated properties are explained in terms of the variation of the exchange couplings J(FM) and J(AFM) with [r(A)] and the invariance of the single-ion Jahn-Teller energy with [r(A)]. A qualitative temperature-[r(A)] phase diagram, consistent with the experimental observations, has been constructed to describe the properties of the manganates in the different [r(A)] regimes. (C) 1997 Academic Press.