Journal articles: '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

11

BASSINO, FRÉDÉRIQUE, CYRIL NICAUD, and PASCAL WEIL. "RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP." International Journal of Algebra and Computation 18, no. 02 (March 2008): 375–405. http://dx.doi.org/10.1142/s0218196708004482.

Full text

Abstract:

We give an efficient algorithm to randomly generate finitely generated subgroups of a given size, in a finite rank free group. Here, the size of a subgroup is the number of vertices of its representation by a reduced graph such as can be obtained by the method of Stallings foldings. Our algorithm randomly generates a subgroup of a given size n, according to the uniform distribution over size n subgroups. In the process, we give estimates of the number of size n subgroups, of the average rank of size n subgroups, and of the proportion of such subgroups that have finite index. Our algorithm has average case complexity [Formula: see text] in the RAM model and [Formula: see text] in the bitcost model.

APA, Harvard, Vancouver, ISO, and other styles

12

Semeráth, Oszkár, Rebeka Farkas, Gábor Bergmann, and Dániel Varró. "Diversity of graph models and graph generators in mutation testing." International Journal on Software Tools for Technology Transfer 22, no. 1 (September 11, 2019): 57–78. http://dx.doi.org/10.1007/s10009-019-00530-6.

Full text

Abstract:

Abstract When custom modeling tools are used for designing complex safety-critical systems (e.g., critical cyber-physical systems), the tools themselves need to be validated by systematic testing to prevent tool-specific bugs reaching the system. Testing of such modeling tools relies upon an automatically generated set of models as a test suite. While many software testing practices recommend that this test suite should be diverse, model diversity has not been studied systematically for graph models. In the paper, we propose different diversity metrics for models by generalizing and exploiting neighborhood and predicate shapes as abstraction. We evaluate such shape-based diversity metrics using various distance functions in the context of mutation testing of graph constraints and access policies for two separate industrial DSLs. Furthermore, we evaluate the quality (i.e., bug detection capability) of different (random and consistent) model generation techniques for mutation testing purposes.

APA, Harvard, Vancouver, ISO, and other styles

13

PEYSAKHOV, MAXIM, and WILLIAM C. REGLI. "Using assembly representations to enable evolutionary design of Lego structures." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17, no. 2 (May 2003): 155–68. http://dx.doi.org/10.1017/s0890060403172046.

Full text

Abstract:

This paper presents an approach to the automatic generation of electromechanical engineering designs. We apply messy genetic algorithm (GA) optimization techniques to the evolution of assemblies composed of LegoTM structures. Each design is represented as a labeled assembly graph and is evaluated based on a set of behavior and structural equations. The initial populations are generated at random, and design candidates for subsequent generations are produced by user-specified selection techniques. Crossovers are applied by using cut and splice operators at the random points of the chromosomes; random mutations are applied to modify the graph with a certain low probability. This cycle continues until a suitable design is found. The research contributions in this work include the development of a new GA encoding scheme for mechanical assemblies (Legos), as well as the creation of selection criteria for this domain. Our eventual goal is to introduce a simulation of electromechanical devices into our evaluation functions. We believe that this research creates a foundation for future work and it will apply GA techniques to the evolution of more complex and realistic electromechanical structures.

APA, Harvard, Vancouver, ISO, and other styles

14

Barrett, Chris, Martin Drozda, Madhav V. Marathe, S. S. Ravi, and James P. Smith. "A Mobility and Traffic Generation Framework for Modeling and Simulating Ad Hoc Communication Networks." Scientific Programming 12, no. 1 (2004): 1–23. http://dx.doi.org/10.1155/2004/921065.

Full text

Abstract:

We present a generic mobility and traffic generation framework that can be incorporated into a tool for modeling and simulating large scale ad~hoc networks. Three components of this framework, namely a mobility data generator (MDG), a graph structure generator (GSG) and an occlusion modification tool (OMT) allow a variety of mobility models to be incorporated into the tool. The MDG module generates positions of transceivers at specified time instants. The GSG module constructs the graph corresponding to the ad hoc network from the mobility data provided by MDG. The OMT module modifies the connectivity of the graph produced by GSG to allow for occlusion effects. With two other modules, namely an activity data generator (ADG) which generates packet transmission activities for transceivers and a packet activity simulator (PAS) which simulates the movement and interaction of packets among the transceivers, the framework allows the modeling and simulation of ad hoc communication networks. The design of the framework allows a user to incorporate various realistic parameters crucial in the simulation. We illustrate the utility of our framework through a comparative study of three mobility models. Two of these are synthetic models (random waypoint and exponentially correlated mobility) proposed in the literature. The third model is based on an urban population mobility modeling tool (TRANSIMS) developed at the Los Alamos National Laboratory. This tool is capable of providing comprehensive information about the demographics, mobility and interactions of members of a large urban population. A comparison of these models is carried out by computing a variety of parameters associated with the graph structures generated by the models. There has recently been interest in the structural properties of graphs that arise in real world systems. We examine two aspects of this for the graphs created by the mobility models: change associated with power control (range of transceivers) and variation in time as transceivers move in space.

APA, Harvard, Vancouver, ISO, and other styles

15

