Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

Design of high-order filters with restricted component values

The feasibility of realising a high-order LC filter with a small set of different capacitor values, without sacrificing the frequency response specifications, is indicated. This idea could be conveniently adopted in other filter structures also—for example the FDNR transformed filter realisations.

Calorimetric values of composite solid propellants

The calorimetric values of composite solid propellant based on polystyrene, polyphenolformaldehyde, poly(vinyl chloride) and carboxy-terminated polybutadiene were determined using combustion calorimetry in order to assess the uncertainities in their measurements. The dependence of the calorimetric values on various propellant composition was obtained. The stoichiometry of oxidizer and fuel in the propellant for complete combustion obtained experimentally were compared with the theoretical stoichiometry calculated based on the oxidizer decomposition.

Precise Values of the "C Component Vicinal Coupling Constants for Calculating Side-Chain Conformations in Amino Acids

From consideration of 'H-lH vicinal coupling constants and '"G'H long-range coupling constants in a series of amino acid derivatives, the precise values of uC component vicinal coupling constants have been calculated for the three minimum energy staggered rotamers for the C(or)H-C(P)H, side-chains of amino acids.

New method of calculating calorific values from elemental compositions of fossil fuels

A new method of calculating the calorific values of fossil fuels from their chemical composition has been developed, based on the concept that heats of reaction of stoichiometric fuel-oxidizer systems are rectilinearly related with the total oxidizing or reducing valancies of the mixture. The calorific value of fossil fuels has been shown to be directly related to the net reducing valencies of the fuel. The proposed method is simple and compares favourably with the other prominent methods reported in the literature.

Absolute values of instantaneous corrosion rates by faradaic rectification

Doss and Agarwal 1 discovered the "redoxokinetic effect" which is now familiarly known as faradaic rectification. Subsequently, the theory and applications of faradaic rectification due to a single electrode reaction have been developed by several workers 2-5. The theory and application of faradaic rectification in the case of a corrosion cell sustaining mixed electrode reactions on a corroding metal was reported recently 6"7. This led to the development of a new electrochemical method of corrosion rate determination. It was shown that changes in the instantaneous corrosion rates of a metal are readily evaluated by faradaic rectification measurements at the corrosion potential of the metal in a given medium. The aim of the present work is to show that absolute values of instantaneous corrosion rates may also be obtained by the new method under certain conditions. The practical advantages that arise from this development are pointed out.

A Shapley value analysis to coordinate the formation of procurement

In this paper we address the problem of forming procurement networks for items with value adding stages that are linearly arranged. Formation of such procurement networks involves a bottom-up assembly of complex production, assembly, and exchange relationships through supplier selection and contracting decisions. Recent research in supply chain management has emphasized that such decisions need to take into account the fact that suppliers and buyers are intelligent and rational agents who act strategically. In this paper, we view the problem of Procurement Network Formation (PNF) for multiple units of a single item as a cooperative game where agents cooperate to form a surplus maximizing procurement network and then share the surplus in a fair manner. We study the implications of using the Shapley value as a solution concept for forming such procurement networks. We also present a protocol, based on the extensive form game realization of the Shapley value, for forming these networks.

The core and shapley value analysis for cooperative formation of procurement networks

Formation of high value procurement networks involves a bottom-up assembly of complex production, assembly, and exchange relationships through supplier selection and contracting decisions, where suppliers are intelligent and rational agents who act strategically. In this paper we address the problem of forming procurement networks for items with value adding stages that are linearly arranged We model the problem of Procurement Network Formation (PNF) for multiple units of a single item as a cooperative game where agents cooperate to form a surplus maximizing procurement network and then share the surplus in a stable and fair manner We first investigate the stability of such networks by examining the conditions under which the core of the game is non-empty. We then present a protocol, based on the extensive form game realization of the core, for forming such networks so that the resulting network is stable. We also mention a key result when the Shapley value is applied as a solution concept.

Temperature dependence of g values in tetragonal ionic Cu++ salts

A temperature dependence has been observed in the spin-Hamiltonian parameters of the Cu++ ion in a tetragonal crystal field and the variation has been interpreted in terms of vibronic effects.

Growth of ionization currents in dry air at high values of E/N

Uniform field steady-state ionization currents were measured in dry air as a function of N at constant E/N (E is the electric field strength and N the gas number density) and constant electrode separation d for 14·13 × 10-16 less-than-or-eq, slant E/N less-than-or-eq, slant 282·5 × 10-16 V cm2. Uniform field sparking potentials were also measured for Nd range 1·24 × 1016 less-than-or-eq, slant Nd less-than-or-eq, slant 245 × 1016 cm-2. The ratio of the Townsend primary ionization coefficient α to N, α/N, was found to depend on E/N only. The secondary coefficients were also evaluated for aluminium and gold-plated electrodes for the above range of E/N. Measurements of the sparking potentials showed that Paschen's law is not obeyed in air at values of Nd near and below the Paschen minimum.

Relationship between Low Strain Shear Modulus and Standard Penetration Test N Values

A low strain shear modulus plays a fundamental role in the estimation of site response parameters In this study an attempt has been made to develop the relationships between standard penetration test (SPT) N values with the low strain shear modulus (G(max)) For this purpose, field experiments SPT and multichannel analysis of surface wave data from 38 locations in Bangalore, India, have been used, which were also used for seismic microzonation project The in situ density of soil layer was evaluated using undisturbed soil samples from the boreholes Shear wave velocity (V-s) profiles with depth were obtained for the same locations or close to the boreholes The values for low strain shear modulus have been calculated using measured V-s and soil density About 215 pairs of SPT N and G(max) values are used for regression analysis The differences between fitted regression relations using measured and corrected values were analyzed It is found that an uncorrected value of N and modulus gives the best fit with a high regression coefficient when compared to corrected N and corrected modulus values This study shows better correlation between measured values of N and G(max) when compared to overburden stress corrected values of N and G(max)

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.

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 decidable temporal logic with repeating values

Various logical formalisms with the freeze quantifier have been recently considered to model computer systems even though this is a powerful mechanism that often leads to undecidability. In this paper, we study a linear-time temporal logic with past-time operators such that the freeze operator is only used to express that some value from an infinite set is repeated in the future or in the past. Such a restriction has been inspired by a recent work on spatio-temporal logics. We show decidability of finitary and infinitary satisfiability by reduction into the verification of temporal properties in Petri nets. This is a surprising result since the logic is closed under negation, contains future-time and past-time temporal operators and can express the nonce property and its negation. These ingredients are known to lead to undecidability with a more liberal use of the freeze quantifier.