Relevant bibliographies by topics / Random graph generation

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Random graph generation'

Author: Grafiati
Published: 4 June 2021
Last updated: 6 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Random graph generation.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Random graph generation"

1

Vizi, Máté Benjámin, Péter Árpád Mizsák, and Tamás Kalmár-Nagy. "Saturation in Regular, Exotic and Random Pore Networks." Fluctuation and Noise Letters 17, no. 03 (September 2018): 1850024. http://dx.doi.org/10.1142/s0219477518500244.

Full text
Abstract:
Porcolation simulations were carried out on various networks: both regular and irregular. The saturation curve was obtained for cubic networks, localized and completely random 3D networks and networks based on exotic graphs like Sierpiński triangle and carpet. For the random graph generation, a modification of the cell list algorithm was introduced, which is capable of generating local random graphs efficiently. With the help of this graph generation method, the effect of locality was investigated, and it was proven to be an important property of random networks from the viewpoint of liquid propagation. The saturation curves of local random networks with different prescribed pore degree distributions were also obtained.
APA, Harvard, Vancouver, ISO, and other styles
2

Wagaman, Amy. "Graph construction and random graph generation for modeling protein structures." Statistical Analysis and Data Mining 6, no. 6 (August 26, 2013): 482–95. http://dx.doi.org/10.1002/sam.11203.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Sun, Wenbo, and Ivona Bezáková. "Sampling Random Chordal Graphs by MCMC (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 10 (April 3, 2020): 13929–30. http://dx.doi.org/10.1609/aaai.v34i10.7237.

Full text
Abstract:
Chordal graphs are a widely studied graph class, with applications in several areas of computer science, including structural learning of Bayesian networks. Many problems that are hard on general graphs become solvable on chordal graphs. The random generation of instances of chordal graphs for testing these algorithms is often required. Nevertheless, there are only few known algorithms that generate random chordal graphs, and, as far as we know, none of them generate chordal graphs uniformly at random (where each chordal graph appears with equal probability). In this paper we propose a Markov chain Monte Carlo (MCMC) method to sample connected chordal graphs uniformly at random. Additionally, we propose a Markov chain that generates connected chordal graphs with a bounded treewidth uniformly at random. Bounding the treewidth parameter (which bounds the largest clique) has direct implications on the running time of various algorithms on chordal graphs. For each of the proposed Markov chains we prove that they are ergodic and therefore converge to the uniform distribution. Finally, as initial evidence that the Markov chains have the potential to mix rapidly, we prove that the chain on graphs with bounded treewidth mixes rapidly for trees (chordal graphs with treewidth bound of one).
APA, Harvard, Vancouver, ISO, and other styles
4

Abidin, Zainal, and Agus Zainal Arifin. "Membatasi k-Ketenggaan Simpul dalam Pembangkitan Random Graph Metode Erdos Royi untuk Meningkatkan Kinerja Komputasi." CAUCHY 1, no. 2 (May 15, 2010): 97. http://dx.doi.org/10.18860/ca.v1i2.1706.

Full text
Abstract:
Edges generation by random graph erdos-royi methods was needed high computation, it’s caused low performance. In fact, edge generation was used frequently with many nodes. this paper is described a node restriction by k-nearest neighbour on edge generation of random graph erdos royi method. Result of node<br />restriction by k-nearest neighbour can be reduced computation time.
APA, Harvard, Vancouver, ISO, and other styles
5

Allen, Thomas E., Judy Goldsmith, Hayden Elizabeth Justice, Nicholas Mattei, and Kayla Raines. "Uniform Random Generation and Dominance Testing for CP-Nets." Journal of Artificial Intelligence Research 59 (August 29, 2017): 771–813. http://dx.doi.org/10.1613/jair.5455.

Full text
Abstract:
The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o and o', of a minimal proof that o is preferred to o'. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.
APA, Harvard, Vancouver, ISO, and other styles
6

Basuli, Krishnendu, and Saptershi Naskar. "Generation of a random simple graph and its graphical presentation." Ubiquity 2008, March (March 2008): 1–4. http://dx.doi.org/10.1145/1366313.1361266.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

BOROVIK, ALEXANDRE V., EVGENII I. KHUKHRO, and ALEXEI G. MYASNIKOV. "THE ANDREWS–CURTIS CONJECTURE AND BLACK BOX GROUPS." International Journal of Algebra and Computation 13, no. 04 (August 2003): 415–36. http://dx.doi.org/10.1142/s0218196703001468.

