Random Dot-Product Graph Model
A Random Dot-Product Graph Model is a Random Graph that associates with each vertex a dot product vector.
- Example(s):
- Counter-Example(s):
- See: Markov Chain, Graph Theory, Web Page, Hyperlink, URL, Web-Graph, Directed Graph, Directed Acyclic Graph, Rado Graph.
References
2021
- (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Random_walk#Models Retrieved:2021-8-15.
- Another model, which generalizes Gilbert's random graph model, is the random dot-product model. A random dot-product graph associates with each vertex a real vector. The probability of an edge uv between any vertices u and v is some function of the dot product u • v of their respective vectors.
The network probability matrix models random graphs through edge probabilities, which represent the probability [math]\displaystyle{ p_{i,j} }[/math] that a given edge [math]\displaystyle{ e_{i,j} }[/math] exists for a specified time period. This model is extensible to directed and undirected; weighted and unweighted; and static or dynamic graphs structure.
For M ≃ pN, where N is the maximal number of edges possible, the two most widely used models, G(n,M) and G(n,p), are almost interchangeable.[1]
Random regular graphs form a special case, with properties that may differ from random graphs in general.
Once we have a model of random graphs, every function on graphs, becomes a random variable. The study of this model is to determine if, or at least estimate the probability that, a property may occur.[2]
- Another model, which generalizes Gilbert's random graph model, is the random dot-product model. A random dot-product graph associates with each vertex a real vector. The probability of an edge uv between any vertices u and v is some function of the dot product u • v of their respective vectors.
2020
- (Jones & Rubin-Delanchy, 2020) ⇒ Andrew Jones, and Patrick Rubin-Delanchy (2020). "The Multilayer Random Dot-Product Graph". In: arXiv:2007.10455.
2019
- (Chung et al., 2019) ⇒ Jaewon Chung, Benjamin D. Pedigo, Eric W. Bridgeford, Bijan K. Varjavand, Hayden S. Helm, and Joshua T. Vogelstein (2019). "GraSPy: Graph Statistics in Python". In: J. Mach. Learn. Res., 20, 158-1.
2007
- (Young & Scheinerman, 2007) ⇒ Stephen J. Young, and Edward R. Scheinerman (2007)."Random Dot Product Graph Models for Social Networks". In: Algorithms and Models for the Web-Graph, 138.
- ↑ Bollobas, B. and Riordan, O.M. “Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003
- ↑ Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.