Abstract:
|
Bipartite networks are commonly observed in various scientific and engineering domains. Detection of matched communities, i.e. communities consisting of nodes of two types that are closely connected with one another, in a bipartite network is a fundamental and challenging problem. The most widely used approaches for matched community detection are either computationally inefficient or prone to non-ideal performance. In this paper, we propose a new two-stage algorithm that uses fast spectral methods to recover matched communities. We show that for bipartite networks, it is critical to adjust for the community size in matched community detection, which had not been considered by other spectral methods. Further, for the proposed algorithm, we also provide theoretical error bounds on the proportion of misclustered nodes under a variant of the stochastic block model. Numerical studies indicate that the proposed algorithm outperforms existing spectral algorithms, especially when the sizes of the matched communities of each type are proportionally different.
|