Optimal partition of geometric complex networks

Abstract

We introduce a method to find a low sparsity partition and an estimate h of the Cheeger constant of complex networks by exploiting the geometric properties that many networks exhibit. We generate synthetic networks from the S1/H2 model and obtain estimates for h that are between one and three orders of magnitude lower than the average sparsity over a large number of random partitions, ⟨s⟩, and decrease with network size. We then select seven real networks, infer an embedding into the hyperbolic disk and obtain estimates for h that are all lower than ⟨s⟩, but only three of them are at least one order of magnitude below. In conclusion, the geometric method provides better results than random in all cases and, if the network exhibits an underlying metric space, it provides estimates that are orders of magnitude lower than random and decrease with network size.