Savinkov, Rostislav, Dmitry Grebennikov, Darya Puchkova, Valery Chereshnev, Igor Sazonov, and Gennady Bocharov. "Graph Theory for Modeling and Analysis of the Human Lymphatic System." Mathematics 8, no. 12 (December 17, 2020): 2236. http://dx.doi.org/10.3390/math8122236.

Full text

Abstract:

The human lymphatic system (HLS) is a complex network of lymphatic organs linked through the lymphatic vessels. We present a graph theory-based approach to model and analyze the human lymphatic network. Two different methods of building a graph are considered: the method using anatomical data directly and the method based on a system of rules derived from structural analysis of HLS. A simple anatomical data-based graph is converted to an oriented graph by quantifying the steady-state fluid balance in the lymphatic network with the use of the Poiseuille equation in vessels and the mass conservation at vessel junctions. A computational algorithm for the generation of the rule-based random graph is developed and implemented. Some fundamental characteristics of the two types of HLS graph models are analyzed using different metrics such as graph energy, clustering, robustness, etc.

APA, Harvard, Vancouver, ISO, and other styles

16

Yang, Weihua, and David Rideout. "High Dimensional Hyperbolic Geometry of Complex Networks." Mathematics 8, no. 11 (October 23, 2020): 1861. http://dx.doi.org/10.3390/math8111861.

Full text

Abstract:

High dimensional embeddings of graph data into hyperbolic space have recently been shown to have great value in encoding hierarchical structures, especially in the area of natural language processing, named entity recognition, and machine generation of ontologies. Given the striking success of these approaches, we extend the famous hyperbolic geometric random graph models of Krioukov et al. to arbitrary dimension, providing a detailed analysis of the degree distribution behavior of the model in an expanded portion of the parameter space, considering several regimes which have yet to be considered. Our analysis includes a study of the asymptotic correlations of degree in the network, revealing a non-trivial dependence on the dimension and power law exponent. These results pave the way to using hyperbolic geometric random graph models in high dimensional contexts, which may provide a new window into the internal states of network nodes, manifested only by their external interconnectivity.

APA, Harvard, Vancouver, ISO, and other styles

17

Zhang, Ying, Shi Hang Huang, Ying Liu, Zhen Fang, and De Peng Dang. "Study on Automatic Test Paper Generation Algorithm Based on the Maximum Flow of the Upper and Lower Bounds." Advanced Materials Research 756-759 (September 2013): 3065–69. http://dx.doi.org/10.4028/www.scientific.net/amr.756-759.3065.

Full text

Abstract:

The core of exam management system is how to generate test paper automatically. The existing algorithmic is difficult to simultaneously achieve the requirements with efficient, random, flexible and expansive performance. In this paper, we introduce the maximum flow algorithm of the upper and lower bounds in the graph theory, create a test paper generation model based on constraint conditions, and implement the test paper generation under complex constraints. In addition, to illustrate the success rate and efficiency, the system generated automatically test papers on proposition needs. In turn, it verifies the correctness and rationality of the model. The algorithm proposed in this paper will provide theoretical and technical support for other systems, and it further promotes the development of the exam management system.

APA, Harvard, Vancouver, ISO, and other styles

18

Lv, Zhao, Shuming Chen, and Yaohua Wang. "Simulation-Based Hardware Verification with a Graph-Based Specification." Mathematical Problems in Engineering 2018 (2018): 1–10. http://dx.doi.org/10.1155/2018/6398616.

Full text

Abstract:

Simulation-based verification continues to be the primary technique for hardware verification due to its scalability and ease of use; however, it lacks exhaustiveness. Although formal verification techniques can exhaustively prove functional correctness, they are limited in terms of the scale of their design due to the state-explosion problem. Alternatively, semiformal approaches can involve a compromise between scalability, exhaustiveness, and resource costs. Therefore, we propose an event-driven flow graph-based specification, which can describe the cycle-accurate functional behaviors without the exploration of whole state space. To efficiently generate input sequences according to the proposed specification, we introduce a functional automatic test pattern generation (ATPG) approach, which involves the proposed intelligent redundancy-reduction strategy to solve problems of random test vectors. We also proposed functional coverage criterion based on the formal specification to support a more reliable measure of verification. We implement a verification platform based on the proposed semiformal approach and compare the proposed semiformal approach with the constrained randomized test (CRT) approach. The experiment results show that the proposed semiformal verification method ensures a more exhaustive and effective exploration of the functional correctness of designs under verification (DUVs).

APA, Harvard, Vancouver, ISO, and other styles

19

Liu, Wei, and Jing Su. "Online digital library sampling based on query related graph." Electronic Library 36, no. 6 (December 10, 2018): 1082–98. http://dx.doi.org/10.1108/el-08-2017-0163.

Full text

Abstract:

