Loading…
Sampling properties of directed networks
For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Althoug...
Saved in:
Published in: | arXiv.org 2012-10 |
---|---|
Main Authors: | , , , , , |
Format: | Article |
Language: | English |
Subjects: | |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
cited_by | |
---|---|
cites | |
container_end_page | |
container_issue | |
container_start_page | |
container_title | arXiv.org |
container_volume | |
creator | Seung-Woo, Son Christensen, Claire Bizhani, Golnoosh Foster, David V Grassberger, Peter Paczuski, Maya |
description | For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Although it is well established that BFS sampling fails, in most cases, to capture the IN-component(s) of directed networks, a description of the effects of BFS sampling on other topological properties are all but absent from the literature. To systematically study the effects of sampling biases on directed networks, we compare BFS sampling to random sampling on complete large-scale directed networks. We present new results and a thorough analysis of the topological properties of seven different complete directed networks (prior to sampling), including three versions of Wikipedia, three different sources of sampled World Wide Web data, and an Internet-based social network. We detail the differences that sampling method and coverage can make to the structural properties of sampled versions of these seven networks. Most notably, we find that sampling method and coverage affect both the bow-tie structure, as well as the number and structure of strongly connected components in sampled networks. In addition, at low sampling coverage (i.e. less than 40%), the values of average degree, variance of out-degree, degree auto-correlation, and link reciprocity are overestimated by 30% or more in BFS-sampled networks, and only attain values within 10% of the corresponding values in the complete networks when sampling coverage is in excess of 65%. These results may cause us to rethink what we know about the structure, function, and evolution of real-world directed networks. |
doi_str_mv | 10.48550/arxiv.1201.1507 |
format | article |
fullrecord | <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2081781650</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2081781650</sourcerecordid><originalsourceid>FETCH-LOGICAL-a510-f413ef6181235f86343868a392be231b743ad266a32b58965eaf7ecbd77c18e83</originalsourceid><addsrcrecordid>eNotjk1Lw0AQQBdBaKm99xjw4iVxZ2Y_pkcpfkHBg72XTTIrqTWJu6n68y3o6d3ee0qtQFeGrdW3If10XxWghgqs9hdqjkRQskGcqWXOB601Oo_W0lzdvIaP8dj1b8WYhlHS1Ekuhli0XZJmkrboZfoe0nu-UpcxHLMs_7lQu4f73eap3L48Pm_utmWwoMtogCQ6YECykR0ZYseB1lgLEtTeUGjRuUBYW147KyF6aerW-wZYmBbq-k973vk8SZ72h-GU-nNxj5rBMzir6RdWFEFZ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2081781650</pqid></control><display><type>article</type><title>Sampling properties of directed networks</title><source>Publicly Available Content Database</source><creator>Seung-Woo, Son ; Christensen, Claire ; Bizhani, Golnoosh ; Foster, David V ; Grassberger, Peter ; Paczuski, Maya</creator><creatorcontrib>Seung-Woo, Son ; Christensen, Claire ; Bizhani, Golnoosh ; Foster, David V ; Grassberger, Peter ; Paczuski, Maya</creatorcontrib><description>For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Although it is well established that BFS sampling fails, in most cases, to capture the IN-component(s) of directed networks, a description of the effects of BFS sampling on other topological properties are all but absent from the literature. To systematically study the effects of sampling biases on directed networks, we compare BFS sampling to random sampling on complete large-scale directed networks. We present new results and a thorough analysis of the topological properties of seven different complete directed networks (prior to sampling), including three versions of Wikipedia, three different sources of sampled World Wide Web data, and an Internet-based social network. We detail the differences that sampling method and coverage can make to the structural properties of sampled versions of these seven networks. Most notably, we find that sampling method and coverage affect both the bow-tie structure, as well as the number and structure of strongly connected components in sampled networks. In addition, at low sampling coverage (i.e. less than 40%), the values of average degree, variance of out-degree, degree auto-correlation, and link reciprocity are overestimated by 30% or more in BFS-sampled networks, and only attain values within 10% of the corresponding values in the complete networks when sampling coverage is in excess of 65%. These results may cause us to rethink what we know about the structure, function, and evolution of real-world directed networks.</description><identifier>EISSN: 2331-8422</identifier><identifier>DOI: 10.48550/arxiv.1201.1507</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Epidemics ; Properties (attributes) ; Random sampling ; Reciprocity ; Social networks ; Topology</subject><ispartof>arXiv.org, 2012-10</ispartof><rights>2012. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2081781650?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>780,784,25753,27925,37012,44590</link.rule.ids></links><search><creatorcontrib>Seung-Woo, Son</creatorcontrib><creatorcontrib>Christensen, Claire</creatorcontrib><creatorcontrib>Bizhani, Golnoosh</creatorcontrib><creatorcontrib>Foster, David V</creatorcontrib><creatorcontrib>Grassberger, Peter</creatorcontrib><creatorcontrib>Paczuski, Maya</creatorcontrib><title>Sampling properties of directed networks</title><title>arXiv.org</title><description>For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Although it is well established that BFS sampling fails, in most cases, to capture the IN-component(s) of directed networks, a description of the effects of BFS sampling on other topological properties are all but absent from the literature. To systematically study the effects of sampling biases on directed networks, we compare BFS sampling to random sampling on complete large-scale directed networks. We present new results and a thorough analysis of the topological properties of seven different complete directed networks (prior to sampling), including three versions of Wikipedia, three different sources of sampled World Wide Web data, and an Internet-based social network. We detail the differences that sampling method and coverage can make to the structural properties of sampled versions of these seven networks. Most notably, we find that sampling method and coverage affect both the bow-tie structure, as well as the number and structure of strongly connected components in sampled networks. In addition, at low sampling coverage (i.e. less than 40%), the values of average degree, variance of out-degree, degree auto-correlation, and link reciprocity are overestimated by 30% or more in BFS-sampled networks, and only attain values within 10% of the corresponding values in the complete networks when sampling coverage is in excess of 65%. These results may cause us to rethink what we know about the structure, function, and evolution of real-world directed networks.</description><subject>Epidemics</subject><subject>Properties (attributes)</subject><subject>Random sampling</subject><subject>Reciprocity</subject><subject>Social networks</subject><subject>Topology</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2012</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNotjk1Lw0AQQBdBaKm99xjw4iVxZ2Y_pkcpfkHBg72XTTIrqTWJu6n68y3o6d3ee0qtQFeGrdW3If10XxWghgqs9hdqjkRQskGcqWXOB601Oo_W0lzdvIaP8dj1b8WYhlHS1Ekuhli0XZJmkrboZfoe0nu-UpcxHLMs_7lQu4f73eap3L48Pm_utmWwoMtogCQ6YECykR0ZYseB1lgLEtTeUGjRuUBYW147KyF6aerW-wZYmBbq-k973vk8SZ72h-GU-nNxj5rBMzir6RdWFEFZ</recordid><startdate>20121013</startdate><enddate>20121013</enddate><creator>Seung-Woo, Son</creator><creator>Christensen, Claire</creator><creator>Bizhani, Golnoosh</creator><creator>Foster, David V</creator><creator>Grassberger, Peter</creator><creator>Paczuski, Maya</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20121013</creationdate><title>Sampling properties of directed networks</title><author>Seung-Woo, Son ; Christensen, Claire ; Bizhani, Golnoosh ; Foster, David V ; Grassberger, Peter ; Paczuski, Maya</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a510-f413ef6181235f86343868a392be231b743ad266a32b58965eaf7ecbd77c18e83</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2012</creationdate><topic>Epidemics</topic><topic>Properties (attributes)</topic><topic>Random sampling</topic><topic>Reciprocity</topic><topic>Social networks</topic><topic>Topology</topic><toplevel>online_resources</toplevel><creatorcontrib>Seung-Woo, Son</creatorcontrib><creatorcontrib>Christensen, Claire</creatorcontrib><creatorcontrib>Bizhani, Golnoosh</creatorcontrib><creatorcontrib>Foster, David V</creatorcontrib><creatorcontrib>Grassberger, Peter</creatorcontrib><creatorcontrib>Paczuski, Maya</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><jtitle>arXiv.org</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Seung-Woo, Son</au><au>Christensen, Claire</au><au>Bizhani, Golnoosh</au><au>Foster, David V</au><au>Grassberger, Peter</au><au>Paczuski, Maya</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Sampling properties of directed networks</atitle><jtitle>arXiv.org</jtitle><date>2012-10-13</date><risdate>2012</risdate><eissn>2331-8422</eissn><abstract>For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Although it is well established that BFS sampling fails, in most cases, to capture the IN-component(s) of directed networks, a description of the effects of BFS sampling on other topological properties are all but absent from the literature. To systematically study the effects of sampling biases on directed networks, we compare BFS sampling to random sampling on complete large-scale directed networks. We present new results and a thorough analysis of the topological properties of seven different complete directed networks (prior to sampling), including three versions of Wikipedia, three different sources of sampled World Wide Web data, and an Internet-based social network. We detail the differences that sampling method and coverage can make to the structural properties of sampled versions of these seven networks. Most notably, we find that sampling method and coverage affect both the bow-tie structure, as well as the number and structure of strongly connected components in sampled networks. In addition, at low sampling coverage (i.e. less than 40%), the values of average degree, variance of out-degree, degree auto-correlation, and link reciprocity are overestimated by 30% or more in BFS-sampled networks, and only attain values within 10% of the corresponding values in the complete networks when sampling coverage is in excess of 65%. These results may cause us to rethink what we know about the structure, function, and evolution of real-world directed networks.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><doi>10.48550/arxiv.1201.1507</doi><oa>free_for_read</oa></addata></record> |
fulltext | fulltext |
identifier | EISSN: 2331-8422 |
ispartof | arXiv.org, 2012-10 |
issn | 2331-8422 |
language | eng |
recordid | cdi_proquest_journals_2081781650 |
source | Publicly Available Content Database |
subjects | Epidemics Properties (attributes) Random sampling Reciprocity Social networks Topology |
title | Sampling properties of directed networks |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T22%3A34%3A37IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Sampling%20properties%20of%20directed%20networks&rft.jtitle=arXiv.org&rft.au=Seung-Woo,%20Son&rft.date=2012-10-13&rft.eissn=2331-8422&rft_id=info:doi/10.48550/arxiv.1201.1507&rft_dat=%3Cproquest%3E2081781650%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a510-f413ef6181235f86343868a392be231b743ad266a32b58965eaf7ecbd77c18e83%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2081781650&rft_id=info:pmid/&rfr_iscdi=true |