[Dmbu-l] Reconstructing graphs form neighborhood data : Friday @ 11:00, MCS 148
cmav at bu.edu
Thu Nov 29 01:10:55 EST 2012
The talk is going to be on Friday (as correctly stated in the subject) and
On Wed, Nov 28, 2012 at 3:13 PM, Charalampos Mavroforakis <cmav at bu.edu>wrote:
> Hi everyone. Dora will give a prep talk tomorrow for ICDM . Here is the
> Consider a social network and suppose that we are given the number of
> friends between each pair of users. Can we reconstruct the underlying
> Similarly, consider a set of documents and the words that appear in them.
> If we
> know the number of common words for every pair of documents, as well as the
> number of common documents for every pair of words, can we infer which
> appear in which documents? In this paper, we develop a general methodology
> answering questions like the ones above. We formalize these questions in
> what we
> call the Reconstruction problem: Given information about the common
> of nodes in a network, our goal is to reconstruct the hidden binary matrix
> indicates the presence or absence of relationships between individual
> We propose an effective and practical heuristic, which
> exploits properties of the singular value decomposition of the hidden
> matrix. More specifically, we show that using the available neighborhood
> information, we can reconstruct the hidden matrix by finding the
> components of
> its singular value decomposition and then combining them appropriately. Our
> extensive experimental study suggests that our methods are able to
> binary matrices of different characteristics with up to 100% accuracy.
> This is a joint work with Evimaria Terzi and Rainer Gemulla from MPI.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Dmbu-l