Generating Scale-free Networks with Adjustable Clustering Coefficient Via Random Walks

This paper presents an algorithm for generating scale-free networks with adjustable clustering coefficient. The algorithm is based on a random walk procedure combined with a triangle generation scheme which takes into account genetic factors; this way, preferential attachment and clustering control are implemented using only local information. Simulations are presented which support the validity of the scheme, characterizing its tuning capabilities.

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.

Empirical analysis of traffic volume for the application of the options theory to highway concessions

*************************************************************************************** EL WCTR es un Congreso de reconocido prestigio internacional en el ámbito de la investigación del transporte que hasta el 2010 publicaba sus libros de abstracts con ISBN. Por ello consideramos que debería seguir teníendose en cuenta para los indicadores de calidad ******************************************************************************************* Investment projects in the field of transportation infrastructures have a high degree of uncertainty and require an important amount of resources. In highway concessions in particular, the calculation of the Net Present Value (NPV) of the project by means of the discount of cash flows, may lead to erroneous results when the project incorporates certain flexibility. In these cases, the theory of real options is an alternative tool for the valuation of concessions. When the variable that generates uncertainty (in our case, the traffic) follows a random walk (or Geometric Brownian Motion), we can calculate the value of the options embedded in the contract starting directly from the process followed by that variable. This procedure notably simplifies the calculation method. In order to test the hypothesis of the evolution of traffic as a Geometric Brownian Motion, we have used the available series of traffic in Spanish highways, and we have applied the Augmented Dickey-Fuller approach, which is the most widely used test for this kind of study. The main result of the analysis is that we cannot reject the hypothesis that traffic follows a Geometric Brownian Motion in the majority of both toll highways and free highways in Spain.

Percolation in soils at Different Bulk Densities: Porosity, Connectivity and Grey Threshold.

To improve percolation modelling on soils the geometrical properties of the pore space must be understood; this includes porosity, particle and pore size distribution and connectivity of the pores. A study was conducted with a soil at different bulk densities based on 3D grey images acquired by X-ray computed tomography. The objective was to analyze the effect in percolation of aspects of pore network geometry and discuss the influence of the grey threshold applied to the images. A model based on random walk algorithms was applied to the images, combining five bulk densities with up to six threshold values per density. This allowed for a dynamical perspective of soil structure in relation to water transport through the inclusion of percolation speed in the analyses. To evaluate separately connectivity and isolate the effect of the grey threshold, a critical value of 35% of porosity was selected for every density. This value was the smallest at which total-percolation walks appeared for the all images of the same porosity and may represent a situation of percolation comparable among bulks densities. This criterion avoided an arbitrary decision in grey thresholds. Besides, a random matrix simulation at 35% of porosity with real images was used to test the existence of pore connectivity as a consequence of a non-random soil structure.

Topology of a percolating soil pore network.

A connectivity function defined by the 3D-Euler number, is a topological indicator and can be related to hydraulic properties (Vogel and Roth, 2001). This study aims to develop connectivity Euler indexes as indicators of the ability of soils for fluid percolation. The starting point was a 3D grey image acquired by X-ray computed tomography of a soil at bulk density of 1.2 mg cm-3. This image was used in the simulation of 40000 particles following a directed random walk algorithms with 7 binarization thresholds. These data consisted of 7 files containing the simulated end points of the 40000 random walks, obtained in Ruiz-Ramos et al. (2010). MATLAB software was used for computing the frequency matrix of the number of particles arriving at every end point of the random walks and their 3D representation.

Systematic analysis of direct-drive baseline designs for shock ignition with the Laser MégaJoule

We present direct-drive target design studies for the laser mégajoule using two distinct initial aspect ratios (A = 34 and A = 5). Laser pulse shapes are optimized by a random walk method and drive power variations are used to cover a wide variety of implosion velocities between 260 km/s and 365 km/s. For selected implosion velocities and for each initial aspect ratio, scaled-target families are built in order to find self-ignition threshold. High-gain shock ignition is also investigated in the context of Laser MégaJoule for marginally igniting targets below their own self-ignition threshold.

Modelos para el análisis dinámico y la predicción a corto plazo de los precios de la electricidad en mercados liberalizados

En esta tesis se va a describir y aplicar de forma novedosa la técnica del alisado exponencial multivariante a la predicción a corto plazo, a un día vista, de los precios horarios de la electricidad, un problema que se está estudiando intensivamente en la literatura estadística y económica reciente. Se van a demostrar ciertas propiedades interesantes del alisado exponencial multivariante que permiten reducir el número de parámetros para caracterizar la serie temporal y que al mismo tiempo permiten realizar un análisis dinámico factorial de la serie de precios horarios de la electricidad. En particular, este proceso multivariante de elevada dimensión se estimará descomponiéndolo en un número reducido de procesos univariantes independientes de alisado exponencial caracterizado cada uno por un solo parámetro de suavizado que variará entre cero (proceso de ruido blanco) y uno (paseo aleatorio). Para ello, se utilizará la formulación en el espacio de los estados para la estimación del modelo, ya que ello permite conectar esa secuencia de modelos univariantes más eficientes con el modelo multivariante. De manera novedosa, las relaciones entre los dos modelos se obtienen a partir de un simple tratamiento algebraico sin requerir la aplicación del filtro de Kalman. De este modo, se podrán analizar y poner al descubierto las razones últimas de la dinámica de precios de la electricidad. Por otra parte, la vertiente práctica de esta metodología se pondrá de manifiesto con su aplicación práctica a ciertos mercados eléctricos spot, tales como Omel, Powernext y Nord Pool. En los citados mercados se caracterizará la evolución de los precios horarios y se establecerán sus predicciones comparándolas con las de otras técnicas de predicción. ABSTRACT This thesis describes and applies the multivariate exponential smoothing technique to the day-ahead forecast of the hourly prices of electricity in a whole new way. This problem is being studied intensively in recent statistics and economics literature. It will start by demonstrating some interesting properties of the multivariate exponential smoothing that reduce drastically the number of parameters to characterize the time series and that at the same time allow a dynamic factor analysis of the hourly prices of electricity series. In particular this very complex multivariate process of dimension 24 will be estimated by decomposing a very reduced number of univariate independent of exponentially smoothing processes each characterized by a single smoothing parameter that varies between zero (white noise process) and one (random walk). To this end, the formulation is used in the state space model for the estimation, since this connects the sequence of efficient univariate models to the multivariate model. Through a novel way, relations between the two models are obtained from a simple algebraic treatment without applying the Kalman filter. Thus, we will analyze and expose the ultimate reasons for the dynamics of the electricity price. Moreover, the practical aspect of this methodology will be shown by applying this new technique to certain electricity spot markets such as Omel, Powernext and Nord Pool. In those markets the behavior of prices will be characterized, their predictions will be formulated and the results will be compared with those of other forecasting techniques.

