Stretched-exponential behavior and random walks on diluted hypercubic lattices

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Discriminating Different Classes of Biological Networks by Analyzing the Graphs Spectra Distribution

The brain's structural and functional systems, protein-protein interaction, and gene networks are examples of biological systems that share some features of complex networks, such as highly connected nodes, modularity, and small-world topology. Recent studies indicate that some pathologies present topological network alterations relative to norms seen in the general population. Therefore, methods to discriminate the processes that generate the different classes of networks (e. g., normal and disease) might be crucial for the diagnosis, prognosis, and treatment of the disease. It is known that several topological properties of a network (graph) can be described by the distribution of the spectrum of its adjacency matrix. Moreover, large networks generated by the same random process have the same spectrum distribution, allowing us to use it as a "fingerprint". Based on this relationship, we introduce and propose the entropy of a graph spectrum to measure the "uncertainty" of a random graph and the Kullback-Leibler and Jensen-Shannon divergences between graph spectra to compare networks. We also introduce general methods for model selection and network model parameter estimation, as well as a statistical procedure to test the nullity of divergence between two classes of complex networks. Finally, we demonstrate the usefulness of the proposed methods by applying them to (1) protein-protein interaction networks of different species and (2) on networks derived from children diagnosed with Attention Deficit Hyperactivity Disorder (ADHD) and typically developing children. We conclude that scale-free networks best describe all the protein-protein interactions. Also, we show that our proposed measures succeeded in the identification of topological changes in the network while other commonly used measures (number of edges, clustering coefficient, average path length) failed.

Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree ?. We use the Lovasz local lemma to show the following two results about colourings ? of the edges of the complete graph Kn. If for each vertex v of Kn the colouring ? assigns each colour to at most (n - 2)/(22.4?2) edges emanating from v, then there is a copy of G in Kn which is properly edge-coloured by ?. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409433, 2003]. On the other hand, if ? assigns each colour to at most n/(51?2) edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from ?. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Szekely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernandez, Procacci, and Scoppola [preprint, arXiv:0910.1824]. (c) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425436, 2012

Analysis of competitiveness in the NBA regular seasons

[EN] Research background and hypothesis. Several attempts have been made to understand some modalities of sport from the point of view of complexity. Most of these studies deal with this phenomenon with regard to the mechanics of the game itself (in isolation). Nevertheless, some research has been conducted from the perspective of competition between teams. Our hypothesis was that for the study of competitiveness levels in the system of league competition our analysis model (Shannon entropy), is a useful and highly sensitive tool to determine the degree of global competitiveness of a league. Research aim. The aim of our study was to develop a model for the analysis of competitiveness level in team sport competitions based on the uncertainty level that might exist for each confrontation. Research methods. Degree of uncertainty or randomness of the competition was analyzed as a factor of competitiveness. It was calculated on the basis of the Shannon entropy. Research results. We studied 17 NBA regular seasons, which showed a fairly steady entropic tendency. There were seasons less competitive (? 0.9800) than the overall average (0.9835), and periods where the competitiveness remained at higher levels (range: 0.9851 to 0.9902). Discussion and conclusions. A league is more competitive when it is more random. Thus, it is harder to predict the fi nal outcome. However, when the competition is less random, the degree of competitiveness will decrease signifi cantly. The NBA is a very competitive league, there is a high degree of uncertainty of knowing the fi nal result.

Statistical Mechanics of Monomer-Dimer Models on Complete and Erdös-Rényi Graphs

Nella tesi sono trattate due famiglie di modelli meccanico statistici su vari grafi: i modelli di spin ferromagnetici (o di Ising) e i modelli di monomero-dimero. Il primo capitolo è dedicato principalmente allo studio del lavoro di Dembo e Montanari, in cui viene risolto il modello di Ising su grafi aleatori. Nel secondo capitolo vengono studiati i modelli di monomero-dimero, a partire dal lavoro di Heilemann e Lieb,con l'intento di dare contributi nuovi alla teoria. I principali temi trattati sono disuguaglianze di correlazione, soluzioni esatte su alcuni grafi ad albero e sul grafo completo, la concentrazione dell'energia libera intorno al proprio valor medio sul grafo aleatorio diluito di Erdös-Rényi.

