Yandex School of Data Analysis Conference
Machine Learning: Prospects and Applications
[ Ссылка ]
We will survey some of the recent algorithmic approaches to design sublinear-
time algorithms to determine cluster structure of graphs.
As a concrete example, we will show how to test in O*(n^{1/2})-time
whether a graph with n nodes can be partitioned into no more than k clusters
such that the outer-conductance of each cluster is at least phi_out
and the inner-conductance of the induced subgraph on each cluster is at
least phi_in, for a large spectrum of parameters k, phi_out and phi_in.
