On Thu, Oct 4, 2012 at 7:03 PM, Eric Purdy <epurdy@uchicago.edu> wrote:
If anyone would like to work on this problem, but needs more hints, let me know.
If we were not given a network but we were given the probability functions α and β and a complete set of rankings on n vertices, then we could use this model to generate—for instance on a computer—a hypothetical but plausible network in which edges appeared with the appropriate probabilities. In effect, we have a random graph model that incorporates rankings. In this paper, however, we want to perform the reverse operation: given a network we want to deduce the rankings of the nodes and the values of the functions α and β. To put that another way, if we are given a network and we assume that it is generated from our model, what values of the rankings and probability functions are most likely to have generated the network we observe?
This question leads us to a maximum likelihood formulation of our problem, which we treat using an expectation–maximization (EM) approach in which the ranks R are considered hidden variables to be determined and the functions α and β are parameters of the model.
Using a Poisson formulation of the random network generation process, we can write the probability of generation of a network G with rankings R, given the functions
α and β, as (See Eq 1)
...The function β takes a more complicated form which we parametrize as a Fourier cosine series, keeping five terms and squaring to enforce nonnegativity, plus an additional Gaussian peak at the origin