Impact of random and systematic recall errors and selection bias in case--control studies on mobile phone use and brain tumors in adolescents (CEFALO study)

Whether the use of mobile phones is a risk factor for brain tumors in adolescents is currently being studied. Case--control studies investigating this possible relationship are prone to recall error and selection bias. We assessed the potential impact of random and systematic recall error and selection bias on odds ratios (ORs) by performing simulations based on real data from an ongoing case--control study of mobile phones and brain tumor risk in children and adolescents (CEFALO study). Simulations were conducted for two mobile phone exposure categories: regular and heavy use. Our choice of levels of recall error was guided by a validation study that compared objective network operator data with the self-reported amount of mobile phone use in CEFALO. In our validation study, cases overestimated their number of calls by 9% on average and controls by 34%. Cases also overestimated their duration of calls by 52% on average and controls by 163%. The participation rates in CEFALO were 83% for cases and 71% for controls. In a variety of scenarios, the combined impact of recall error and selection bias on the estimated ORs was complex. These simulations are useful for the interpretation of previous case-control studies on brain tumor and mobile phone use in adults as well as for the interpretation of future studies on adolescents.

Pattern and process: competition causes regular spacing of individuals within plant populations

1 We used simulated and experimental plant populations to analyse mortality-driven pattern formation under size-dependent competition. Larger plants had an advantage under size-asymmetric but not under symmetric competition. Initial patterns were random or clumped. 2 The simulations were individual-based and spatially explicit. Size-dependent competition was modelled with different rules to partition overlapping zones of influence. 3 The experiment used genotypes of Arabidopsis thaliana with different morphological plasticity and hence size-dependent competition. Compared with wild types, transgenic individuals over-expressed phytochrome A and had decreased plasticity because of disabled phytochrome-mediated shade avoidance. Therefore, competition among transgenics was more asymmetric compared with wild-types. 4 Density-dependent mortality under symmetric competition did not substantially change the initial spatial pattern. Conversely, simulations under asymmetric competition and experimental patterns of transgenic over-expressors showed patterns of survivors that deviated substantially from random mortality independent of initial patterns. 5 Small-scale initial patterns of wild types were regular rather than random or clumped. We hypothesize that this small-scale regularity may be explained by early shade avoidance of seedlings in their cotyledon stage. 6 Our experimental results support predictions from an individual-based simulation model and support the conclusion that regular spatial patterns of surviving individuals should be interpreted as evidence for strong, asymmetric competitive interactions and subsequent density-dependent mortality.

Brief Announcement: Node Sampling Using Centrifugal Random Walks.

We propose distributed algorithms for sampling networks based on a new class of random walks that we call Centrifugal Random Walks (CRW). A CRW is a random walk that starts at a source and always moves away from it. We propose CRW algorithms for connected networks with arbitrary probability distributions, and for grids and networks with regular concentric connectivity with distance based distributions. All CRW sampling algorithms select a node with the exact probability distribution, do not need warm-up, and end in a number of hops bounded by the network diameter.

Node sampling using random centrifugal walks

Sampling a network with a given probability distribution has been identified as a useful operation. In this paper we propose distributed algorithms for sampling networks, so that nodes are selected by a special node, called the source, with a given probability distribution. All these algorithms are based on a new class of random walks, that we call Random Centrifugal Walks (RCW). A RCW is a random walk that starts at the source and always moves away from it. Firstly, an algorithm to sample any connected network using RCW is proposed. The algorithm assumes that each node has a weight, so that the sampling process must select a node with a probability proportional to its weight. This algorithm requires a preprocessing phase before the sampling of nodes. In particular, a minimum diameter spanning tree (MDST) is created in the network, and then nodes weights are efficiently aggregated using the tree. The good news are that the preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. After that, every sample is done with a RCW whose length is bounded by the network diameter. Secondly, RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. The key features of the RCW algorithms (unlike previous Markovian approaches) are that (1) they do not need to warm-up (stabilize), (2) the sampling always finishes in a number of hops bounded by the network diameter, and (3) it selects a node with the exact probability distribution.

