The Cross-Entropy Method for Network Reliability Estimation

Consider a network of unreliable links, modelling for example a communication network. Estimating the reliability of the network—expressed as the probability that certain nodes in the network are connected—is a computationally difficult task. In this paper we study how the Cross-Entropy method can be used to obtain more efficient network reliability estimation procedures. Three techniques of estimation are considered: Crude Monte Carlo and the more sophisticated Permutation Monte Carlo and Merge Process. We show that the Cross-Entropy method yields a speed-up over all three techniques.     

To change or not to change: adapting mathematical knowledge for teaching (MKT) measures for use in Korea

This paper examines challenges in adapting mathematical knowledge for teaching (MKT) measures developed in the United States for use in Korea. After an initial analysis of candidate issues regarding the “fit” of items to the Korean context—whether items were familiar, authentic, and realistic as characterized by Delaney et al. (J Math Teach Educ 11:171–197, 2008)—we adapted and administered an instrument developed by the Learning Mathematics for Teaching project with 93 Korean teachers and conducted follow-up interviews with nine teachers. Based on analysis of this data, we conducted a second round of revision and then administered the revised test to 101 Korean teachers. Results showed that small modifications that were made to increase fit often increased teachers’ performance on the items as expected, but the impact of changes was at times difficult to interpret. For several items, modifications introduced unanticipated validity issues. The paper discusses dynamics that arise in making changes to MKT items—in particular, the tension in modifying items to increase the fit to specific educational contexts while maintaining validity.     

Symmetry Groupoids and Admissible Vector Fields for Coupled Cell Networks

The space of admissible vector fields, consistent with the structureof a network of coupled dynamical systems, can be specifiedin terms of the network's symmetry groupoid. The symmetry groupoidalso determines the robust patterns of synchrony in the network– those that arise because of the network topology. Inparticular, synchronous cells can be identified in a canonicalmanner to yield a quotient network. Admissible vector fieldson the original network induce admissible vector fields on thequotient, and any dynamical state of such an induced vectorfield can be lifted to the original network, yielding an analogousstate in which certain sets of cells are synchronized. In thepaper, necessary and sufficient conditions are specified forall admissible vector fields on the quotient to lift in thismanner. These conditions are combinatorial in nature, and theproof uses invariant theory for the symmetric group. Also thesymmetry groupoid of a quotient is related to that of the originalnetwork, and it is shown that there is a close analogy withthe usual normalizer symmetry that arises in group-equivariantdynamics.     

Arc refractor methods for adaptive importance sampling on large Bayesian networks under evidential reasoning

Approximate Bayesian inference by importance sampling derives probabilistic statements from a Bayesian network, an essential part of evidential reasoning with the network and an important aspect of many Bayesian methods. A critical problem in importance sampling on Bayesian networks is the selection of a good importance function to sample a network’s prior and posterior probability distribution. The initially optimal importance functions eventually start deviating from the optimal function when sampling a network’s posterior distribution given evidence, even when adaptive methods are used that adjust an importance function to the evidence by learning. In this article we propose a new family of Refractor Importance Sampling (RIS) algorithms for adaptive importance sampling under evidential reasoning. RIS applies “arc refractors” to a Bayesian network by adding new arcs and refining the conditional probability tables. The goal of RIS is to optimize the importance function for the posterior distribution and reduce the error variance of sampling. Our experimental results show a significant improvement of RIS over state-of-the-art adaptive importance sampling algorithms.     

On 2-stage robust LP with RHS uncertainty: complexity results and applications

We investigate here the class—denoted R-LP-RHSU—of two-stage robust linear programming problems with right-hand-side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with uncertain task durations); robust maximum flow (with uncertain arc capacities); robust network capacity expansion problems; robust inventory management; some robust production planning problems in the context of power production/distribution systems. It is shown that such problems can be formulated as large scale linear programs with associated nonconvex separation subproblem. A formal proof of strong NP-hardness for the general case is then provided, and polynomially solvable subclasses are exhibited. Differences with other previously described robust LP problems (featuring row-wise uncertainty instead of column wise uncertainty) are highlighted.     

Extreme inaccuracies in Gaussian Bayesian networks

To evaluate the impact of model inaccuracies over the network’s output, after the evidence propagation, in a Gaussian Bayesian network, a sensitivity measure is introduced. This sensitivity measure is the Kullback-Leibler divergence and yields different expressions depending on the type of parameter to be perturbed, i.e. on the inaccurate parameter.In this work, the behavior of this sensitivity measure is studied when model inaccuracies are extreme, i.e. when extreme perturbations of the parameters can exist. Moreover, the sensitivity measure is evaluated for extreme situations of dependence between the main variables of the network and its behavior with extreme inaccuracies. This analysis is performed to find the effect of extreme uncertainty about the initial parameters of the model in a Gaussian Bayesian network and about extreme values of evidence. These ideas and procedures are illustrated with an example.     

Goodness of Fit of Logistic Regression Models for Random Graphs

