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

Charalampos Mavroforakis cmav at bu.edu
Wed Nov 28 15:13:57 EST 2012


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/20121128/7ce38405/attachment.html>


More information about the Dmbu-l mailing list