Constellations and the unsupervised learning of graphs

In this paper, we propose a novel method for the unsupervised clustering of graphs in the context of the constellation approach to object recognition. Such method is an EM central clustering algorithm which builds prototypical graphs on the basis of fast matching with graph transformations. Our experiments, both with random graphs and in realistic situations (visual localization), show that our prototypes improve the set median graphs and also the prototypes derived from our previous incremental method. We also discuss how the method scales with a growing number of images.

Random exams using Sweave

The adaptation of the Spanish University to the European Higher Education Area (EEES in Spanish) demands the integration of new tools and skills that would make the teaching- learning process easier. This adaptation involves a change in the evaluation methods, which goes from a system where the student was evaluated with a final exam, to a new system where we include a continuous evaluation in which the final exam may represent at most 50% in the vast majority of the Universities. Devising a new and fair continuous evaluation system is not an easy task to do. That would mean a student’s’ learning process follow-up by the teachers, and as a consequence an additional workload on existing staff resources. Traditionally, the continuous evaluation is associated with the daily work of the student and a collection of the different marks partly or entirely based on the work they do during the academic year. Now, small groups of students and an attendance control are important aspects to take into account in order to get an adequate assessment of the students. However, most of the university degrees have groups with more than 70 students, and the attendance control is a complicated task to perform, mostly because it consumes significant amounts of staff time. Another problem found is that the attendance control would encourage not-interested students to be present at class, which might cause some troubles to their classmates. After a two year experience in the development of a continuous assessment in Statistics subjects in Social Science degrees, we think that individual and periodical tasks are the best way to assess results. These tasks or examinations must be done in classroom during regular lessons, so we need an efficient system to put together different and personal questions in order to prevent students from cheating. In this paper we provide an efficient and effective way to elaborate random examination papers by using Sweave, a tool that generates data, graphics and statistical calculus from the software R and shows results in PDF documents created by Latex. In this way, we will be able to design an exam template which could be compiled in order to generate as many PDF documents as it is required, and at the same time, solutions are provided to easily correct them.

Inclusive education in Spain: how do skills, resources, and supports affect regular education teachers’ perceptions of inclusion?

This study examined regular education teachers’ perceptions of inclusion in elementary and secondary schools in Spain and how these perceptions may differ depending on teaching experience, skills, and the availability of resources and supports. Stratified random sampling procedures were used to draw a representative sample of 336 general education teachers (68 kindergarten, 133 elementary, and 135 secondary teachers) from the province of Alicante. The results indicated the acceptance of the principles of inclusion, although teacher skills, time, material resources, and personal supports for inclusion were deemed insufficient. Kindergarten and elementary teachers showed more positive perceptions of inclusion than secondary education teachers, and so did teachers with more personal supports and material resources than those with less supports and resources. The results are discussed in terms of its implications for practice in order to promote more inclusive classrooms in Spain.

Random recursion

Thesis (Ph.D.)--University of Washington, 2016-06

Random graph coloring:Statistical physics approach

The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the two-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges. ©2002 The American Physical Society.

Properties of sparse random matrices over finite fields

Typical properties of sparse random matrices over finite (Galois) fields are studied, in the limit of large matrices, using techniques from the physics of disordered systems. For the case of a finite field GF(q) with prime order q, we present results for the average kernel dimension, average dimension of the eigenvector spaces and the distribution of the eigenvalues. The number of matrices for a given distribution of entries is also calculated for the general case. The significance of these results to error-correcting codes and random graphs is also discussed.