Purpose Digital library sampling is used to obtain a collection of random literature records from the backend database, which is a crucial issue for a variety of important purposes in many online digital library applications. Digital libraries can only be accessed through their query interfaces. The challenge is how to ensure the randomness of the sample via the autonomous query interface. Design/methodology/approach This paper presents an iterative and incremental approach to obtain samples through the query interface of a digital library. In the approach, a novel graph model, query-related graph, is proposed to transform the flat literature records into a graph structure, and samples are obtained iteratively by traveling the query-related graph. Besides query-related graph, the key components, query generation, termination condition and amending deviation, are also discussed in detail. Findings The extensive experiments over two real digital libraries, ISTIC and IEEE Xplore, show the proposed approach results in a better performance. First, the approach is very effective to obtain high-quality samples which are evaluated by the measure “sample deviation.” Second, the sampling process is very efficient by only submitting fewer random queries. Third, the approach is robust. Research limitations/implications This sampling approach is limited by the query interfaces on a web page. In rare cases (<3 per cent), this approach cannot access query interfaces by sophisticated techniques. Practical implications Digital library sampling is very useful for a variety of important purposes: subject distribution analysis, literature quality evaluation, digital library size estimation, source selection in digital library integration and content freshness evaluation. Social implications Myriads of online digital libraries can be accessed online. Digital library sampling is a useful way to understand digital libraries for many important applications. Originality/value Most of the attributes of a digital library query interface have infinite values, such as keyword attributes, which cannot be handled effectively by the existing sampling approaches.

APA, Harvard, Vancouver, ISO, and other styles

20

Shan, Laixiang, Jun Qin, Mingshi Chen, and Zheng Qin. "Degeneralization Algorithm for Generation of Büchi Automata Based on Contented Situation." Journal of Applied Mathematics 2015 (2015): 1–10. http://dx.doi.org/10.1155/2015/516104.

Full text

Abstract:

We present on-the-fly degeneralization algorithm used to transform generalized Büchi automata (GBA) into Büchi Automata (BA) different from the standard degeneralization algorithm. Contented situation, which is used to record what acceptance conditions are satisfiable during expanding LTL formulae, is attached to the states and transitions in the BA. In order to get the deterministic BA, the Shannon expansion is used recursively when we expand LTL formulae by applying the tableau rules. On-the-fly degeneralization algorithm is carried out in each step of the expansion of LTL formulae. Ordered binary decision diagrams are used to represent the BA and simplify LTL formulae. The temporary automata are stored as syntax directed acyclic graph in order to save storage space. These ideas are implemented in a conversion algorithm used to build a property automaton corresponding to the given LTL formulae. We compare our method to previous work and show that it is more efficient for four sets of random formulae generated by LBTT.

APA, Harvard, Vancouver, ISO, and other styles

21

Block, Per, Christoph Stadtfeld, and Tom A. B. Snijders. "Forms of Dependence: Comparing SAOMs and ERGMs From Basic Principles." Sociological Methods & Research 48, no. 1 (November 17, 2016): 202–39. http://dx.doi.org/10.1177/0049124116672680.

Full text

Abstract:

Two approaches for the statistical analysis of social network generation are widely used; the tie-oriented exponential random graph model (ERGM) and the stochastic actor-oriented model (SAOM) or Siena model. While the choice for either model by empirical researchers often seems arbitrary, there are important differences between these models that current literature tends to miss. First, the ERGM is defined on the graph level, while the SAOM is defined on the transition level. This allows the SAOM to model asymmetric or one-sided tie transition dependence. Second, network statistics in the ERGM are defined globally but are nested in actors in the SAOM. Consequently, dependence assumptions in the SAOM are generally stronger than in the ERGM. Resulting from both, meso- and macro-level properties of networks that can be represented by either model differ substantively and analyzing the same network employing ERGMs and SAOMs can lead to distinct results. Guidelines for theoretically founded model choice are suggested.

APA, Harvard, Vancouver, ISO, and other styles

22

Al-Sharaeh, Saleh H. "Random Graph Generation Based p-Method and Box Method for the Evaluation of Power-Aware Routing Protocols of Ad hoc Networks." American Journal of Applied Sciences 5, no. 12 (December 1, 2008): 1662–69. http://dx.doi.org/10.3844/ajassp.2008.1662.1669.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Gray, Caitlin, Lewis Mitchell, and Matthew Roughan. "Generating connected random graphs." Journal of Complex Networks 7, no. 6 (March 20, 2019): 896–912. http://dx.doi.org/10.1093/comnet/cnz011.

Full text

Abstract:

Abstract Sampling random graphs is essential in many applications, and often algorithms use Markov chain Monte Carlo methods to sample uniformly from the space of graphs. However, often there is a need to sample graphs with some property that we are unable, or it is too inefficient, to sample using standard approaches. In this article, we are interested in sampling graphs from a conditional ensemble of the underlying graph model. We present an algorithm to generate samples from an ensemble of connected random graphs using a Metropolis–Hastings framework. The algorithm extends to a general framework for sampling from a known distribution of graphs, conditioned on a desired property. We demonstrate the method to generate connected spatially embedded random graphs, specifically the well-known Waxman network, and illustrate the convergence and practicalities of the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

24

Kayibi, Koko K., U. Samee, S. Pirzada, and Mohammad Ali Khan. "Rejection sampling of bipartite graphs with given degree sequence." Acta Universitatis Sapientiae, Mathematica 10, no. 2 (December 1, 2018): 249–75. http://dx.doi.org/10.2478/ausm-2018-0020.

Full text

Abstract:

