One of the current practical, useful but sensitive topic in social networks is polling problemwhere the privacy of exchanged information and user reputation are very critical. Indeed, userswant to preserve the confidentiality of their votes and to hide, if any, their misbehaviors. Recently,Guerraoui et al. proposed polling protocols based on simple secret sharing scheme and withoutrequiring any central authority or cryptography system. However these protocols can be deployedsafely and efficiently provided that the social graph structure should be transformed into a ringstructure-based overlay and the number of participating users is perfect square. In this thesis,we address the problem of deploying decentralized polling protocols for general social graphsand how to transform these graphs in order to increase the privacy and/or accuracy properties.First, we propose three simple decentralized polling protocols that rely on the current state ofsocial graphs. The two first protocols use synchronous and asynchronous models and verificationprocedures to detect the misbehaving users. The third protocol is an asynchronous one thatdoes not require any verification procedures and contains a method for efficiently broadcastingmessage under a family of social graphs satisfying what we call the m-broadcasting property.Second, we formalize the “adding friends” problem such that we can reuse the social graphs aftersome minimum structural modifications consisting in adding new friendship relations. We alsodevise algorithms for solving this problem in centralized and decentralized networks. We validateour solutions with some performance evaluations which show that our protocols are accurate,and inside the theoretical bounds.

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000637 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000637 | SxmlIndent | more

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:tel-01139325
   |texte=   On the Polling Problem for Decentralized Social Networks
}}