Logistic regression is a natural and simple tool to understand how covariates contribute to explain the topology of a binary network. Once the model is fitted, the practitioner is interested in the goodness of fit of the regression to check if the covariates are sufficient to explain the whole topology of the network and, if they are not, to analyze the residual structure. To address this problem, we introduce a generic model that combines logistic regression with a network-oriented residual term. This residual term takes the form of the graphon function of a W-graph. Using a variational Bayes framework, we infer the residual graphon by averaging over a series of blockwise constant functions. This approach allows us to define a generic goodness-of-fit criterion, which corresponds to the posterior probability for the residual graphon to be constant. Experiments on toy data are carried out to assess the accuracy of the procedure. Several networks from social sciences and ecology are studied to illustrate the proposed methodology. Supplementary material for this article is available online.     

Leaving us in tiers: can homophily be used to generate tiering effects?

Substantial evidence indicates that our social networks are divided into tiers in which people have a few very close social support group, a larger set of friends, and a much larger number of relatively distant acquaintances. Because homophily—the principle that like seeks like—has been suggested as a mechanism by which people interact, it may also provide a mechanism that generates such frequencies and distributions. However, our multi-agent simulation tool, Construct, suggests that a slight supplement to a knowledge homophily model—the inclusion of several highly salient personal facts that are infrequently shared—can more successfully lead to the tiering behavior often observed in human networks than a simplistic homophily model. Our findings imply that homophily on both general and personal facts is necessary in order to achieve realistic frequencies of interaction and distributions of interaction partners. Implications of the model are discussed, and recommendations are provided for simulation designers seeking to use homophily models to explain human interaction patterns.     

Function Spaces and Capacity Related to a Sublinear Expectation: Application to <Emphasis Type="Italic">G</Emphasis>-Brownian Motion Paths

In this paper we give some basic and important properties of several typical Banach spaces of functions of G-Brownian motion paths induced by a sublinear expectation—G-expectation. Many results can be also applied to more general situations. A generalized version of Kolmogorov’s criterion for continuous modification of a stochastic process is also obtained. The results can be applied in continuous time dynamic and coherent risk measures in finance, in particular for path-dependence risky positions under situations of volatility model uncertainty.     

The spectra of lamplighter groups and Cayley machines

We calculate the spectra and spectral measures associated to random walks on restricted wreath products G wr , with G a finite group, by calculating the Kesten—von Neumann—Serre spectral measures for the random walks on Schreier graphs of certain groups generated by automata. This generalises the work of Grigorchuk and Żuk on the lamplighter group. In the process we characterise when the usual spectral measure for a group generated by an automaton coincides with the Kesten—von Neumann—Serre spectral measure.     

The Theory of Multidimensional Persistence

Persistent homology captures the topology of a filtration—a one-parameter family of increasing spaces—in terms of a complete discrete invariant. This invariant is a multiset of intervals that denote the lifetimes of the topological entities within the filtration. In many applications of topology, we need to study a multifiltration: a family of spaces parameterized along multiple geometric dimensions. In this paper, we show that no similar complete discrete invariant exists for multidimensional persistence. Instead, we propose the rank invariant, a discrete invariant for the robust estimation of Betti numbers in a multifiltration, and prove its completeness in one dimension. The first author was partially supported by NSF under grant DMS-0354543. The second author was partially supported by DARPA under grant HR 0011-06-1-0038 and by ONR under grant N 00014-08-1-0908. Both authors were partially supported by DARPA under grant HR 0011-05-1-0007.     

A Loss function approach to identifying environmental exceedances

A frequent problem in environmental science is the prediction of extrema and exceedances. It is well known that Bayesian and empirical-Bayesian predictors based on integrated squared error loss (ISEL) tend to overshrink predictions of extrema toward the mean. In this paper, we consider a geostatistical extension of the weighted rank squared error loss function (WRSEL) of Wright et al. (2003), which we call the integrated weighted quantile squared error loss (IWQSEL), as the basis for prediction of exceedances and their spatial location. The loss function is based on an ordering of the underlying spatial process using a spatially averaged cumulative distribution function. We illustrate this methodology with a Bayesian analysis of surface-nitrogen concentrations in the Chesapeake Bay and compare the new IWQSEL predictor with a standard ISEL predictor. We also give a comparison to predicted extrema obtained from a “plug-in” goestatistical analysis. AMS 2000 Subject Classification Primary—62M30; Secondary—62H11     

Topology control in the mobile ad hoc networks in order to intensify energy conservation

Although studied for years, due to their dynamic nature, research in the field of mobile ad hoc networks (MANETs) has remained a vast area of interest. Since once distributed, there will be less to no plausibility of recharge, energy conservation has become one of the pressing concerns regarding this particular type of network. In fact, one of the main obligations of designers is to make efficient use of these scarce resources. There has been tremendous work done in different layers of protocol stack in order to intensify energy conservation. To date, numerous topology control algorithms have been proposed, however, only a few have used meta-heuristics such as genetic algorithms, neural networks and/or learning automata to overcome this issue. On the other hand, since nodes are mobile and thus in a different spatial position, as time varies, we can expect that by regulating time intervals between topology controls, one may prolong the network’s lifetime. The main initiative of this paper is to intensify energy conservation in a mobile ad hoc network by using weighted and learning automata based algorithms. The learning automata, regulates time intervals between which the topology controls are done. The represented learning automata based algorithm uses its learning ability to find appropriate time-intervals so that the nodes would regulate the energy needed in order to exchange the information to their neighbors, accordingly. Moreover, at first we have represented two weighted based algorithms which extend two prominent protocols, namely K-Neigh and LMST. Then these algorithms are combined with a learning based algorithm which regulates time intervals between which the topology controls are done. In comparison with approaches that are based on periodic topology controls, proposed approach shows enhanced results. On the other hand, considering the learning ability of the learning automata based algorithms, composition of the aforementioned algorithms has been proven to be enhanced, in the respect of energy consumed per data transmitted, over those compared with.     

