Search

Your search keyword '"Peleg, David"' showing total 4 results
Start Over Author "Peleg, David" Language french
4 results on '"Peleg, David"'

1. Attachement préférentiel comme unique équilibre

Author

Avin, Chen, Cohen, Avi, Fraigniaud, Pierre, Lotker, Zvi, Peleg, David, Ben-Gurion University of the Negev (BGU), Weizmann Institute of Science [Rehovot, Israël], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Weizmann Institute of Science, and Fraigniaud, Pierre

Subjects
[INFO.INFO-WB] Computer Science [cs]/Web, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-SI] Computer Science [cs]/Social and Information Networks [cs.SI], [INFO.INFO-WB]Computer Science [cs]/Web, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI]
Abstract

International audience; Cet article démontre que la règle de l'attachement préférentiel apparait comme *unique* équilibre de Nash d'un jeu naturel de formation de réseaux sociaux. Dans ce jeu, les nœuds se joignent au réseau l'un après l'autre, et chaque nœud souhaite maximiser son degré ultime, ce dernier représentant son capital social dans la "société" composée des nœuds et de leurs connexions. Ce résultat fournit un argument formel supplémentaire en faveur de l'utilisation du modèle de l'attachement préférentiel, conçu initialement pour capturer le mécanisme intuitif selon lequel les plus favorisés tendent à accroître leur avantage sur les autres acteurs.

Published
2018

2. Construction locale de sous-graphes couvrants peu denses

Author

Gavoille, Cyril, Derbel, Bilel, Peleg, David, Viennot, Laurent, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Sciences et Technologies - Bordeaux 1, Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Parallel Cooperative Multi-criteria Optimization (DOLPHIN), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract

National audience

Published
2008

3. Exploration par un automate fini de réseaux anonymes étiquetés

Author

Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David, Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and Les deuxièmes et troisièmes auteurs ont reçu le support des projets Fragile de de l'ACI Sécurité Informatique, PairAPair de l'ACI Masse de Données, et Grand Large de l'INRIA.

Subjects
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à explorer chacun des n{\oe}uds du réseau. Il a été montré que, pour tout robot $\cR$ à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ n{\oe}uds que $\cR$ ne réussit pas à explorer. Ce papier s'intéresse à la possibilité d'aider le robot en ajoutant des étiquettes de petite taille aux n{\oe}uds grâce à un calcul préalable. Nous décrivons un algorithme d'exploration qui, étant donné des étiquettes appropriées sur 2~bits (en fait des étiquettes de trois valeurs différentes), permet à un robot d'explorer tous les réseaux. De plus, nous décrivons un algorithme linéaire calculant un tel étiquetage. Nous montrons également comment modifier notre méthode d'étiquetage afin qu'un robot puisse explorer tous les réseaux de degré constant, avec des étiquettes de seulement 1~bit (donc des étiquettes de deux valeurs différentes seulement). Autrement dit, alors qu'il n'existe pas de robot capable d'explorer tous les réseaux (non étiquetés) de degré maximum~3, il existe un robot $\cR^*$ et un moyen de colorier les n{\oe}uds en noir et blanc tel que $\cR^*$ réussit à explorer tous les réseaux coloriés de degré maximum~3.

Published
2005

4. Exploration de réseaux par un robot

Author

Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), P. Fraigniaud and D. Ilcinkas are supported by the project ``PairAPair' of the ACI Masses de Données, A.~Pelc is supported in part by NSERC grant OGP 0008136 and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais., and Ilcinkas, David

Subjects
[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le réseau est anonyme, au sens que les nœuds ne disposent pas nécessairement d'un étiquetage global. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à traverser chacun des liens du réseau. Nous montrons que, pour tout robot à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ nœuds que le robot ne réussit pas à explorer. Cette borne $K+1$ améliore toutes les bornes connues jusqu'aujourd'hui. Nous montrons également que, pour explorer tous les graphes de diamètre $D$ et de degré maximum $d$, un robot doit disposer de $\Omega(D\log{d})$ bits de mémoire, et ce même si l'on restreint l'exploration aux réseaux planaires. Enfin, nous montrons que cette borne est asymptotiquement optimale, en décrivant un algorithme qui permet à un robot possédant une mémoire de $O(D\log{d})$ bits d'explorer tous les réseaux de diamètre $D$ et de degré maximum $d$. Ceci nous permet donc de conclure que la complexité mémoire du problème de l'exploration de réseaux est $\Theta(D\log{d})$ bits.

Published
2004

Catalog

Books, media, physical & digital resources
See catalog results