Abstract Let A = (a1, a2, ..., an) be a degree sequence of a simple bipartite graph. We present an algorithm that takes A as input, and outputs a simple bipartite realization of A, without stalling. The running time of the algorithm is ⊝(n1n2), where ni is the number of vertices in the part i of the bipartite graph. Then we couple the generation algorithm with a rejection sampling scheme to generate a simple realization of A uniformly at random. The best algorithm we know is the implicit one due to Bayati, Kim and Saberi (2010) that has a running time of O(mamax), where $m = {1 \over 2}\sum\nolimits_{i = 1}^n {{a_i}} and amax is the maximum of the degrees, but does not sample uniformly. Similarly, the algorithm presented by Chen et al. (2005) does not sample uniformly, but nearly uniformly. The realization of A output by our algorithm may be a start point for the edge-swapping Markov Chains pioneered by Brualdi (1980) and Kannan et al.(1999).

APA, Harvard, Vancouver, ISO, and other styles

25

Biró, Csaba, and Udayan B. Darji. "Generating Infinite Random Graphs." Proceedings of the Edinburgh Mathematical Society 61, no. 3 (May 22, 2018): 847–68. http://dx.doi.org/10.1017/s0013091517000487.

Full text

Abstract:

AbstractWe define a growing model of random graphs. Given a sequence of non-negative integers {dn}n=0∞ with the property that di≤i, we construct a random graph on countably infinitely many vertices v0, v1… by the following process: vertex vi is connected to a subset of {v0, …, vi−1} of cardinality di chosen uniformly at random. We study the resulting probability space. In particular, we give a new characterization of random graphs, and we also give probabilistic methods for constructing infinite random trees.

APA, Harvard, Vancouver, ISO, and other styles

26

Farhang-Sardroodi, Suzan, Amir H. Darooneh, Mohammad Kohandel, and Natalia L. Komarova. "Environmental spatial and temporal variability and its role in non-favoured mutant dynamics." Journal of The Royal Society Interface 16, no. 157 (August 2019): 20180781. http://dx.doi.org/10.1098/rsif.2018.0781.

Full text

Abstract:

Understanding how environmental variability (or randomness) affects evolution is of fundamental importance for biology. The presence of temporal or spatial variability significantly affects the competition dynamics in populations, and gives rise to some counterintuitive observations. In this paper, we consider both birth–death (BD) or death–birth (DB) Moran processes, which are set up on a circular or a complete graph. We investigate spatial and temporal variability affecting division and/or death parameters. Assuming that mutant and wild-type fitness parameters are drawn from an identical distribution, we study mutant fixation probability and timing. We demonstrate that temporal and spatial types of variability possess fundamentally different properties. Under temporal randomness, in a completely mixed system, minority mutants experience (i) higher than neutral fixation probability and a higher mean conditional fixation time, if the division rates are affected by randomness and (ii) lower fixation probability and lower mean conditional fixation time if the death rates are affected. Once spatial restrictions are imposed, however, these effects completely disappear, and mutants in a circular graph experience neutral dynamics, but only for the DB update rule in case (i) and for the BD rule in case (ii) above. In contrast to this, in the case of spatially variable environment, both for BD/DB processes, both for complete/circular graph and both for division/death rates affected, minority mutants experience a higher than neutral probability of fixation. Fixation time, however, is increased by randomness on a circle, while it decreases for complete graphs under random division rates. A basic difference between temporal and spatial kinds of variability is the types of correlations that occur in the system. Under temporal randomness, mutants are spatially correlated with each other (they simply have equal fitness values at a given moment of time; the same holds for wild-types). Under spatial randomness, there are subtler, temporal correlations among mutant and wild-type cells, which manifest themselves by cells of each type ‘claiming’ better spots for themselves. Applications of this theory include cancer generation and biofilm dynamics.

APA, Harvard, Vancouver, ISO, and other styles

27

Jung, Chanju, Yong-Hyuk Kim, Yourim Yoon, and Byung-Ro Moon. "A New Adaptive Hungarian Mating Scheme in Genetic Algorithms." Discrete Dynamics in Nature and Society 2016 (2016): 1–13. http://dx.doi.org/10.1155/2016/3512546.

Full text

Abstract:

In genetic algorithms, selection or mating scheme is one of the important operations. In this paper, we suggest an adaptive mating scheme using previously suggested Hungarian mating schemes. Hungarian mating schemes consist of maximizing the sum of mating distances, minimizing the sum, and random matching. We propose an algorithm to elect one of these Hungarian mating schemes. Every mated pair of solutions has to vote for the next generation mating scheme. The distance between parents and the distance between parent and offspring are considered when they vote. Well-known combinatorial optimization problems, the traveling salesperson problem, and the graph bisection problem are used for the test bed of our method. Our adaptive strategy showed better results than not only pure and previous hybrid schemes but also existing distance-based mating schemes.

APA, Harvard, Vancouver, ISO, and other styles

28

Ramírez Pérez, José Felipe, Dariel Corchado López del Castillo, and Maylevis Morejón Valdés. "Algorithm for measurement and analysis of authority and influence of users in social and professional networks." PAAKAT: Revista de Tecnología y Sociedad 11, no. 21 (August 26, 2021): 1–27. http://dx.doi.org/10.32870/pk.a11n21.598.

Full text

Abstract:

