Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
| Autor: | Kasper Green Larsen, Jaroslaw Blasiok, Michael Mitzenmacher, Preetum Nakkiran, Ben Lawson, Charalampos E. Tsourakakis, Vasileios Nakos |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Computer Science - Machine Learning Discrete Mathematics (cs.DM) Applied Mathematics Correlation clustering Breadth-first search Computer Science - Social and Information Networks Disjoint sets Binary logarithm Machine Learning (cs.LG) Combinatorics Computational Mathematics Modeling and Simulation Computer Science - Data Structures and Algorithms FOS: Mathematics Feature (machine learning) Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) Enhanced Data Rates for GSM Evolution Heuristics Computer Science - Discrete Mathematics Sign (mathematics) Mathematics |
| Zdroj: | Internet Mathematics. |
| ISSN: | 1944-9488 |
| DOI: | 10.24166/im.05.2019 |
| Popis: | Social networks involve both positive and negative relationships, which can be captured in signed graphs. The {\em edge sign prediction problem} aims to predict whether an interaction between a pair of nodes will be positive or negative. We provide theoretical results for this problem that motivate natural improvements to recent heuristics. The edge sign prediction problem is related to correlation clustering; a positive relationship means being in the same cluster. We consider the following model for two clusters: 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 Comment: arXiv admin note: text overlap with arXiv:1609.00750 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|