On the Conductance of Random Inner Product Graphs

Опубликовано 17 августа 2016, 21:15

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 $\mu$ 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 $\Omega ({\log}^2 n)$ have constant conductance, with high probability. However: (1) Their conductance depends on $\mu$ 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).