Full text
Abstract:
The paper discusses the Andrews–Curtis graph Δk(G,N) of a normal subgroup N in a group G. The vertices of the graph are k-tuples of elements in N which generate N as a normal subgroup; two vertices are connected if one of them can be obtained from another by certain elementary transformations. This object appears naturally in the theory of black box finite groups and in the Andrews–Curtis conjecture in algebraic topology [3]. We suggest an approach to the Andrews–Curtis conjecture based on the study of Andrews–Curtis graphs of finite groups, discuss properties of Andrews–Curtis graphs of some classes of finite groups and results of computer experiments with generation of random elements of finite groups by random walks on their Andrews–Curtis graphs.
APA, Harvard, Vancouver, ISO, and other styles
8

Morris, James F., Jerome W. O’Neal, and Richard F. Deckro. "A random graph generation algorithm for the analysis of social networks." Journal of Defense Modeling and Simulation: Applications, Methodology, Technology 11, no. 3 (June 11, 2013): 265–76. http://dx.doi.org/10.1177/1548512912450370.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Daskin, Anmer, Ananth Grama, and Sabre Kais. "Quantum random state generation with predefined entanglement constraint." International Journal of Quantum Information 12, no. 05 (August 2014): 1450030. http://dx.doi.org/10.1142/s0219749914500300.

Full text
Abstract:
Entanglement plays an important role in quantum communication, algorithms, and error correction. Schmidt coefficients are correlated to the eigenvalues of the reduced density matrix. These eigenvalues are used in von Neumann entropy to quantify the amount of the bipartite entanglement. In this paper, we map the Schmidt basis and the associated coefficients to quantum circuits to generate random quantum states. We also show that it is possible to adjust the entanglement between subsystems by changing the quantum gates corresponding to the Schmidt coefficients. In this manner, random quantum states with predefined bipartite entanglement amounts can be generated using random Schmidt basis. This provides a technique for generating equivalent quantum states for given weighted graph states, which are very useful in the study of entanglement, quantum computing, and quantum error correction.
APA, Harvard, Vancouver, ISO, and other styles
10

Bressan, Stéphane, Alfredo Cuzzocrea, Panagiotis Karras, Xuesong Lu, and Sadegh Heyrani Nobari. "An effective and efficient parallel approach for random graph generation over GPUs." Journal of Parallel and Distributed Computing 73, no. 3 (March 2013): 303–16. http://dx.doi.org/10.1016/j.jpdc.2012.09.010.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Random graph generation"

1

Parikh, Nidhi Kiranbhai. "Generating Random Graphs with Tunable Clustering Coefficient." Thesis, Virginia Tech, 2011. http://hdl.handle.net/10919/31591.

Full text
Abstract:
Most real-world networks exhibit a high clustering coefficientâ the probability that two neighbors of a node are also neighbors of each other. We propose four algorithms CONF-1, CONF-2, THROW-1, and THROW-2 which are based on the configuration model and that take triangle degree sequence (representing the number of triangles/corners at a node) and single-edge degree sequence (representing the number of single-edges/stubs at a node) as input and generate a random graph with a tunable clustering coefficient. We analyze them theoretically and empirically for the case of a regular graph. CONF-1 and CONF-2 generate a random graph with the degree sequence and the clustering coefficient anticipated from the input triangle and single-edge degree sequences. At each time step, CONF-1 chooses each node for creating triangles or single edges with the same probability, while CONF-2 chooses a node for creating triangles or single edge with a probability proportional to their number of unconnected corners or unconnected stubs, respectively. Experimental results match quite well with the anticipated clustering coefficient except for highly dense graphs, in which case the experimental clustering coefficient is higher than the anticipated value. THROW-2 chooses three distinct nodes for creating triangles and two distinct nodes for creating single edges, while they need not be distinct for THROW-1. For THROW-1 and THROW-2, the degree sequence and the clustering coefficient of the generated graph varies from the input. However, the expected degree distribution, and the clustering coefficient of the generated graph can also be predicted using analytical results. Experiments show that, for THROW-1 and THROW-2, the results match quite well with the analytical results. Typically, only information about degree sequence or degree distribution is available. We also propose an algorithm DEG that takes degree sequence and clustering coefficient as input and generates a graph with the same properties. Experiments show results for DEG that are quite similar to those for CONF-1 and CONF-2.
Master of Science
APA, Harvard, Vancouver, ISO, and other styles
2

Perarnau, Swann. "Environnements pour l'analyse expérimentale d'applications de calcul haute performance." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00650047.

