Abstract In this work we show that, using the eigen-decomposition of the adjacencymatrix, we can consistently estimate latent positions for random dot productgraphs provided the latent positions are i.i.d. from some distribution. If classlabels are observed for a number of vertices tending to inﬁnity, then we showthat the remaining vertices can be classiﬁed with error converging to Bayes opti-mal using the k -nearest-neighbors classiﬁcation rule. We evaluate the proposedmethods on simulated data and a graph derived from Wikipedia. 1 Introduction The classical statistical pattern recognition setting involves( X , Y ),( X 1 , Y 1 ),...,( X n , Y n ) i . i˘ . d . F X , Y ,where the X i : 7!R d are observed feature vectors and the Y i : 7!f0,1gare ob-served class labels for some probability space . We deﬁne D=f( X i , Y i )gas the train-ing set. The goal is to learn a classiﬁer h (;D): R d !f0,1gsuch that the probability oferror P[ h ( X ;D)6= Y jD]approaches Bayes optimal as n !1for all distributions
Many latent space approaches seek to generalize the stochastic blockmodel to allow for variation within blocks. For example, the mixed membership model of @cite_10 posits that a vertex could have partial membership in multiple blocks. In @cite_13 , latent vectors are presumed to be drawn from a mixture of multivariate normal distributions with the link function depending on the distance between the latent vectors. They use Bayesian techniques to estimate the latent vectors.
@cite_13 @cite_10
2096091969 2107107106
Network models are widely used to represent relations between interacting units or actors. Network data often exhibit transitivity, meaning that two actors that have ties to a third actor are more likely to be tied than actors that do not, homophily by attributes of the actors or dyads, and clustering. Interest often focuses on finding clusters of actors or ties, and the number of groups in the data is typically unknown. We propose a new model, the "latent position cluster model", under which the probability of a tie between two actors depends on the distance between them in an unobserved Euclidean 'social space', and the actors' locations in the latent social space arise from a mixture of distributions, each corresponding to a cluster. We propose two estimation methods: a two-stage maximum likelihood method and a fully Bayesian method that uses Markov chain Monte Carlo sampling. The former is quicker and simpler, but the latter performs better. We also propose a Bayesian way of determining the number of clusters that are present by using approximate conditional Bayes factors. Our model represents transitivity, homophily by attributes and clustering simultaneously and does not require the number of clusters to be known. The model makes it easy to simulate realistic networks with clustering, which are potentially useful as inputs to models of more complex systems of which the network is part, such as epidemic models of infectious disease. We apply the model to two networks of social relations. A free software package in the R statistical language, latentnet, is available to analyse data by using the model. Copyright 2007 Royal Statistical Society. Consider data consisting of pairwise measurements, such as presence or absence of links between pairs of objects. These data arise, for instance, in the analysis of protein interactions and gene regulatory networks, collections of author-recipient email, and social networks. Analyzing pairwise measurements with probabilistic models requires special assumptions, since the usual independence or exchangeability assumptions no longer hold. Here we introduce a class of variance allocation models for pairwise measurements: mixed membership stochastic blockmodels. These models combine global parameters that instantiate dense patches of connectivity (blockmodel) with local parameters that instantiate node-specific variability in the connections (mixed membership). We develop a general variational inference algorithm for fast approximate posterior inference. We demonstrate the advantages of mixed membership stochastic blockmodels with applications to social networks and protein interaction networks.