Orthogonal MCMC algorithms

Monte Carlo (MC) methods are widely used in signal processing, machine learning and stochastic optimization. A well-known class of MC methods are Markov Chain Monte Carlo (MCMC) algorithms. In this work, we introduce a novel parallel interacting MCMC scheme, where the parallel chains share information using another MCMC technique working on the entire population of current states. These parallel ?vertical? chains are led by random-walk proposals, whereas the ?horizontal? MCMC uses a independent proposal, which can be easily adapted by making use of all the generated samples. Numerical results show the advantages of the proposed sampling scheme in terms of mean absolute error, as well as robustness w.r.t. to initial values and parameter choice.

Uniformly reweighted belief propagation for distributed Bayesian hypothesis testing

Belief propagation (BP) is a technique for distributed inference in wireless networks and is often used even when the underlying graphical model contains cycles. In this paper, we propose a uniformly reweighted BP scheme that reduces the impact of cycles by weighting messages by a constant ?edge appearance probability? rho ? 1. We apply this algorithm to distributed binary hypothesis testing problems (e.g., distributed detection) in wireless networks with Markov random field models. We demonstrate that in the considered setting the proposed method outperforms standard BP, while maintaining similar complexity. We then show that the optimal ? can be approximated as a simple function of the average node degree, and can hence be computed in a distributed fashion through a consensus algorithm.

Novel fast random search clustering approach for mixing matrix identification in MIMO linear blind inverse problems with sparse inputs

In this paper we propose a novel fast random search clustering (RSC) algorithm for mixing matrix identification in multiple input multiple output (MIMO) linear blind inverse problems with sparse inputs. The proposed approach is based on the clustering of the observations around the directions given by the columns of the mixing matrix that occurs typically for sparse inputs. Exploiting this fact, the RSC algorithm proceeds by parameterizing the mixing matrix using hyperspherical coordinates, randomly selecting candidate basis vectors (i.e. clustering directions) from the observations, and accepting or rejecting them according to a binary hypothesis test based on the Neyman–Pearson criterion. The RSC algorithm is not tailored to any specific distribution for the sources, can deal with an arbitrary number of inputs and outputs (thus solving the difficult under-determined problem), and is applicable to both instantaneous and convolutive mixtures. Extensive simulations for synthetic and real data with different number of inputs and outputs, data size, sparsity factors of the inputs and signal to noise ratios confirm the good performance of the proposed approach under moderate/high signal to noise ratios. RESUMEN. Método de separación ciega de fuentes para señales dispersas basado en la identificación de la matriz de mezcla mediante técnicas de "clustering" aleatorio.

Random positions of dendritic spines in human cerebral cortex

Dendritic spines establish most excitatory synapses in the brain and are located in Purkinje cell’s dendrites along helical paths, perhaps maximizing the probability to contact different axons. To test whether spine helixes also occur in neocortex, we reconstructed >500 dendritic segments from adult human cortex obtained from autopsies. With Fourier analysis and spatial statistics, we analyzed spine position along apical and basal dendrites of layer 3 pyramidal neurons from frontal, temporal, and cingulate cortex. Although we occasionally detected helical positioning, for the great majority of dendrites we could not reject the null hypothesis of spatial randomness in spine locations, either in apical or basal dendrites, in neurons of different cortical areas or among spines of different volumes and lengths. We conclude that in adult human neocortex spine positions are mostly random. We discuss the relevance of these results for spine formation and plasticity and their functional impact for cortical circuits.

Random positioning of dendritic spines in the human cerebral cortex

Dendritic spines establish most excitatory synapses in the brain and are located in Purkinje cell?s dendrites along helical paths, perhaps maximizing the probability to contact different axons. To test whether spine helixes also occur in neocortex, we reconstructed ?500 dendritic segments from adult human cortex obtained from autopsies. With Fourier analysis and spatial statistics, we analyzed spine position along apical and basal dendrites of layer 3 pyramidal neurons from frontal, temporal, and cingulate cortex. Although we occasionally detected helical positioning, for the great majority of dendrites we could not reject the null hypothesis of spatial randomness in spine locations, either in apical or basal dendrites, in neurons of different cortical areas or among spines of different volumes and lengths. We conclude that in adult human neocortex spine positions are mostly random. We discuss the relevance of these results for spine formation and plasticity and their functional impact for cortical circuits.