The measurement and analysis of the authority and influence exercised by a person in an organization or social network, be it formal or informal, has been the subject of numerous researches in several fields of science. At present, this phenomenon has taken on greater connotation due to its irruption in the digital space and the importance of having this knowledge for decision-making in spheres such as politics, education and the dissemination of information. In this research, an algorithm was developed for the measurement and analysis of the authority and influence of users in social and professional networks. The study had a mixed approach, with correlational scope and experimental design. A random sample n = 30 specialists was used, which was carried out between May 2019 and October 2020. It was based on the premise that, in order to carry out an adequate measurement and analysis of authority and influence, the structure of the graph must be considered that represents the social network and the interactions that occur between users. As a result, the Total Authority algorithm is developed, a computer tool for the generation of the graph and a case study, which evaluates its relevance, operation and applicability, which shows satisfactory results in its comparison with the HITS algorithm and a sociogram.

APA, Harvard, Vancouver, ISO, and other styles

29

Jiang, Yu, Meilian Liang, Yanmei Teng, and Xiaodong Xu. "Random Cyclic Triangle-Free Graphs of Prime Order." Journal of Mathematics 2021 (August 7, 2021): 1–6. http://dx.doi.org/10.1155/2021/5595919.

Full text

Abstract:

Cyclic triangle-free process (CTFP) is the cyclic analog of the triangle-free process. It begins with an empty graph of order n and generates a cyclic graph of order n by iteratively adding parameters, chosen uniformly at random, subject to the constraint that no triangle is formed in the cyclic graph obtained, until no more parameters can be added. The structure of a cyclic triangle-free graph of the prime order is different from that of composite integer order. Cyclic graphs of prime order have better properties than those of composite number order, which enables generating cyclic triangle-free graphs more efficiently. In this paper, a novel approach to generating cyclic triangle-free graphs of prime order is proposed. Based on the cyclic graphs of prime order, obtained by the CTFP and its variant, many new lower bounds on R 3 , t are computed, including R 3,34 ≥ 230 , R 3,35 ≥ 242 , R 3,36 ≥ 252 , R 3,37 ≥ 264 , R 3,38 ≥ 272 . Our experimental results demonstrate that all those related best known lower bounds, except the bound on R 3,34 , are improved by 5 or more.

APA, Harvard, Vancouver, ISO, and other styles

30

WANG, CHENG, OMAR LIZARDO, and DAVID HACHEN. "Algorithms for generating large-scale clustered random graphs." Network Science 2, no. 3 (November 21, 2014): 403–15. http://dx.doi.org/10.1017/nws.2014.7.

Full text

Abstract:

AbstractReal-world networks are often compared to random graphs to assess whether their topological structure could be a result of random processes. However, a simple random graph in large scale often lacks social structure beyond the dyadic level. As a result we need to generate clustered random graph to compare the local structure at higher network levels. In this paper a generalized version of Gleeson's algorithm G(VS, VT, ES, ET, S, T) is advanced to generate a clustered random graph in large-scale which persists the number of vertices |V|, the number of edges |E|, and the global clustering coefficient CΔ as in the real network and it works successfully for nine large-scale networks. Our new algorithm also has advantages in randomness evaluation and computation efficiency when compared with the existing algorithms.

APA, Harvard, Vancouver, ISO, and other styles

31

GERKE, STEFANIE, ANGELIKA STEGER, and NICHOLAS WORMALD. "Pegging Graphs Yields a Small Diameter." Combinatorics, Probability and Computing 20, no. 2 (August 24, 2010): 239–48. http://dx.doi.org/10.1017/s096354831000026x.

Full text

Abstract:

We consider the following process for generating large random cubic graphs. Starting with a given graph, repeatedly add edges that join the midpoints of two randomly chosen edges. We show that the growing graph asymptotically almost surely has logarithmic diameter. This process is motivated by a particular type of peer-to-peer network. Our method extends to similar processes that generate regular graphs of higher degree.

APA, Harvard, Vancouver, ISO, and other styles

32

Gao, Su, and Chuang Shao. "Random generations of the countable random graph." Annals of Pure and Applied Logic 143, no. 1-3 (November 2006): 79–86. http://dx.doi.org/10.1016/j.apal.2005.12.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

TAO, TREVOR. "An improved MCMC algorithm for generating random graphs from constrained distributions." Network Science 4, no. 1 (February 11, 2016): 117–39. http://dx.doi.org/10.1017/nws.2015.35.

Full text

Abstract:

AbstractWe consider the problem of generating uniformly random graphs from a constrained distribution. A graph is valid if it obeys certain constraints such as a given number of nodes, edges, k-stars or degree sequence, and each graph must occur with equal probability. A typical application is to confirm the correctness of a model by repeated sampling and comparing statistical properties against empirical data. Markov Chain Monte Carlo (MCMC) algorithms are often used, but have certain difficulties such as the inability to search the space of all possible valid graphs. We propose an improved algorithm which overcomes these difficulties. Although each individual iteration of the MCMC algorithm takes longer, we obtain better coverage of the search space in the same amount of time. This leads to better estimates of various quantities such as the expected number of transitive triads given the constraints. The algorithm should be of general interest with many possible applications, including the world wide web, biological, and social networks.

APA, Harvard, Vancouver, ISO, and other styles

34

