Cargando…

A partial knowledge of friends of friends speeds social search

Milgram empirically showed that people knowing only connections to their friends could locate any person in the U.S. in a few steps. Later research showed that social network topology enables a node aware of its full routing to find an arbitrary target in even fewer steps. Yet, the success of people...

Descripción completa

Detalles Bibliográficos
Autores principales: Elsisy, Amr, Szymanski, Boleslaw K., Plum, Jasmine A., Qi, Miao, Pentland, Alex
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8376299/
https://www.ncbi.nlm.nih.gov/pubmed/34412110
http://dx.doi.org/10.1371/journal.pone.0255982
_version_ 1783740465157242880
author Elsisy, Amr
Szymanski, Boleslaw K.
Plum, Jasmine A.
Qi, Miao
Pentland, Alex
author_facet Elsisy, Amr
Szymanski, Boleslaw K.
Plum, Jasmine A.
Qi, Miao
Pentland, Alex
author_sort Elsisy, Amr
collection PubMed
description Milgram empirically showed that people knowing only connections to their friends could locate any person in the U.S. in a few steps. Later research showed that social network topology enables a node aware of its full routing to find an arbitrary target in even fewer steps. Yet, the success of people in forwarding efficiently knowing only personal connections is still not fully explained. To study this problem, we emulate it on a real location-based social network, Gowalla. It provides explicit information about friends and temporal locations of each user useful for studies of human mobility. Here, we use it to conduct a massive computational experiment to establish new necessary and sufficient conditions for achieving social search efficiency. The results demonstrate that only the distribution of friendship edges and the partial knowledge of friends of friends are essential and sufficient for the efficiency of social search. Surprisingly, the efficiency of the search using the original distribution of friendship edges is not dependent on how the nodes are distributed into space. Moreover, the effect of using a limited knowledge that each node possesses about friends of its friends is strongly nonlinear. We show that gains of such use grow statistically significantly only when this knowledge is limited to a small fraction of friends of friends.
format Online
Article
Text
id pubmed-8376299
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-83762992021-08-20 A partial knowledge of friends of friends speeds social search Elsisy, Amr Szymanski, Boleslaw K. Plum, Jasmine A. Qi, Miao Pentland, Alex PLoS One Research Article Milgram empirically showed that people knowing only connections to their friends could locate any person in the U.S. in a few steps. Later research showed that social network topology enables a node aware of its full routing to find an arbitrary target in even fewer steps. Yet, the success of people in forwarding efficiently knowing only personal connections is still not fully explained. To study this problem, we emulate it on a real location-based social network, Gowalla. It provides explicit information about friends and temporal locations of each user useful for studies of human mobility. Here, we use it to conduct a massive computational experiment to establish new necessary and sufficient conditions for achieving social search efficiency. The results demonstrate that only the distribution of friendship edges and the partial knowledge of friends of friends are essential and sufficient for the efficiency of social search. Surprisingly, the efficiency of the search using the original distribution of friendship edges is not dependent on how the nodes are distributed into space. Moreover, the effect of using a limited knowledge that each node possesses about friends of its friends is strongly nonlinear. We show that gains of such use grow statistically significantly only when this knowledge is limited to a small fraction of friends of friends. Public Library of Science 2021-08-19 /pmc/articles/PMC8376299/ /pubmed/34412110 http://dx.doi.org/10.1371/journal.pone.0255982 Text en © 2021 Elsisy et al https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Elsisy, Amr
Szymanski, Boleslaw K.
Plum, Jasmine A.
Qi, Miao
Pentland, Alex
A partial knowledge of friends of friends speeds social search
title A partial knowledge of friends of friends speeds social search
title_full A partial knowledge of friends of friends speeds social search
title_fullStr A partial knowledge of friends of friends speeds social search
title_full_unstemmed A partial knowledge of friends of friends speeds social search
title_short A partial knowledge of friends of friends speeds social search
title_sort partial knowledge of friends of friends speeds social search
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8376299/
https://www.ncbi.nlm.nih.gov/pubmed/34412110
http://dx.doi.org/10.1371/journal.pone.0255982
work_keys_str_mv AT elsisyamr apartialknowledgeoffriendsoffriendsspeedssocialsearch
AT szymanskiboleslawk apartialknowledgeoffriendsoffriendsspeedssocialsearch
AT plumjasminea apartialknowledgeoffriendsoffriendsspeedssocialsearch
AT qimiao apartialknowledgeoffriendsoffriendsspeedssocialsearch
AT pentlandalex apartialknowledgeoffriendsoffriendsspeedssocialsearch
AT elsisyamr partialknowledgeoffriendsoffriendsspeedssocialsearch
AT szymanskiboleslawk partialknowledgeoffriendsoffriendsspeedssocialsearch
AT plumjasminea partialknowledgeoffriendsoffriendsspeedssocialsearch
AT qimiao partialknowledgeoffriendsoffriendsspeedssocialsearch
AT pentlandalex partialknowledgeoffriendsoffriendsspeedssocialsearch