{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T19:33:12Z","timestamp":1777059192412,"version":"3.51.4"},"reference-count":109,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and\/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete understanding of network sampling is critical to support the field of network science. In this paper, we outline a framework for the general problem of network sampling by highlighting the different objectives, population and units of interest, and classes of network sampling methods. In addition, we propose a spectrum of computational models for network sampling methods, ranging from the traditionally studied model based on the assumption of a static domain to a more challenging model that is appropriate for streaming domains. We design a family of sampling methods based on the concept of graph induction that generalize across the full spectrum of computational models (from static to streaming) while efficiently preserving many of the topological properties of the input graphs. Furthermore, we demonstrate how traditional static sampling algorithms can be modified for graph streams for each of the three main classes of sampling methods: node, edge, and topology-based sampling. Experimental results indicate that our proposed family of sampling methods more accurately preserve the underlying properties of the graph in both static and streaming domains. Finally, we study the impact of network sampling algorithms on the parameter estimation and performance evaluation of relational classification algorithms.<\/jats:p>","DOI":"10.1145\/2601438","type":"journal-article","created":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T14:20:23Z","timestamp":1416320423000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":153,"title":["Network Sampling"],"prefix":"10.1145","volume":"8","author":[{"given":"Nesreen K.","family":"Ahmed","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer","family":"Neville","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramana","family":"Kompella","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134271.1134277"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases. 81--92","author":"Aggarwal C. C."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920964"},{"key":"e_1_2_1_4_1","volume-title":"SIAM International Conference on Data Mining. 478--489","author":"Aggarwal C."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767885"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164180"},{"key":"e_1_2_1_7_1","volume-title":"Advances in Database Systems","volume":"31","author":"Ed Charu C.","year":"2007"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830252.1830253"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2351316.2351324"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2nd Workshop on Information in Networks.","author":"Ahmed N. K."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International AAAI Conference on Weblogs and Social Media. 1--4.","author":"Ahmed N. K."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242685"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687710"},{"key":"e_1_2_1_15_1","unstructured":"J. I. Alvarez-Hamelin L. Dall\u2019Asta A. Barrat and A. Vespignani. 2005. k-core decomposition of Internet graphs: Hierarchies self-similarity and measurement biases. arXiv preprint cs\/0511007 (2005).  J. I. Alvarez-Hamelin L. Dall\u2019Asta A. Barrat and A. Vespignani. 2005. k-core decomposition of Internet graphs: Hierarchies self-similarity and measurement biases. arXiv preprint cs\/0511007 (2005)."},{"key":"e_1_2_1_16_1","volume-title":"Algorithms and Models for the Web-Graph. Lecture Notes in Computer Science","volume":"6516","author":"Avrachenkov K."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 633--634","author":"Babcock B."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963492"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187907"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 623--632","author":"Bar-Yossef Z."},{"key":"e_1_2_1_22_1","unstructured":"E. Baykan M. Henzinger S. F. Keller S. De Castelberg and M. Kinzler. 2009. A comparison of techniques for sampling web pages. Arxiv preprint arXiv:0902.1604 (2009).  E. Baykan M. Henzinger S. F. Keller S. De Castelberg and M. Kinzler. 2009. A comparison of techniques for sampling web pages. Arxiv preprint arXiv:0902.1604 (2009)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00569-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_27_1","volume-title":"SIAM International Conference on Data Mining. 442--446","author":"Chakrabarti D."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages and Programming. 693--703","author":"Charikar M."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.67"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International AAAI Conference on Weblogs and Social Media. 89--96","author":"Conover M."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065201"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339572"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International AAAI Conference on Weblogs and Social Media. 34--41","author":"Choudhury M. De"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347107"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases -","volume":"30","author":"Fan W.","year":"2004"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014069"},{"key":"e_1_2_1_37_1","volume-title":"SIAM International Conference on Data Mining. 457--461","author":"Fan W."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-3758(77)90011-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/1402403"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/270740"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 16th International Joint Conference on Artificial Intelligence. 1300--1309","author":"Friedman N."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1083784.1083789"},{"key":"e_1_2_1_43_1","volume-title":"SIAM International Conference on Data Mining. 3--14","author":"Gao J."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0811113106"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9531.2010.01223.x"},{"key":"e_1_2_1_46_1","volume-title":"IEEE International Conference on Computer Communications. 1--9.","author":"Gjoka M."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_2_1_48_1","volume-title":"IEEE International Conference on Computer Communications. 1--12","author":"Gkantsidis C."},{"key":"e_1_2_1_49_1","unstructured":"David F. Gleich. 2012. Graph of Flickr Photo-Sharing Social Network Crawled in May 2006. (Feb 2012). https:\/\/research.hub.purdue.edu\/publications\/1002.  David F. Gleich. 2012. Graph of Flickr Photo-Sharing Social Network Crawled in May 2006. (Feb 2012). https:\/\/research.hub.purdue.edu\/publications\/1002."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177705148"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1086\/226224"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198387"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00199-2"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731356"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.2307\/3096941"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00055-4"},{"key":"e_1_2_1_58_1","volume-title":"External Memory Algorithms: Dimacs Workshop External Memory and Visualization","volume":"50","author":"Henzinger M."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502529"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2010.11.033"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.151"},{"key":"e_1_2_1_63_1","volume-title":"Computing and Combinatorics. Lecture Notes in Computer Science","volume":"1627","author":"Kleinberg J."},{"key":"e_1_2_1_64_1","unstructured":"E. D. Kolaczyk. 2009. Statistical Analysis of Network Data. Springer Chapter 5: Sampling and Estimation in Network Graphs 123--152.  E. D. Kolaczyk. 2009. Statistical Analysis of Network Data. Springer Chapter 5: Sampling and Estimation in Network Graphs 123--152."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090193.1090199"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2007.06.004"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111005"},{"key":"e_1_2_1_69_1","unstructured":"Justin Lafferty. 2012. Facebook Users Worldwide: 3.2 Billion Likes And Comments Per Day. http:\/\/allfacebook.com\/facebook-marketing-infographic-engagement_b98277. (August 2012).  Justin Lafferty. 2012. Facebook Users Worldwide: 3.2 Billion Likes And Comments Per Day. http:\/\/allfacebook.com\/facebook-marketing-infographic-engagement_b98277. (August 2012)."},{"key":"e_1_2_1_70_1","volume-title":"IEEE International Conference on Computer Communications. 332--341","author":"Lakhina A."},{"key":"e_1_2_1_71_1","unstructured":"L. Lee. 2001. On the effectiveness of the skew divergence for statistical language analysis. In Artificial Intelligence and Statistics. 65--72.  L. Lee. 2001. On the effectiveness of the skew divergence for statistical language analysis. In Artificial Intelligence and Statistics. 65--72."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.016102"},{"key":"e_1_2_1_73_1","unstructured":"SNAP. 2013. Stanford Network Analysis Project. http:\/\/snap.stanford.edu\/data\/.  SNAP. 2013. Stanford Network Analysis Project. http:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_75_1","volume-title":"SIAM International Conference on Data Mining. 259--270","author":"Li X."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_13"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248659.1248693"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772762"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020431"},{"key":"e_1_2_1_80_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. 346--357","author":"Singh Gurmeet","year":"2002"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","unstructured":"A. McGregor. 2009. Graph mining on streams. Encyclopedia of Database Systems Springer 1271--1275.  A. McGregor. 2009. Graph mining on streams. Encyclopedia of Database Systems Springer 1271--1275.","DOI":"10.1007\/978-0-387-39940-9_184"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan. 2005. Data streams: Algorithms and applications. Now Publishers Inc.  S. Muthukrishnan. 2005. Data streams: Algorithms and applications. Now Publishers Inc.","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.50"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.89.208701"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.254"},{"key":"e_1_2_1_87_1","volume-title":"IEEE International Conference on Computer Communications. 2701--2705","author":"Rasti A. H."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100510050359"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30217-6_1"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.5555\/2444851.2444861"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376928"},{"key":"e_1_2_1_93_1","doi-asserted-by":"crossref","unstructured":"P. Sen G. Namata M. Bilgic L. Getoor B. Galligher and T. Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29 3 (2008) 93--106.  P. Sen G. Namata M. Bilgic L. Getoor B. Galligher and T. Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29 3 (2008) 93--106.","DOI":"10.1609\/aimag.v29i3.2157"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450149"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0501179102"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/1177080.1177084"},{"key":"e_1_2_1_97_1","volume-title":"Proceedings of the 17th International Joint Conference on Artificial Intelligence -","volume":"2","author":"Taskar B."},{"key":"e_1_2_1_98_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases -","volume":"29","author":"Tatbul N."},{"key":"e_1_2_1_99_1","volume-title":"Proceedings of the 28th International Conference on Machine Learning. 793--800","author":"Vattani A."},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956778"},{"key":"e_1_2_1_103_1","doi-asserted-by":"crossref","unstructured":"H. Wang P. S. Yu and J. Han. 2010. Data Mining and Knowledge Discovery Handbook. Springer Chapter 40: Mining Concept-Drifting Data Streams 789--802.  H. Wang P. S. Yu and J. Han. 2010. Data Mining and Knowledge Discovery Handbook. Springer Chapter 40: Mining Concept-Drifting Data Streams 789--802.","DOI":"10.1007\/978-0-387-09823-4_40"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.2307\/800824"},{"key":"e_1_2_1_105_1","doi-asserted-by":"crossref","unstructured":"Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393 6684 (1998) 440--442.  Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393 6684 (1998) 440--442.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772790"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1109\/APWeb.2010.10"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.75.046114"},{"key":"e_1_2_1_110_1","doi-asserted-by":"crossref","unstructured":"J. Zhang. 2010. Managing and Mining Graph Data. Springer Chapter 13: A survey on streaming algorithms for massive graphs 393--420.  J. Zhang. 2010. Managing and Mining Graph Data. Springer Chapter 13: A survey on streaming algorithms for massive graphs 393--420.","DOI":"10.1007\/978-1-4419-6045-0_13"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601438","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:53Z","timestamp":1750276853000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601438"}},"subtitle":["From Static to Streaming Graphs"],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":109,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2601438"],"URL":"https:\/\/doi.org\/10.1145\/2601438","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}