Full text
Abstract:
Les machines du domaine du calcul haute performance (HPC) gagnent régulièrement en com- plexité. De nos jours, chaque nœud de calcul peut être constitué de plusieurs puces ou de plusieurs cœurs se partageant divers caches mémoire de façon hiérarchique. Que se soit pour comprendre les performances ob- tenues par une application sur ces architectures ou pour développer de nouveaux algorithmes et valider leur performance, une phase d'expérimentation est souvent nécessaire. Dans cette thèse, nous nous intéressons à deux formes d'analyse expérimentale : l'exécution sur machines réelles et la simulation d'algorithmes sur des jeux de données aléatoires. Dans un cas comme dans l'autre, le contrôle des paramètres de l'environnement (matériel ou données en entrée) permet une meilleure analyse des performances de l'application étudiée. Ainsi, nous proposons deux méthodes pour contrôler l'utilisation par une application des ressources ma- térielles d'une machine : l'une pour le temps processeur alloué et l'autre pour la quantité de cache mémoire disponible. Ces deux méthodes nous permettent notamment d'étudier les changements de comportement d'une application en fonction de la quantité de ressources allouées. Basées sur une modification du compor- tement du système d'exploitation, nous avons implémenté ces méthodes pour un système Linux et démontré leur utilité dans l'analyse de plusieurs applications parallèles. Du point de vue de la simulation, nous avons étudié le problème de la génération aléatoire de graphes orientés acycliques (DAG) pour la simulation d'algorithmes d'ordonnancement. Bien qu'un grand nombre d'algorithmes de génération existent dans ce domaine, la plupart des publications repose sur des implémen- tations ad-hoc et peu validées de ces derniers. Pour pallier ce problème, nous proposons un environnement de génération comprenant la majorité des méthodes rencontrées dans la littérature. Pour valider cet envi- ronnement, nous avons réalisé de grande campagnes d'analyses à l'aide de Grid'5000, notamment du point de vue des propriétés statistiques connues de certaines méthodes. Nous montrons aussi que la performance d'un algorithme est fortement influencée par la méthode de génération des entrées choisie, au point de ren- contrer des phénomènes d'inversion : un changement d'algorithme de génération inverse le résultat d'une comparaison entre deux ordonnanceurs.
APA, Harvard, Vancouver, ISO, and other styles
3

Penschuck, Manuel [Verfasser], Ulrich [Akademischer Betreuer] Meyer, Ulrich [Gutachter] Meyer, Peter [Gutachter] Sanders, and Georg [Gutachter] Schnitger. "Scalable generation of random graphs / Manuel Penschuck ; Gutachter: Ulrich Meyer, Peter Sanders, Georg Schnitger ; Betreuer: Ulrich Meyer." Frankfurt am Main : Universitätsbibliothek Johann Christian Senckenberg, 2021. http://d-nb.info/1239730012/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bhuiyan, Md Hasanuzzaman. "Parallel Algorithms for Switching Edges and Generating Random Graphs from Given Degree Sequences using HPC Platforms." Diss., Virginia Tech, 2017. http://hdl.handle.net/10919/80299.

Full text
Abstract:
Networks (or graphs) are an effective abstraction for representing many real-world complex systems. Analyzing various structural properties of and dynamics on such networks reveal valuable insights about the behavior of such systems. In today's data-rich world, we are deluged by the massive amount of heterogeneous data from various sources, such as the web, infrastructure, and online social media. Analyzing this huge amount of data may take a prohibitively long time and even may not fit into the main memory of a single processing unit, thus motivating the necessity of efficient parallel algorithms in various high-performance computing (HPC) platforms. In this dissertation, we present distributed and shared memory parallel algorithms for some important network analytic problems. First, we present distributed memory parallel algorithms for switching edges in a network. Edge switch is an operation on a network, where two edges are selected randomly, and one of their end vertices are swapped with each other. This operation is repeated either a given number of times or until a specified criterion is satisfied. It has diverse real-world applications such as in generating simple random networks with a given degree sequence and in modeling and studying various dynamic networks. One of the steps in our edge switch algorithm requires generating multinomial random variables in parallel. We also present the first non-trivial parallel algorithm for generating multinomial random variables. Next, we present efficient algorithms for assortative edge switch in a labeled network. Assuming each vertex has a label, an assortative edge switch operation imposes an extra constraint, i.e., two edges are randomly selected and one of their end vertices are swapped with each other if the labels of the end vertices of the edges remain the same as before. It can be used to study the effect of the network structural properties on dynamics over a network. Although the problem of assortative edge switch seems to be similar to that of (regular) edge switch, the constraint on the vertex labels in assortative edge switch leads to a new difficulty, which needs to be addressed by an entirely new algorithmic approach. We first present a novel sequential algorithm for assortative edge switch; then we present an efficient distributed memory parallel algorithm based on our sequential algorithm. Finally, we present efficient shared memory parallel algorithms for generating random networks with exact given degree sequence using a direct graph construction method, which involves computing a candidate list for creating an edge incident on a vertex using the Erdos-Gallai characterization and then randomly creating the edges from the candidates.
Ph. D.
APA, Harvard, Vancouver, ISO, and other styles
5

