DE-crawler: A densification-expansion algorithm for online data collection

Katchaguy Areekijseree, Sucheta Soundarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Over the past two decades, online social networks have attracted a great deal of attention from researchers. However, before one can gain insight into the behavior or structure of a network, one must first collect appropriate data. Data collection poses several challenges, such as API or bandwidth limits, which require the data collector to carefully consider which queries to make. Many network crawling methods have been proposed; however, their performance depends on network structure. In particular, our previous work in [1] has shown that existing algorithms tend to either (1) Do well at exploring dense areas of a network, but have difficulty in transitioning to new areas of the network, or (2) Easily move between network regions, but fail to fully explore each region. In this work, we introduce DE-Crawler, a novel network crawler that attempts to capture the best of both worlds. DE-Crawler consists of two main stages: Densification, in which the crawler aims to find as many nodes as possible in the current dense region (or community), and Expansion, in which the crawler tries to escape from its current region and move to another dense region. We show that DE-Crawler performs well across networks with different structural properties, outperforming baseline algorithms by up to 28%.

Original languageEnglish (US)
Title of host publicationProceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
EditorsAndrea Tagarelli, Chandan Reddy, Ulrik Brandes
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages164-169
Number of pages6
ISBN (Electronic)9781538660515
DOIs
StatePublished - Oct 24 2018
Event10th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018 - Barcelona, Spain
Duration: Aug 28 2018Aug 31 2018

Other

Other10th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018
CountrySpain
CityBarcelona
Period8/28/188/31/18

    Fingerprint

ASJC Scopus subject areas

  • Sociology and Political Science
  • Communication
  • Computer Networks and Communications
  • Information Systems and Management

Cite this

Areekijseree, K., & Soundarajan, S. (2018). DE-crawler: A densification-expansion algorithm for online data collection. In A. Tagarelli, C. Reddy, & U. Brandes (Eds.), Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018 (pp. 164-169). [8508311] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASONAM.2018.8508311