Why Steiner-tree type algorithms work for community detection

We consider the problem of reconstructing a specific connected community S ⊂ V in a graph G = (V,E), where each node v is as-sociated with a signal whose strength grows with the likelihood that v belongs to S. This problem appears in social or protein inter-action network, the latter also referred to as the signaling pathway reconstruction prob-lem (Bailly-Bechet et al., 2011). We study this community reconstruction problem under several natural generative models, and make the following two contribu-tions. First, in the context of social networks, where the signals are modeled as bounded-supported random variables, we design an ef-ficient algorithm for recovering most mem-bers in S with well-controlled false positive overhead, by utilizing the network structure for a large family of “homogeneous ” gener-ative models. This positive result is com-plemented by an information theoretic lower bound for the case where the network struc-ture is unknown or the network is heteroge-neous. Second, we consider the case in which the graph represents the protein interaction network, in which it is customary to con-sider signals that have unbounded support, we generalize our first contribution to give the first theoretical justification of why ex-isting Steiner-tree type heuristics work well in practice. 1