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):
  • GraSPy (Chung et al., 2019),
  • Multilayer Random Dot-Product Graph (Jones & Rubin-Delanchy, 2020)
  • RDPGM for Social Networks (Young & Scheinerman, 2007),
  • …
• Counter-Example(s):
  • an Erdos-Renyi Model,
  • an Exponential Family Random Graph Model (ERGM),
  • a Stochastic Block Model,
  • a Watts-Strogatz Model,
  • a Web-based Random-Graph Model.
• 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.

    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.

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.

---