Duvignau, Romaric. "Maintenance et simulation de graphes aléatoires dynamiques." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0177/document.

Full text
Abstract:
Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit
We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way
APA, Harvard, Vancouver, ISO, and other styles
6

Lesparre, Youen. "Evaluation de l'affectation des tâches sur une architecture à mémoire distribuée pour des modèles flot de données." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066086/document.

Full text
Abstract:
Avec l'augmentation de l'utilisation des smartphones, des objets connectés et des véhicules automatiques, le domaine des systèmes embarqués est devenu omniprésent dans notre environnement. Ces systèmes sont souvent contraints en terme de consommation et de taille. L'utilisation des processeurs many-cores dans des systèmes embarqués permet une conception rapide tout en respectant des contraintes temps-réels et en conservant une consommation énergétique basse.Exécuter une application sur un processeur many-core requiert un dispatching des tâches appelé problème de mapping et est connu comme étant NP-complet.Les contributions de cette thèse sont divisées en trois parties :Tout d'abord, nous étendons d'importantes propriétés dataflow au modèle Phased Computation Graph.Ensuite, nous présentons un générateur de graphe dataflow capable de générer des Synchonous Dataflow Graphs, Cyclo-Static Dataflow Graphs et Phased Computation Graphs vivant avec plus de 10000 tâches en moins de 30 secondes. Le générateur est comparé à SDF3 et PREESM.Enfin, la contribution majeure de cette thèse propose une nouvelle méthode d'évaluation d'un mapping en utilisant les modèles Synchonous Dataflow Graphe et Cyclo-Static Dataflow Graphe. La méthode évalue efficacement la mémoire consommée par les communications d'un dataflow mappé sur une architecture à mémoire distribuée. L'évaluation est déclinée en deux versions, la première garantit la vivacité alors que la seconde ajoute une contrainte de débit. La méthode d'évaluation est expérimentée avec des dataflow générés par Turbine et avec des applications réelles
With the increasing use of smart-phones, connected objects or automated vehicles, embedded systems have become ubiquitous in our living environment. These systems are often highly constrained in terms of power consumption and size. They are more and more implemented with many-core processor array that allow, rapid design to meet stringent real-time constraints while operating at relatively low frequency, with reduced power consumption.Running an application on a processor array requires dispatching its tasks on the processors in order to meet capacity and performance constraints. This mapping problem is known to be NP-complete.The contributions of this thesis are threefold:First we extend important notions from the Cyclo-Static Dataflow Graph to the Phased Computation Graph model and two equivalent sufficient conditions of liveness.Second, we present a random dataflow graph generator able to generate Synchonous Dataflow Graphs, Cyclo-Static Dataflow Graphs and Phased Computation Graphs. The Generator, is able to generate live dataflow of up to 10,000 tasks in less than 30 seconds. It is compared with SDF3 and PREESM.Third and most important, we propose a new method of evaluation of a mapping using the Synchonous Dataflow Graph and the Cyclo-Static Dataflow Graph models. The method evaluates efficiently the memory footprint of the communications of a dataflow graph mapped on a distributed architecture. The evaluation is declined in two versions, the first guarantees a live mapping while the second accounts for a constraint on throughput.The evaluation method is experimented on dataflow graphs from Turbine and on real-life applications
APA, Harvard, Vancouver, ISO, and other styles
7

Vaverka, Filip. "Lokalizace mobilního robota pomocí kamery." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2015. http://www.nusl.cz/ntk/nusl-234985.

Full text
Abstract:
This thesis describes design and implementation of an approach to the mobile robot localization. The proposed method is based purely on images taken by a monocular camera. The described solution handles localization as an association problem and, therefore, falls in the category of topological localization methods. The method is based on a generative probabilistic model of the environment appearance. The proposed solution is capable to eliminate some of the difficulties which are common in traditional localization approaches.
APA, Harvard, Vancouver, ISO, and other styles
8

Russ, Ricardo. "Service Level Achievments - Test Data for Optimal Service Selection." Thesis, Linnéuniversitetet, Institutionen för datavetenskap (DV), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-50538.

Full text
Abstract:
This bachelor’s thesis was written in the context of a joint research group, which developed a framework for finding and providing the best-fit web service for a user. The problem of the research group lays in testing their developed framework sufficiently. The framework can either be tested with test data produced by real web services which costs money or by generated test data based on a simulation of web service behavior. The second attempt has been developed within this scientific paper in the form of a test data generator. The generator simulates a web service request by defining internal services, whereas each service has an own internal graph which considers the structure of a service. A service can be atomic or can be compose of other services that are called in a specific manner (sequential, loop, conditional). The generation of the test data is done by randomly going through the services which result in variable response times, since the graph structure changes every time the system has been initialized. The implementation process displayed problems which have not been solved within the time frame. Those problems are displaying interesting challenges for the dynamical generation of random graphs. Those challenges should be targeted in further research.
APA, Harvard, Vancouver, ISO, and other styles
9

