On Constrained Adding Friends in Social Networks

Hoang Bao Thien 1 Abdessamad Imine 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Online social networks are currently experiencing a peak and they resemble real platforms of social conversion and content delivery. Indeed, they are exploited in many ways: from conducting public opinion polls about any political issue to planning big social events for a large public. To securely perform these large-scale computations, current protocols use a simple secret sharing scheme which enables users to obfuscate their inputs. However, these protocols require a minimum number of friends, i.e. the minimum degree of the social graph should be not smaller than a given threshold. Often this condition is not satisfied by all social graphs. Yet we can reuse these graphs after some structural modifications consisting in adding new friendship relations. In this paper, we provide the first definition and theoretical analysis of the ''\emph{adding friends}'' problem. We formally describe this problem that, given a graph $G$ and parameter $c$, asks for the graph satisfying the threshold $c$ that results from $G$ with the minimum of edge-addition operations. We present algorithms for solving this problem in centralized social networks. An experimental evaluation on real-world social graphs demonstrates that our protocols are accurate and inside the theoretical bounds.
Type de document :
Communication dans un congrès
Adam Jatowt and Ee-Peng Lim and Ying Ding and Asako Miura and Taro Tezuka and Gaël Dias and Katsumi Tanaka and Andrew J. Flanagin and Bing Tian Dai. SocInfo - The 5th International Conference on Social Informatics - 2013, Nov 2013, Kyoto, Japan. Springer, 8238, pp.467-477, 2013, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-319-03260-3_40〉. 〈10.1007/978-3-319-03260-3_40〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00916037
Contributeur : Hoang Bao Thien <>
Soumis le : lundi 9 décembre 2013 - 16:21:31
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10

Identifiants

Citation

Hoang Bao Thien, Abdessamad Imine. On Constrained Adding Friends in Social Networks. Adam Jatowt and Ee-Peng Lim and Ying Ding and Asako Miura and Taro Tezuka and Gaël Dias and Katsumi Tanaka and Andrew J. Flanagin and Bing Tian Dai. SocInfo - The 5th International Conference on Social Informatics - 2013, Nov 2013, Kyoto, Japan. Springer, 8238, pp.467-477, 2013, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-319-03260-3_40〉. 〈10.1007/978-3-319-03260-3_40〉. 〈hal-00916037〉

Partager

Métriques

Consultations de la notice

261