TY - JOUR AU - Laishram, Ricky AU - Wendt, Jeremy D. AU - Soundarajan, Sucheta PY - 2019/07/17 Y2 - 2024/03/28 TI - Crawling the Community Structure of Multiplex Networks JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: AI and the Web DO - 10.1609/aaai.v33i01.3301168 UR - https://ojs.aaai.org/index.php/AAAI/article/view/3782 SP - 168-175 AB - <p>We examine the problem of crawling the community structure of a multiplex network containing multiple layers of edge relationships. While there has been a great deal of work examining community structure in general, and some work on the problem of sampling a network to preserve its community structure, to the best of our knowledge, this is the first work to consider this problem on multiplex networks. We consider the specific case in which the layers of a multiplex network have different query (collection) costs and reliabilities; and a data collector is interested in identifying the community structure of the most expensive layer. We propose <em>MultiComSample</em> (MCS), a novel algorithm for crawling a multiplex network. MCS uses multiple levels of multi-armed bandits to determine the best layers, communities and node roles for selecting nodes to query. We test MCS against six baseline algorithms on real-world multiplex networks, and achieved large gains in performance. For example, after consuming a budget equivalent to sampling 20% of the nodes in the expensive layer, we observe that MCS outperforms the best baseline by up to 49%.</p> ER -