Gao, Pu. "Generation and properties of random graphs and analysis of randomized algorithms." Thesis, 2010. http://hdl.handle.net/10012/4987.

Full text
Abstract:
We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large random regular graphs beginning with small ones. We prove that the limiting joint distribution of the numbers of short cycles in the resulting graph is independent Poisson. We use the coupling method to bound the total variation distance between the joint distribution of short cycle counts and its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound of the $\eps$-mixing time. The coupling involves two different, though quite similar, Markov chains that are not time-homogeneous. We also show that the $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound is essentially tight. We study also the connectivity of random $d$-regular graphs generated by the pegging algorithm. We show that these graphs are asymptotically almost surely $d$-connected for any even constant $d\ge 4$. The problem of orientation of random hypergraphs is motivated by the classical load balancing problem. Let $h>w>0$ be two fixed integers. Let $\orH$ be a hypergraph whose hyperedges are uniformly of size $h$. To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to this hyperedge, and the rest negative. A $(w,k)$-orientation of $\orH$ consists of a $w$-orientation of all hyperedges of $\orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The other topic we discuss is computing the probability of induced subgraphs in a random regular graph. Let $0
APA, Harvard, Vancouver, ISO, and other styles
10

Lyu, Yu-Han, and 呂昱翰. "Random Generating k-connected Graphs." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/21237074229415401785.

Full text
Abstract:
碩士
國立清華大學
資訊工程學系
95
Enumerating combinatorial objects is an important research topic in combinatorics. Algorithms for random generating combinatorial objects are called sampling. Sampling has many applications in computer science, for example program testing. Mathematicians can use sampling to verify combinatorial property. We developed a simple algorithm to sample k-connected graphs based on Markov Chain Monte Carlo method. This algorithm generates graphs at approximately uniform distribution, and we prove it is rapidly mixing
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Random graph generation"

1

Reggini, Horacio C. Regular polyhedra: Random generation, Hamiltonian paths, and single chain nets. Buenos Aires: Academia Nacional de Ciencias Exactas, Físicas y Naturales, 1991.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Mikov, Aleksandr. Generalized graphs and grammars. ru: INFRA-M Academic Publishing LLC., 2021. http://dx.doi.org/10.12737/1013698.

Full text
Abstract:
The textbook deals with ordinary graphs and their generalizations-hypergraphs, hierarchical structures, geometric graphs, random and dynamic graphs. Graph grammars are considered in detail. Meets the requirements of the federal state educational standards of higher education of the latest generation. For master's students studying in the areas of the 02.00.00 group "Computer and Information Sciences", and can also be used in senior bachelor's courses and other areas in the field of computer science and computer engineering.
APA, Harvard, Vancouver, ISO, and other styles
3

Coolen, A. C. C., A. Annibale, and E. S. Roberts. Random graph ensembles. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0003.

Full text
Abstract:
This chapter presents some theoretical tools for defining random graph ensembles systematically via soft or hard topological constraints including working through some properties of the Erdös-Rényi random graph ensemble, which is the simplest non-trivial random graph ensemble where links appear between two nodes with a fixed probability p. The chapter sets out the central representation of graph generation as the result of a discrete-time Markovian stochastic process. This unites the two flavours of graph generation approaches – because they can be viewed as simply moving forwards or backwards through this representation. It is possible to define a random graph by an algorithm, and then calculate the associated stationary probability. The alternative approach is to specify sampling weights and then to construct an algorithm that will have these weights as the stationary probabilities upon convergence.
APA, Harvard, Vancouver, ISO, and other styles
4

Coolen, A. C. C., A. Annibale, and E. S. Roberts. Applications of random graphs. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0011.

Full text
Abstract:
This chapter reviews graph generation techniques in the context of applications. The first case study is power grids, where proposed strategies to prevent blackouts have been tested on tailored random graphs. The second case study is in social networks. Applications of random graphs to social networks are extremely wide ranging – the particular aspect looked at here is modelling the spread of disease on a social network – and how a particular construction based on projecting from a bipartite graph successfully captures some of the clustering observed in real social networks. The third case study is on null models of food webs, discussing the specific constraints relevant to this application, and the topological features which may contribute to the stability of an ecosystem. The final case study is taken from molecular biology, discussing the importance of unbiased graph sampling when considering if motifs are over-represented in a protein–protein interaction network.
APA, Harvard, Vancouver, ISO, and other styles
5

