New interface

# On Constrained Adding Friends in Social Networks

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.
Keywords :
Document type :
Conference papers

https://hal.inria.fr/hal-00916037
Contributor : Hoang Bao Thien Connect in order to contact the contributor
Submitted on : Monday, December 9, 2013 - 4:21:31 PM
Last modification on : Friday, January 21, 2022 - 3:09:01 AM

### Citation

Hoang Bao Thien, Abdessamad Imine. On Constrained Adding Friends in Social Networks. SocInfo - The 5th International Conference on Social Informatics - 2013, Nov 2013, Kyoto, Japan. pp.467-477, ⟨10.1007/978-3-319-03260-3_40⟩. ⟨hal-00916037⟩

Record views