Abstract | ||
---|---|---|
Let w : 0 , 1 2 ź 0 , 1 be a symmetric function, and consider the random process G ( n , w ) , where vertices are chosen from 0 , 1 uniformly at random, and w governs the edge formation probability. Such a random graph is said to have a linear embedding, if the probability of linking to a particular vertex v decreases with distance. The rate of decrease, in general, depends on the particular vertex v . A linear embedding is called uniform if the probability of a link between two vertices depends only on the distance between them. In this article, we consider the question whether it is possible to \"transform\" a linear embedding to a uniform one, through replacing the uniform probability space 0 , 1 with a suitable probability space on R . We give necessary and sufficient conditions for the existence of a uniform linear embedding for random graphs where w attains only a finite number of values. Our findings show that for a general w the answer is negative in most cases. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.ejc.2016.09.004 | Eur. J. Comb. |
Field | DocType | Volume |
Random element,Discrete mathematics,Symmetric function,Combinatorics,Random graph,Embedding,Vertex (geometry),Symmetric probability distribution,Stochastic process,Probability distribution,Mathematics | Journal | 61 |
Issue | ISSN | Citations |
C | 0195-6698 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Huda Chuangpishit | 1 | 1 | 1.50 |
Mahya Ghandehari | 2 | 21 | 3.43 |
Jeannette Janssen | 3 | 295 | 32.23 |