Coolen, Ton, Alessia Annibale, and Ekaterina Roberts. Generating Random Networks and Graphs. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.001.0001.

Full text
Abstract:
This book supports researchers who need to generate random networks, or who are interested in the theoretical study of random graphs. The coverage includes exponential random graphs (where the targeted probability of each network appearing in the ensemble is specified), growth algorithms (i.e. preferential attachment and the stub-joining configuration model), special constructions (e.g. geometric graphs and Watts Strogatz models) and graphs on structured spaces (e.g. multiplex networks). The presentation aims to be a complete starting point, including details of both theory and implementation, as well as discussions of the main strengths and weaknesses of each approach. It includes extensive references for readers wishing to go further. The material is carefully structured to be accessible to researchers from all disciplines while also containing rigorous mathematical analysis (largely based on the techniques of statistical mechanics) to support those wishing to further develop or implement the theory of random graph generation. This book is aimed at the graduate student or advanced undergraduate. It includes many worked examples, numerical simulations and exercises making it suitable for use in teaching. Explicit pseudocode algorithms are included to make the ideas easy to apply. Datasets are becoming increasingly large and network applications wider and more sophisticated. Testing hypotheses against properly specified control cases (null models) is at the heart of the ‘scientific method’. Knowledge on how to generate controlled and unbiased random graph ensembles is vital for anybody wishing to apply network science in their research.
APA, Harvard, Vancouver, ISO, and other styles
6

Coolen, A. C. C., A. Annibale, and E. S. Roberts. Introduction. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0001.

Full text
Abstract:
This introductory chapter sets the scene for the material which follows by briefly introducing the study of networks and describing their wide scope of application. It discusses the role of well-specified random graphs in setting network science onto a firm scientific footing, emphasizing the importance of well-defined null models. Non-trivial aspects of graph generation are introduced. An important distinction is made between approaches that begin with a desired probability distribution on the final graph ensembles and approaches where the graph generation process is the main object of interest and the challenge is to analyze the expected topological properties of the generated networks. At the core of the graph generation process is the need to establish a mathematical connection between the stochastic graph generation process and the stationary probability distribution to which these processes evolve.
APA, Harvard, Vancouver, ISO, and other styles
7

Coolen, A. C. C., A. Annibale, and E. S. Roberts. Ensembles with hard constraints. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0005.

Full text
Abstract:
This chapter introduces random graph ensembles involving hard constraints such as setting a fixed total number of links or fixed degree sequence, including properties of the partition function. It continues on from the previous chapter’s investigation of ensembles with soft-constrained numbers of two-stars (two-step paths) and soft-constrained total number of triangles, but now combined with a hard constraint on the total number of links. This illustrates phase transitions in a mixed-constrained ensemble – which in this case is shown to be a condensation transition, where the network becomes clumped. This is investigated in detail using techniques from statistical mechanics and also looking at the averaged eigenvalue spectrum of the ensemble. These phase transition phenomena have important implications for the design of graph generation algorithms. Although hard constraints can (by force) impose required values of observables, difficult-to-reconcile constraints can lead to graphs being generated with unexpected and unphysical overall topologies.
APA, Harvard, Vancouver, ISO, and other styles
8

Coolen, A. C. C., A. Annibale, and E. S. Roberts. Soft constraints: exponential random graph models. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0004.

Full text
Abstract:
Exponential random graph models (ERGMs) provide conceptually elegant recipes for generating soft-constrained random graphs. This chapter begins by explaining the theory and describing how to properly specify an ERGM, including demonstrating Lagrange’s method to derive the values of the model parameters that correspond to the desired constraints. Three ERGMs, all with constraints depending linearly on the adjacency matrix, are solved exactly: the targeted total number of links, targeted individual node degrees and targeted number of two-way links in a directed graph. However, when the controlled features become more complicated, ERGMs have a tendency to produce graphs in extreme phases (very dense or very sparse). The two-star model and the Strauss model are worked through in detail using advanced techniques from statistical mechanics in order to analyze the phase transitions. The chapter closes with a discussion of the strengths and weaknesses of ERGMs as null models.
APA, Harvard, Vancouver, ISO, and other styles
9

Coolen, Ton, Alessia Annibale, and Ekaterina Roberts. Generating Random Networks and Graphs. Oxford University Press, 2017.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Coolen, A. C. C., A. Annibale, and E. S. Roberts. Specific constructions. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0009.

Full text
Abstract:
This chapter presents network-generating models which cannot be neatly categorized as growing, nor as defined primarily through a target degree distribution. They are best understood as mechanistic constructions designed to elucidate a particular feature of the network. In the first sub-section, the Watts–Strogatz model is introduced and motivated as a construction to achieve both a high degree of clustering and a low average path length. Geometric graphs, in their Euclidian flavour, are shown to be a natural choice for broadcast networks. The Hyperbolic variant is informally described, because it is known to be a natural space in which to embed hierarchical graphs. Planar graphs have very specific real-world applications, but are extraordinarily challenging to analyze mathematically. Finally, weighted graphs allow for concepts such as traffic to be incorporated into the random graph model.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Random graph generation"

