On the Conductance of Random Inner Product Graphs

May 5, 2010
Milena Mihail | Georgia Tech

Random inner product graphs form a special case of inhomogeneous random graphs.
The model outline is that n vertices are generated from a fixed distribution μ in d-dimensional space,
and two vertices are connected with an edge with probability proportional
to the inner product of their corresponding vectors.
We show that, under the strong inner product condition,
random inner product graphs with minimum degree Ω (log ² n)
have constant conductance, with high probability.
However: (1) Their conductance depends on μ and may differ from classical random graphs.
(2)Their “sparsest cuts” may involve sets of vertices of cardinalities
much larger than the cardinalities of the sparsest cuts of classical random graphs.
The above is in accordance with measurements in many real complex networks.
Joint work with Stephen Young (UCSD).

Speaker Details

Milena Mihail received her PhD from Harvard in 1989.
She served as member of technical staff, manager and senior research scientist
at Bell Communications Research from 1989 until 1999. She joined the
faculty at Georgia Tech in 2000, where she is Associate Professor of
Computer Science. Her expertize is on randomized and approximation algorithms.