  A community needs to be partitioned into disjoint groups; each community
member has an underlying preference over the groups that they would want to be
a member of. We are interested in finding a stable community structure: one
where no subset of members $S$ wants to deviate from the current structure. We
model this setting as a hedonic game, where players are connected by an
underlying interaction network, and can only consider joining groups that are
connected subgraphs of the underlying graph. We analyze the relation between
network structure, and one's capability to infer statistically stable (also
known as PAC stable) player partitions from data. We show that when the
interaction network is a forest, one can efficiently infer PAC stable coalition
structures. Furthermore, when the underlying interaction graph is not a forest,
efficient PAC stabilizability is no longer achievable. Thus, our results
completely characterize when one can leverage the underlying graph structure in
order to compute PAC stable outcomes for hedonic games. Finally, given an
unknown underlying interaction network, we show that it is NP-hard to decide
whether there exists a forest consistent with data samples from the network.