1

Bach, Benjamin, Andre Spritzer, Evelyne Lutton, and Jean-Daniel Fekete. "Interactive Random Graph Generation with Evolutionary Algorithms." In Graph Drawing, 541–52. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-36763-2_48.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Trejo-Sánchez, Joel Antonio, Andrés Vela-Navarro, Alejandro Flores-Lamas, José Luis López-Martínez, Carlos Bermejo-Sabbagh, Nora Leticia Cuevas-Cuevas, and Homero Toral-Cruz. "Fast Random Cactus Graph Generation." In Communications in Computer and Information Science, 129–36. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-10448-1_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Leborgne, Aurélie, Marija Kirandjiska, and Florence Le Ber. "Random Generation of a Locally Consistent Spatio-Temporal Graph." In Graph-Based Representation and Reasoning, 155–69. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-86982-3_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Nobari, Sadegh, Qiang Qu, Muhammad Muzammal, and Qingshan Jiang. "Renovating Watts and Strogatz Random Graph Generation by a Sequential Approach." In Web Information Systems Engineering – WISE 2018, 348–63. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-02922-7_24.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Canon, Louis-Claude, Mohamad El Sayah, and Pierre-Cyrille Héam. "A Comparison of Random Task Graph Generation Methods for Scheduling Problems." In Lecture Notes in Computer Science, 61–73. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-29400-7_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Omodeo, Eugenio G., Alberto Policriti, and Alexandru I. Tomescu. "Random Generation of Sets." In On Sets and Graphs, 201–16. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-54981-1_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Raman, Rajeev. "Generating random graphs efficiently." In Advances in Computing and Information — ICCI '91, 149–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991. http://dx.doi.org/10.1007/3-540-54029-6_164.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Tinhofer, G. "Generating Graphs Uniformly at Random." In Computing Supplementum, 235–55. Vienna: Springer Vienna, 1990. http://dx.doi.org/10.1007/978-3-7091-9076-0_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Şeker, Oylum, Pinar Heggernes, Tınaz Ekim, and Z. Caner Taşkın. "Linear-Time Generation of Random Chordal Graphs." In Lecture Notes in Computer Science, 442–53. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-57586-5_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Chakraborty, Sumit, Maumita Chakraborty, and Rajat Kumar Pal. "Generation of Simple Undirected Connected Random Graphs." In Lecture Notes on Data Engineering and Communications Technologies, 197–206. Singapore: Springer Singapore, 2021. http://dx.doi.org/10.1007/978-981-33-4968-1_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Random graph generation"

1

Nobari, Sadegh, Xuesong Lu, Panagiotis Karras, and Stéphane Bressan. "Fast random graph generation." In the 14th International Conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/1951365.1951406.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Cordeiro, Daniel, Grégory Mounié, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, and Frédéric Wagner. "Random graph generation for scheduling simulations." In 3rd International ICST Conference on Simulation Tools and Techniques. ICST, 2010. http://dx.doi.org/10.4108/icst.simutools2010.8667.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Liu, Fang, Evercita Eugenio, Ick Hoon Jin, and Claire Bowen. "Differentially Private Generation of Social Networks via Exponential Random Graph Models." In 2020 IEEE 44th Annual Computers, Software, and Applications Conference (COMPSAC). IEEE, 2020. http://dx.doi.org/10.1109/compsac48688.2020.00-11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Mariano, Matheus Monteiro, Érica Ferreira Souza, André Takeshi Endo, and Nandamudi L. Vijaykumar. "A comparative study of algorithms for generating switch cover test sets." In XV Simpósio Brasileiro de Qualidade de Software. Sociedade Brasileira de Computação - SBC, 2016. http://dx.doi.org/10.5753/sbqs.2016.15122.

Full text
Abstract:
Test case generation based on Finite State Machines (FSMs) has been extensively investigated due to its accuracy and simplicity. Several test criteria have been proposed in the literature to generate test cases based on FSMs. One of the oldest criteria is the Switch Cover. As a main feature, the Switch Cover criterion defines that all transition pairs of an FSM must be covered. The classical Switch Cover algorithm converts the FSM into a graph (known as Dual Graph); this graph is balanced, and, finally, traversed based on an Eulerian Cycle algorithm. In this context, considering the stage where an FSM is converted into a graph, this study investigates other search algorithms on graphs, namely Depth-First Search (DFS) and Breadth-First Search (BFS), for generating test sets from a Dual Graph. We presented an experimental study that compares the DFS, BFS algorithms with the Eulerian Cycle. The study was conducted with a set of random and real-world machines, taking into account the number of test cases, the test suite size, the average length of sequences and generation time.
APA, Harvard, Vancouver, ISO, and other styles
5

