[cs-talks] Data-X Seminar, 9/22 @ MCS 180

Harrington, Jacob Walter jwharrin at bu.edu
Wed Sep 20 12:43:23 EDT 2017


Predicting Positive and Negative Links with Noisy Queries: Theory & Practice<https://tsourakakis.com/social-media/>
Professor Charalampos Tsourakakis
Data-X Group Seminar, Friday, September 22, 2017 at 1pm in Hariri Seminar Room


Abstract: In this talk, I will present some recent results on an important graph mining problem known as the edge sign prediction problem: can we predict whether an interaction between a pair of nodes will be positive or negative? We model the edge sign prediction problem as follows: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0<q<\frac{1}{2}$. Let $\delta=1-2q$ be the bias. We provide an algorithm that recovers all signs correctly with high probability in the presence of noise for any constant gap $\delta$ with $O(\frac{n\log n}{\delta^4})$ queries. Our algorithm uses breadth first search as its main algorithmic primitive. A byproduct of our proposed learning algorithm is the use of $s-t$ paths as an informative feature to predict the sign of the edge $(s,t)$. As a heuristic, we use edge disjoint $s-t$ paths of short length as a feature for predicting edge signs in real-world signed networks. Our findings suggest that the use of paths improves the classification accuracy of state-of-the-art classifiers, especially for pairs of nodes with no common neighbors. Time permitting, I will discuss a new state-of-the-art approach to community detection in social networks.

This is joint work with Michael Mitzenmacher (Harvard University), Jarosław Błasiok (Harvard University), Ben Lawson (Boston University), Preetum Nakkiran (Harvard University), Vasileios Nakos (Harvard University)

The paper will appear on Arxiv in a few days from now.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20170920/3920d55c/attachment.html>


More information about the cs-talks mailing list