R202, Astronomy-Mathematics Building, NTU
(台灣大學天文數學館 202室)
Community Recovery from Beyond-Pairwise Information
I-Hsiang Wang (National Taiwan University)
Abstract:
In this talk, we explore two community detection methods that leverage beyond-pairwise relational information and statistical information respectively. For harnessing beyond-pairwise relational information, we cast it into a hypergraph clustering problem, where each hyperedge represents the relational information among the entities represented by the vertices in that hyperedge. A polynomial running time recovery algorithm is proposed to achieve the fundamental statistical limit of community detection on a hypergraph stochastic block model. For leveraging beyond-pairwise statistical information, we cast it into a data extraction problem where the recovery algorithm can actively take measurements on a group of entities, each of which records the histogram of community labels in that group. An explicit construction of the measured groups along with a linear running time recovery algorithm is proposed to achieve the fundamental limit on the total number of measurements required to recover all the hidden community labels. The fundamental limit is then extended to the setting of partial recovery with noisy measurements.