Application of RBF neural network improved by peak density function in intelligent color matching of wood dyeing

According to the characteristics of wood dyeing, we propose a predictive model of pigment formula for wood dyeing based on Radial Basis Function (RBF) neural network. In practical application, however, it is found that the number of neurons in the hidden layer of RBF neural network is difficult to determine. In general, we need to test several times according to experience and prior knowledge, which is lack of a strict design procedure on theoretical basis. And we also don’t know whether the RBF neural network is convergent. This paper proposes a peak density function to determine the number of neurons in the hidden layer. In contrast to existing approaches, the centers and the widths of the radial basis function are initialized by extracting the features of samples. So the uncertainty caused by random number when initializing the training parameters and the topology of RBF neural network is eliminated. The average relative error of the original RBF neural network is 1.55% in 158 epochs. However, the average relative error of the RBF neural network which is improved by peak density function is only 0.62% in 50 epochs. Therefore, the convergence rate and approximation precision of the RBF neural network are improved significantly.     

Investment under ambiguity with the best and worst in mind

Recent literature on optimal investment has stressed the difference between the impact of risk and the impact of ambiguity—also called Knightian uncertainty—on investors’ decisions. In this paper, we show that a decision maker’s attitude towards ambiguity is similarly crucial for investment decisions. We capture the investor’s individual ambiguity attitude by applying α-MEU preferences to a standard investment problem. We show that the presence of ambiguity often leads to an increase in the subjective project value, and entrepreneurs are more eager to invest. Thereby, our investment model helps to explain differences in investment behavior in situations which are objectively identical.     

Social Network Discovery by Mining Spatio-Temporal Events

Knowing patterns of relationship in a social network is very useful for law enforcement agencies to investigate collaborations among criminals, for businesses to exploit relationships to sell products, or for individuals who wish to network with others. After all, it is not just what you know, but also whom you know, that matters. However, finding out who is related to whom on a large scale is a complex problem. Asking every single individual would be impractical, given the huge number of individuals and the changing dynamics of relationships. Recent advancement in technology has allowed more data about activities of individuals to be collected. Such data may be mined to reveal associations between these individuals. Specifically, we focus on data having space and time elements, such as logs of people's movement over various locations or of their Internet activities at various cyber locations. Reasoning that individuals who are frequently found together are likely to be associated with each other, we mine from the data instances where several actors co-occur in space and time, presumably due to an underlying interaction. We call these spatio-temporal co-occurrences events, which we use to establish relationships between pairs of individuals. In this paper, we propose a model for constructing a social network from events, and provide an algorithm that mines these events from the data. Experiments on a real-life data tracking people's accesses to cyber locations have also yielded encouraging results. Hady W. Lauw is a graduate student at the School of Computer Engineering, Nanyang Technological University, Singapore. His research interests include spatio-temporal data mining, social network discovery, and link analyisis. He has a BEng in computer engineering from Nanyang Technological University. Ee-Peng Lim is an Associate Professor with the School of Computer Engineering, Nanyang Technological University, Singapore. He received his PhD from the University of Minnesota, Minneapolis in 1994 and B.Sc. in Computer Science from National University of Singapore. Ee-Peng's research interests include information integration, data/text/web mining, digital libraries, and wireless intelligence. He is currently an Associate Editor of the ACM Transactions on Information Systems (TOIS), International Journal of Digital Libraries (IJDL) and International Journal of Data Warehousing and Mining (IJDWM). He was the Program Co-Chair of the ACM/IEEE Joint Conference on Digital Libraries (JCDL 2004), and Conference/Program Co-Chairs of International Conference on Asian Digital Libraries (ICADL 2004). He has also served in the program committee of numerous international conferences. Dr Lim is a Senior Member of IEEE and a Member of ACM. HweeHwa Pang received the B.Sc.—with first class honors—and M.S. degrees from the National University of Singapore in 1989 and 1991, respectively, and the PhD degree from the University of Wisconsin at Madison in 1994, all in Computer Science. He is currently an Associate Professor at the Singapore Management University. His research interests include database management systems, data security and quality, operating systems, and multimedia servers. He has many years of hands-on experience in system implementation and project management. He has also participated in transferring some of his research results to industry. Teck-Tim Tan is an IT Manager (Operations) at the Centre for IT Services, Nanyang Technological University (NTU), Singapore. He administers and oversees NTU's campus-wide wireless LAN infrastructure which facilitates access to the University's vast IT resources and services practically anywhere on campus.