Graphlet decomposition of a weighted network

Hossein Azari Soufiani, Edo Airoldi ; JMLR W&CP 22: 54-63, 2012.

Abstract

We consider the problem of modeling networks with nonnegative edge weights. We develop a \emph{bit-string decomposition (BSD)} for weighted networks, a new representation of social information based on social structure, with an underlying semi-parametric statistical model. We develop a scalable inference algorithm, which combines Expectation-Maximization with Bron-Kerbosch in a novel fashion, for estimating the model's parameters from a network sample. We present theoretical descriptions to the computational complexity of the method. Finally, we demonstrate the performance of the proposed methodology for synthetic data, academic networks from Facebook and finding communities in a historical data from 19th century.