Sampling Community Structure in Dynamic Social Networks

摘要

When studying dynamic networks, it is often of interest to understand how the community structure of the network changes. However, before studying the community structure of dynamic social networks, one must first collect appropriate network data. In this paper we present a network sampling technique to crawl the community structure of dynamic networks when there is a limitation on the number of nodes that can be queried. The process begins by obtaining a sample for the first time step. In subsequent time steps, the crawling process is guided by community structure discoveries made in the past. Experiments conducted on the proposed approach and certain baseline techniques reveal the proposed approach has at least 35% performance increase in cases when the total query budget is fixed over the entire period and at least 8% increase in cases when the query budget is fixed per time step.