Wormald, Nicholas C. "Generating Random Unlabelled Graphs." SIAM Journal on Computing 16, no. 4 (August 1987): 717–27. http://dx.doi.org/10.1137/0216048.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Kim, J. H., and V. H. Vu*. "Generating Random Regular Graphs." Combinatorica 26, no. 6 (December 2006): 683–708. http://dx.doi.org/10.1007/s00493-006-0037-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Yao, W., P. Polewski, and P. Krzystek. "SEMANTIC LABELLING OF ULTRA DENSE MLS POINT CLOUDS IN URBAN ROAD CORRIDORS BASED ON FUSING CRF WITH SHAPE PRIORS." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLII-2/W7 (September 13, 2017): 971–76. http://dx.doi.org/10.5194/isprs-archives-xlii-2-w7-971-2017.

Full text

Abstract:

In this paper, a labelling method for the semantic analysis of ultra-high point density MLS data (up to 4000 points/m<sup>2</sup>) in urban road corridors is developed based on combining a conditional random field (CRF) for the context-based classification of 3D point clouds with shape priors. The CRF uses a Random Forest (RF) for generating the unary potentials of nodes and a variant of the contrastsensitive Potts model for the pair-wise potentials of node edges. The foundations of the classification are various geometric features derived by means of co-variance matrices and local accumulation map of spatial coordinates based on local neighbourhoods. Meanwhile, in order to cope with the ultra-high point density, a plane-based region growing method combined with a rule-based classifier is applied to first fix semantic labels for man-made objects. Once such kind of points that usually account for majority of entire data amount are pre-labeled; the CRF classifier can be solved by optimizing the discriminative probability for nodes within a subgraph structure excluded from pre-labeled nodes. The process can be viewed as an evidence fusion step inferring a degree of belief for point labelling from different sources. The MLS data used for this study were acquired by vehicle-borne Z+F phase-based laser scanner measurement, which permits the generation of a point cloud with an ultra-high sampling rate and accuracy. The test sites are parts of Munich City which is assumed to consist of seven object classes including impervious surfaces, tree, building roof/facade, low vegetation, vehicle and pole. The competitive classification performance can be explained by the diverse factors: e.g. the above ground height highlights the vertical dimension of houses, trees even cars, but also attributed to decision-level fusion of graph-based contextual classification approach with shape priors. The use of context-based classification methods mainly contributed to smoothing of labelling by removing outliers and the improvement in underrepresented object classes. In addition, the routine operation of a context-based classification for such high density MLS data becomes much more efficient being comparable to non-contextual classification schemes.

APA, Harvard, Vancouver, ISO, and other styles

37

Sayed, Wafaa S., Hossam A. H. Fahmy, Ahmed A. Rezk, and Ahmed G. Radwan. "Generalized Smooth Transition Map Between Tent and Logistic Maps." International Journal of Bifurcation and Chaos 27, no. 01 (January 2017): 1730004. http://dx.doi.org/10.1142/s021812741730004x.

Full text

Abstract:

There is a continuous demand on novel chaotic generators to be employed in various modeling and pseudo-random number generation applications. This paper proposes a new chaotic map which is a general form for one-dimensional discrete-time maps employing the power function with the tent and logistic maps as special cases. The proposed map uses extra parameters to provide responses that fit multiple applications for which conventional maps were not enough. The proposed generalization covers also maps whose iterative relations are not based on polynomials, i.e. with fractional powers. We introduce a framework for analyzing the proposed map mathematically and predicting its behavior for various combinations of its parameters. In addition, we present and explain the transition map which results in intermediate responses as the parameters vary from their values corresponding to tent map to those corresponding to logistic map case. We study the properties of the proposed map including graph of the map equation, general bifurcation diagram and its key-points, output sequences, and maximum Lyapunov exponent. We present further explorations such as effects of scaling, system response with respect to the new parameters, and operating ranges other than transition region. Finally, a stream cipher system based on the generalized transition map validates its utility for image encryption applications. The system allows the construction of more efficient encryption keys which enhances its sensitivity and other cryptographic properties.

APA, Harvard, Vancouver, ISO, and other styles

38

KRIVELEVICH, MICHAEL, BENNY SUDAKOV, and DAN VILENCHIK. "On the Random Satisfiable Process." Combinatorics, Probability and Computing 18, no. 5 (September 2009): 775–801. http://dx.doi.org/10.1017/s0963548309990356.

Full text

Abstract:

