Kay Bogerd (TU Eindhoven)

Detecting small communities in inhomogeneous random graphs

Many networks are organized in communities, with certain groups of vertices being more densely connected than others. When these communities are large enough they can easily be detected, whereas small communities can be more difficult, especially when the network is also inhomogeneous. In this talk, we consider the problem of detecting whether an inhomogeneous random graph contains a small community. We show when a scan test can asymptotically detect such a community, and that, in some settings, this scan test is optimal.

(joint work with: Rui Castro, Remco van der Hofstad, and Nicolas Verzelen)