Why Steiner-tree type algorithms work for community detection

Mung Chiang, Henry Lam, Zhenming Liu, H. Vincent Poor

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


We consider the problem of reconstructing a specific connected community S ⊂ V in a graph G = (V;E), where each node v is associated with a signal whose strength grows with the likelihood that v belongs to S. This problem appears in social or protein interaction network, the latter also referred to as the signaling pathway reconstruction problem (Bailly-Bechet et al., 2011). We study this community reconstruction problem under several natural generative models, and make the following two contributions. First, in the context of social networks, where the signals are modeled as boundedsupported random variables, we design an efficient algorithm for recovering most members in S with well-controlled false positive overhead, by utilizing the network structure for a large family of \homogeneous" generative models. This positive result is complemented by an information theoretic lower bound for the case where the network structure is unknown or the network is heterogeneous. Second, we consider the case in which the graph represents the protein interaction network, in which it is customary to consider signals that have unbounded support, we generalize our first contribution to give the first theoretical justification of why existing Steiner-tree type heuristics work well in practice.

Original languageEnglish (US)
Pages (from-to)187-195
Number of pages9
JournalJournal of Machine Learning Research
StatePublished - 2013
Event16th International Conference on Artificial Intelligence and Statistics, AISTATS 2013 - Scottsdale, United States
Duration: Apr 29 2013May 1 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Why Steiner-tree type algorithms work for community detection'. Together they form a unique fingerprint.

Cite this