Modeling social network relationships via t-cherry junction trees

Brian Proulx, Junshan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


The massive scale of online social networks makes it very challenging to characterize the underlying structure therein. In this paper, we employ the t-cherry junction tree, a very recent advancement in probabilistic graphical models, to develop a compact representation and good approximation of an otherwise intractable model for users' relationships in a social network. There are a number of advantages in this approach: 1) the best approximation possible via junction trees belongs to the class of t-cherry junction trees; 2) constructing a t-cherry junction tree can be largely parallelized; and 3) inference can be performed using distributed computation. To improve the quality of approximation, we also devise an algorithm to build a higher order tree gracefully from an existing one, without constructing it from scratch. We apply this approach to Twitter data containing 100,000 nodes and study the problem of recommending connections to new users.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Print)9781479933600
StatePublished - Jan 1 2014
Event33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, ON, Canada
Duration: Apr 27 2014May 2 2014

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
CityToronto, ON

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Cite this