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...
Autores principales: | , , , , |
---|---|
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 |