Search results for "Random graph"
showing 10 items of 28 documents
Spatial Search by Quantum Walk is Optimal for Almost all Graphs.
2015
The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erd\"os-Renyi random graphs, i.e.\ graphs of $n$ vertices where each edge exists with probability $p$, search by CTQW is \textit{almost surely} optimal as long as $p\geq \log^{3/2}(n)/n$. Consequently, we show that quantum spatial search is in fact optimal for \emph{almost all} graphs, meaning that the fraction of graphs of $n$ vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by provin…
Homogeneous actions on the random graph
2018
We show that any free product of two countable groups, one of them being infinite, admits a faithful and homogeneous action on the Random Graph. We also show that a large class of HNN extensions or free products, amalgamated over a finite group, admit such an action and we extend our results to groups acting on trees. Finally, we show the ubiquity of finitely generated free dense subgroups of the automorphism group of the Random Graph whose action on it have all orbits infinite.
From time series to complex networks: the visibility graph
2008
In this work we present a simple and fast computational method, the visibility algorithm , that converts a time series into a graph. The constructed graph inherits several properties of the series in its structure. Thereby, periodic series convert into regular graphs, and random series do so into random graphs. Moreover, fractal series convert into scale-free networks, enhancing the fact that power law degree distributions are related to fractality, something highly discussed recently. Some remarkable examples and analytical tools are outlined to test the method's reliability. Many different measures, recently developed in the complex network theory, could by means of this new approach cha…
Information Functionals and the Notion of (Un)Certainty: Random Matrix Theory - Inspired Case
2007
Information functionals allow one to quantify the degree of randomness of a given probability distribution, either absolutely (through min/max entropy principles) or relative to a prescribed reference one. Our primary aim is to analyze the “minimum information” assumption, which is a classic concept (R. Balian, 1968) in the random matrix theory. We put special emphasis on generic level (eigenvalue) spacing distributions and the degree of their randomness, or alternatively — information/organization deficit.
Growth, percolation, and correlations in disordered fiber networks
1997
This paper studies growth, percolation, and correlations in disordered fiber networks. We start by introducing a 2D continuum deposition model with effective fiber-fiber interactions represented by a parameter $p$ which controls the degree of clustering. For $p=1$, the deposited network is uniformly random, while for $p=0$ only a single connected cluster can grow. For $p=0$, we first derive the growth law for the average size of the cluster as well as a formula for its mass density profile. For $p>0$, we carry out extensive simulations on fibers, and also needles and disks to study the dependence of the percolation threshold on $p$. We also derive a mean-field theory for the threshold ne…
Spatial graphs and Convolutive Models
2020
In the last two decades, many complex systems have benefited from the use of graph theory, and these approaches have shown robust applicability in the field of finance, computer circuits and in biological systems. Large scale models of brain systems make also a great use of random graph models. Graph theory can be instrumental in modeling the connectivity and spatial distribution of neurons, through a characterization of the relative topological properties. However, all approaches in studying brain function have been so far limited to use experimental constraints obtained at a macroscopic level (e.g. fMRI, EEG, MEG, DTI, DSI). In this contribution, we present a microscopic use (i.e. at the …
Joint Topology and Radio Resource Optimization for Device-to-Device Based Mobile Social Networks
2018
In this paper, we consider a joint topology and radio resource optimization for device-to-device (D2D) based mobile social networks. The considered social network is an interest based which is modeled as a d -intersection binomial random graph. The Radio network is also modeled as a random graph where an edge between any two distinct nodes is activated with a certain probability that is equivalent to the probability of exceeding a certain signal to interference ratio for that link. The entire network is then modeled as an intersection graph between the social and radio induced graphs. Thereafter, network topology is optimized such that enabled social edges satisfy certain network connectivi…
Maintaining Dynamic Minimum Spanning Trees: An Experimental Study
2010
AbstractWe report our findings on an extensive empirical study on the performance of several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested several variants of the polylogarithmic algorithm by Holm et al., sparsification on top of Frederickson’s algorithm, and other (less sophisticated) dynamic algorithms. In our experiments, we considered as test sets several random, semi-random and worst-case inputs previously considered in the literature together with inputs arising from real-world applications (e.g., a graph of the Internet Autonomous Systems).
A Hebbian approach to complex-network generation
2011
Through a redefinition of patterns in an Hopfield-like model, we introduce and develop an approach to model discrete systems made up of many, interacting components with inner degrees of freedom. Our approach clarifies the intrinsic connection between the kind of interactions among components and the emergent topology describing the system itself; also, it allows to effectively address the statistical mechanics on the resulting networks. Indeed, a wide class of analytically treatable, weighted random graphs with a tunable level of correlation can be recovered and controlled. We especially focus on the case of imitative couplings among components endowed with similar patterns (i.e. attribute…
Comparative Evaluation of Community Detection Algorithms: A Topological Approach
2012
International audience; Community detection is one of the most active fields in complex networks analysis, due to its potential value in practical applications. Many works inspired by different paradigms are devoted to the development of algorithmic solutions allowing to reveal the network structure in such cohesive subgroups. Comparative studies reported in the literature usually rely on a performance measure considering the community structure as a partition (Rand Index, Normalized Mutual information, etc.). However, this type of comparison neglects the topological properties of the communities. In this article, we present a comprehensive comparative study of a representative set of commu…