[Dmbu-l] Reconstructing graphs form neighborhood data : Friday @ 11:00, MCS 148

Charalampos Mavroforakis 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
not tomorrow.

- Harry


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
> abstract.
>
>
> Abstract:
> Consider a social network and suppose that we are given the number of
> common
> friends between each pair of users. Can we reconstruct the underlying
> network?
> 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
> words
> appear in which documents? In this paper, we develop a general methodology
> for
> answering questions like the ones above. We formalize these questions in
> what we
> call the Reconstruction problem: Given information about the common
> neighbors
> of nodes in a network, our goal is to reconstruct the hidden binary matrix
> that
> indicates the presence or absence of relationships between individual
> nodes.
> We propose an effective and practical heuristic, which
> exploits properties of the singular value decomposition of the hidden
> binary
> 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
> reconstruct
> 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...
URL: <http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20121129/80782dba/attachment.html>


More information about the Dmbu-l mailing list