In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas. randomly permute all $2^k\binom{n}{k}$ possible clauses over the variables x1,. . .,xn, and starting from the empty formula, go over the clauses one by one, including each new clause as you go along if, after its addition, the formula remains satisfiable. We study the evolution of this process, namely the distribution over formulas obtained after scanning through the first m clauses (in the random permutation's order).Random processes with conditioning on a certain property being respected are widely studied in the context of graph properties. This study was pioneered by Ruciński and Wormald in 1992 for graphs with a fixed degree sequence, and also by Erdős, Suen and Winkler in 1995 for triangle-free and bipartite graphs. Since then many other graph properties have been studied, such as planarity and H-freeness. Thus our model is a natural extension of this approach to the satisfiability setting.Our main contribution is as follows. For m ≥ cn, c = c(k) a sufficiently large constant, we are able to characterize the structure of the solution space of a typical formula in this distribution. Specifically, we show that typically all satisfying assignments are essentially clustered in one cluster, and all but e−Ω(m/n)n of the variables take the same value in all satisfying assignments. We also describe a polynomial-time algorithm that finds w.h.p. a satisfying assignment for such formulas.

APA, Harvard, Vancouver, ISO, and other styles

39

KANG, M., and T. G. SEIERSTAD. "The Critical Phase for Random Graphs with a Given Degree Sequence." Combinatorics, Probability and Computing 17, no. 1 (January 2008): 67–86. http://dx.doi.org/10.1017/s096354830700867x.

Full text

Abstract:

We consider random graphs with a fixed degree sequence. Molloy and Reed [11, 12] studied how the size of the giant component changes according to degree conditions. They showed that there is a phase transition and investigated the order of components before and after the critical phase. In this paper we study more closely the order of components at the critical phase, using singularity analysis of a generating function for a branching process which models the random graph with a given degree sequence.

APA, Harvard, Vancouver, ISO, and other styles

40

Melançon, G., I. Dutour, and M. Bousquet-Mélou. "Random Generation of Directed Acyclic Graphs." Electronic Notes in Discrete Mathematics 10 (November 2001): 202–7. http://dx.doi.org/10.1016/s1571-0653(04)00394-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Gao, Pu, and Nicholas Wormald. "Uniform Generation of Random Regular Graphs." SIAM Journal on Computing 46, no. 4 (January 2017): 1395–427. http://dx.doi.org/10.1137/15m1052779.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

STEGER, A., and N. C. WORMALD. "Generating Random Regular Graphs Quickly." Combinatorics, Probability and Computing 8, no. 4 (July 1999): 377–96. http://dx.doi.org/10.1017/s0963548399003867.

Full text

Abstract:

We present a practical algorithm for generating random regular graphs. For all d growing as a small power of n, the d-regular graphs on n vertices are generated approximately uniformly at random, in the sense that all d-regular graphs on n vertices have in the limit the same probability as n → ∞. The expected runtime for these ds is [Oscr ](nd2).

APA, Harvard, Vancouver, ISO, and other styles

43

Van Anh Duong, Dat, and Seokhoon Yoon. "SRMM: A Social Relationship-Aware Human Mobility Model." Electronics 9, no. 2 (January 28, 2020): 221. http://dx.doi.org/10.3390/electronics9020221.

Full text

Abstract:

Since human movement patterns are important for validating the performance of wireless networks, several traces of human movements in real life have been collected. However, collecting data about human movements is costly and time-consuming. Moreover, multiple traces are demanded to test various network scenarios. As a result, a lot of synthetic models of human movement have been proposed. Nevertheless, most of the proposed models were often based on random generation, and cannot produce realistic human movements. Although there have been a few models that tried to capture the characteristics of human movement in real life (e.g., flights, inter-contact times, and pause times following the truncated power-law distribution), those models still cannot reflect realistic human movements due to a lack of consideration for social context among people. To address those limitations, in this paper, we propose a novel human mobility model called the social relationship–aware human mobility model (SRMM), which considers social context as well as the characteristics of human movement. SRMM partitions people into social groups by exploiting information from a social graph. Then, the movements of people are determined by considering the distances to places and social relationships. The proposed model is first evaluated by using a synthetic map, and then a real road map is considered. The results of SRMM are compared with a real trace and other synthetic mobility models. The obtained results indicate that SRMM is consistently better at reflecting both human movement characteristics and social relationships.

APA, Harvard, Vancouver, ISO, and other styles

44

Oyefiade, Adeoye, Kiran Beera, Iska Moxon-Emre, Jovanka Skocic, Ute Bartels, Suzanne Laughlin, Vijay Ramaswamy, and Donald Mabbott. "QOL-09. WHOLE-BRAIN WHITE MATTER NETWORK CONNECTIVITY IS DISRUPTED BY PEDIATRIC BRAIN TUMOR TREATMENT." Neuro-Oncology 22, Supplement_3 (December 1, 2020): iii432. http://dx.doi.org/10.1093/neuonc/noaa222.673.

Full text

Abstract:

Abstract INTRODUCTION Treatments for pediatric brain tumors (PBT) are neurotoxic and lead to long-term deficits that are driven by the perturbation of underlying white matter (WM). It is unclear if and how treatment may impair WM connectivity across the entire brain. METHODS Magnetic resonance images from 41 PBT survivors (mean age: 13.19 years, 53% M) and 41 typically developing (TD) children (mean age: 13.32 years, 51% M) were analyzed. Image reconstruction, segmentation, and node parcellation were completed in FreeSurfer. DTI maps and probabilistic streamline generation were completed in MRtrix3. Connectivity matrices were based on the number of streamlines connecting two nodes and the mean DTI (FA) index across streamlines. We used graph theoretical analyses to define structural differences between groups, and random forest (RF) analyses to identify hubs that reliably classify PBT and TD children. RESULTS For survivors treated with radiation, betweeness centrality was greater in the left insular (p < 0.000) but smaller in the right pallidum (p < 0.05). For survivors treated without radiation (surgery-only), betweeness centrality was smaller in the right interparietal sulcus (p < 0.05). RF analyses showed that differences in WM connectivity from the right pallidum to other parts of the brain reliably classified PBT survivors from TD children (classification accuracy = 77%). CONCLUSIONS The left insular, right pallidum, and right inter-parietal sulcus are structurally perturbed hubs in PBT survivors. WM connectivity from the right pallidum is vulnerable to the long-term effects of treatment for PBT.

APA, Harvard, Vancouver, ISO, and other styles

45

Chiu, David K. Y., Tao Xu, and Iker Gondra. "Random Graph-based Multiple Instance Learning for Structured IoT Smart City Applications." ACM Transactions on Internet Technology 21, no. 3 (June 9, 2021): 1–17. http://dx.doi.org/10.1145/3448611.

Full text

Abstract:

Because of the complex activities involved in IoT networks of a smart city, an important question arises: What are the core activities of the networks as a whole and its basic information flow structure? Identifying and discovering core activities and information flow is a crucial step that can facilitate the analysis. This is the question we are addressing—that is, to identify the core services as a common core substructure despite the probabilistic nature and the diversity of its activities. If this common substructure can be discovered, a systemic analysis and planning can then be performed and key policies related to the community can be developed. Here, a local IoT network can be represented as an attributed graph. From an ensemble of attributed graphs, identifying the common subgraph pattern is then critical in understanding the complexity. We introduce this as the common random subgraph (CRSG) modeling problem, aiming at identifying a subgraph pattern that is the structural “core” that conveys the probabilistically distributed graph characteristics. Given an ensemble of network samples represented as attributed graphs, the method generates a CRSG model that encompasses both structural and statistical characteristics from the related samples while excluding unrelated networks. In generating a CRSG model, our method using a multiple instance learning algorithm transforms an attributed graph (composed of structural elements as edges and their two endpoints) into a “bag” of instances in a vector space. Common structural components across positively labeled graphs are then identified as the common instance patterns among instances across different bags. The structure of the CRSG arises through the combining of common patterns. The probability distribution of the CRSG can then be estimated based on the connections and distributions from the common elements. Experimental results demonstrate that CRSG models are highly expressive in describing typical network characteristics.

APA, Harvard, Vancouver, ISO, and other styles

46

Griffith, Daniel A. "Generating random connected planar graphs." GeoInformatica 22, no. 4 (September 29, 2018): 767–82. http://dx.doi.org/10.1007/s10707-018-0328-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Hagberg, Aric, and Nathan Lemons. "Fast Generation of Sparse Random Kernel Graphs." PLOS ONE 10, no. 9 (September 10, 2015): e0135177. http://dx.doi.org/10.1371/journal.pone.0135177.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Kamiński, Bogumił, Paweł Prałat, and François Théberge. "Artificial Benchmark for Community Detection (ABCD)—Fast random graph model with community structure." Network Science 9, no. 2 (January 26, 2021): 153–78. http://dx.doi.org/10.1017/nws.2020.45.

Full text

Abstract:

AbstractMost of the current complex networks that are of interest to practitioners possess a certain community structure that plays an important role in understanding the properties of these networks. For instance, a closely connected social communities exhibit faster rate of transmission of information in comparison to loosely connected communities. Moreover, many machine learning algorithms and tools that are developed for complex networks try to take advantage of the existence of communities to improve their performance or speed. As a result, there are many competing algorithms for detecting communities in large networks. Unfortunately, these algorithms are often quite sensitive and so they cannot be fine-tuned for a given, but a constantly changing, real-world network at hand. It is therefore important to test these algorithms for various scenarios that can only be done using synthetic graphs that have built-in community structure, power law degree distribution, and other typical properties observed in complex networks. The standard and extensively used method for generating artificial networks is the LFR graph generator. Unfortunately, this model has some scalability limitations and it is challenging to analyze it theoretically. Finally, the mixing parameter μ, the main parameter of the model guiding the strength of the communities, has a non-obvious interpretation and so can lead to unnaturally defined networks. In this paper, we provide an alternative random graph model with community structure and power law distribution for both degrees and community sizes, the Artificial Benchmark for Community Detection (ABCD graph). The model generates graphs with similar properties as the LFR one, and its main parameter ξ can be tuned to mimic its counterpart in the LFR model, the mixing parameter μ. We show that the new model solves the three issues identified above and more. In particular, we test the speed of our algorithm and do a number of experiments comparing basic properties of both ABCD and LFR. The conclusion is that these models produce graphs with comparable properties but ABCD is fast, simple, and can be easily tuned to allow the user to make a smooth transition between the two extremes: pure (independent) communities and random graph with no community structure.

APA, Harvard, Vancouver, ISO, and other styles

49

Davis, Michael, Zhanyu Ma, Weiru Liu, Paul Miller, Ruth Hunter, and Frank Kee. "Generating Realistic Labelled, Weighted Random Graphs." Algorithms 8, no. 4 (December 8, 2015): 1143–74. http://dx.doi.org/10.3390/a8041143.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

BODIRSKY, MANUEL, and MIHYUN KANG. "Generating Outerplanar Graphs Uniformly at Random." Combinatorics, Probability and Computing 15, no. 03 (April 7, 2006): 333. http://dx.doi.org/10.1017/s0963548305007303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Random graph generation'

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