Random Dot Product Graphs

Edward Scheinerman
Johns Hopkins University
Applied Math and Statistics

Random dot product graphs are a generalization of several well-known classes of graphs including threshold graphs, Erdos-Renyi random graphs, and intersection graphs. In this model, vertices are
associated with vectors (drawn at random from some distribution on a low-dimensional Euclidean space). The probability that two vertices are
adjacent is given by the dot product of their associated vectors. By taking the vectors appropriately, we show that the random graphs we
generate exhibit properties akin to those of social and communication networks including clustering, low diameter, and power-law distribution of degrees. We also discuss the inverse problem: Given a graph, or more
generally a set of graphs, how can we best model these graphs as random dot product graphs? The work presented is joint with Miro Kraetzl,
Christine Nickel, and Kimberly Tucker.


Presentation (PowerPoint File)
Video of Talk (RealPlayer File)

Back to Graduate Summer School: Intelligent Extraction of Information from Graphs and High Dimensional Data