Caragiannis, Ioannis, and Evanthia Tsitsoka. "Deanonymizing Social Networks Using Structural Information." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/169.

Full text
Abstract:
We study the following fundamental graph problem that models the important task of deanonymizing social networks. We are given a graph representing an eponymous social network and another graph, representing an anonymous social network, which has been produced by the original one after removing some of its nodes and adding some noise on the links. Our objective is to correctly associate as many nodes of the anonymous network as possible to their corresponding node in the eponymous network. We present two algorithms that attack the problem by exploiting only the structure of the two graphs. The first one exploits bipartite matching computations and is relatively fast. The second one is a local search heuristic which can use the outcome of our first algorithm as an initial solution and further improve it. We have applied our algorithms on inputs that have been produced by well-known random models for the generation of social networks as well as on inputs that use real social networks. Our algorithms can tolerate noise at the level of up to 10%. Interestingly, our results provide further evidence to which graph generation models are most suitable for modeling social networks and distinguish them from unrealistic ones.
APA, Harvard, Vancouver, ISO, and other styles
6

Al-Ghafees, Mohammed, and James Whittaker. "Markov Chain-based Test Data Adequacy Criteria: a Complete Family." In 2002 Informing Science + IT Education Conference. Informing Science Institute, 2002. http://dx.doi.org/10.28945/2435.

Full text
Abstract:
The idea of using white box data flow information to select test cases is well established and has proven an effective testing strategy. This paper extends the concept of data flow testing to the case in which the source code is unavailable and only black box information can be used to make test selection decisions. In such cases, data flow testing is performed by constructing a behavior model of the software under test to act as a surrogate for the program flow graph upon which white box data flow testing is based. The behavior model is a graph representation of externally-visible software state and input-induced state transitions. We first summarize the modeling technique and then define the new data flow selection rules and describe how they are used to generate test cases. Theoretical proof of concept is provided based on a characteristic we call transition variation. Finally, we present results from a laboratory experiments in which we compare the fault detection capability of black box data flow tests to other common techniques of test generation from graphs, including simple random sampling, operational profile sampling and state transition coverage.
APA, Harvard, Vancouver, ISO, and other styles
7

Kim, Jeong Han, and Van H. Vu. "Generating random regular graphs." In the thirty-fifth ACM symposium. New York, New York, USA: ACM Press, 2003. http://dx.doi.org/10.1145/780542.780576.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Gao, Pu, and Nicholas Wormald. "Uniform Generation of Random Regular Graphs." In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2015. http://dx.doi.org/10.1109/focs.2015.78.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Vullikanti, Anil Kumar S. "Parallel Generation of Large-Scale Random Graphs." In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 2018. http://dx.doi.org/10.1109/ipdpsw.2018.00054.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Bayati, Mohsen, Andrea Montanari, and Amin Saberi. "Generating Random Graphs with Large Girth." In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2009. http://dx.doi.org/10.1137/1.9781611973068.63.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Random graph generation"

1

Moseman, Elizabeth. Improving the Computational Efficiency of the Blitzstein-Diaconis Algorithm for Generating Random Graphs of Prescribed Degree. National Institute of Standards and Technology, July 2015. http://dx.doi.org/10.6028/nist.ir.8066.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Schulz, Jan, Daniel Mayerhoffer, and Anna Gebhard. A Network-Based Explanation of Perceived Inequality. Otto-Friedrich-Universität, 2021. http://dx.doi.org/10.20378/irb-49393.

Full text
Abstract:
Across income groups and countries, the public perception of economic inequality and many other macroeconomic variables such as inflation or unemployment rates is spectacularly wrong. These misperceptions have far-reaching consequences, as it is perceived inequality, not actual inequality informing redistributive preferences. The prevalence of this phenomenon is independent of social class and welfare regime, which suggests the existence of a common mechanism behind public perceptions. We propose a network-based explanation of perceived inequality building on recent advances in random geometric graph theory. The literature has identified several stylised facts on how individual perceptions respond to actual inequality and how these biases vary systematically along the income distribution. Our generating mechanism can replicate all of them simultaneously. It also produces social networks that exhibit salient features of real-world networks; namely, they cannot be statistically distinguished from small-world networks, testifying to the robustness of our approach. Our results, therefore, suggest that homophilic segregation is a promising candidate to explain inequality perceptions with strong implications for theories of consumption behaviour.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Random graph generation' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography