Passer au contenu principal

Recherche

Afficher tous les résultats pour

Accueil

Publication

Towards Unbiased BFS Sampling

À propos
Confidentialité
Mentions légales

Copyright © 2025 EPFL, tous droits réservés

Graph Chatbot

Patrick Thiran, Maciej Kurant
2011

Résumé

Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify and correct the degree bias of BFS.

Source officielle

https://infoscience.epfl.ch/entities/publication/8de04969-e485-4a3c-a79f-ad364dc50443

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (23)

Quantification (logique)

vignette|Symboles mathématiques des deux quantificateurs logiques les plus courants.|236px En mathématiques, les expressions « pour tout » (ou « quel que soit ») et « il existe », utilisées pour formuler des propositions mathématiques dans le calcul des prédicats, sont appelées des quantifications. Les symboles qui les représentent en langage formel sont appelés des quantificateurs (ou autrefois des quanteurs). La quantification universelle (« pour tout ... » ou « quel que soit ... ») se dénote par le symbole ∀ (un A à l'envers).

Biais de sélection

Dans une étude statistique, le terme biais de sélection désigne une erreur systématique faite lors de la sélection des sujets à étudier. Ce terme regroupe tous les biais pouvant conduire à ce que les sujets effectivement observés lors d'une enquête ne constituent pas un groupe représentatif des populations censées être étudiées et ne permettent donc pas de répondre aux questions posées dans le protocole. Les biais de sélection se produisent lors de l'échantillonnage, c'est-à-dire lors de la sélection d'un échantillon représentatif de la population étudiée.

Échantillon biaisé

En statistiques, le mot biais a un sens précis qui n'est pas tout à fait le sens habituel du mot. Un échantillon biaisé est un ensemble d'individus d'une population, censé la représenter, mais dont la sélection des individus a introduit un biais qui ne permet alors plus de conclure directement pour l'ensemble de la population. Un échantillon biaisé n'est donc pas un échantillon de personnes biaisées (bien que ça puisse être le cas) mais avant tout un échantillon sélectionné de façon biaisée.

Publications associées (27)

It’s All Relative: Learning Interpretable Models for Scoring Subjective Bias in Documents from Pairwise Comparisons

Matthias Grossglauser, Aswin Suresh, Chi Hsuan Wu

We propose an interpretable model to score the subjective bias present in documents, based only on their textual content. Our model is trained on pairs of revisions of the same Wikipedia article, where one version is more biased than the other. Although pr ...

2024

Exploiting the Signal-Leak Bias in Diffusion Models

Sabine Süsstrunk, Radhakrishna Achanta, Mahmut Sami Arpa, Martin Nicolas Everaert, Athanasios Fitsios

There is a bias in the inference pipeline of most diffusion models. This bias arises from a signal leak whose distribution deviates from the noise distribution, creating a discrepancy between training and inference processes. We demonstrate that this signa ...

2024

Biases in Information Selection and Processing: Survey Evidence from the Pandemic

We conduct two survey experiments to study which information people choose to consume and how it affects their beliefs. In the first experiment, respondents choose between optimistic and pessimistic article headlines related to the COVID-19 pandemic and ar ...

2024