Biased sampling from facebook multilayer activity network using learning automata

摘要

Although much research has been devoted to unbiased sampling of various networks, bias is not always disadvantageous, but sometimes useful. Especially for many real-world applications such as detecting influential nodes, spam users, and the most trustful people, it is preferred to sample users with special properties. Since sampling from friendship network alone cannot collect these important nodes appropriately, one may use interactions occurred among users. This paper deals with biased sampling of multilayer activity network. The proposed method initially learns the transition probabilities according to the considered application using learning automata. Then we sample the graph by running an application-based random walk following the learnt probabilities, in order to be guided to suitable nodes and collect their information. At last, the performance of the proposed method in terms of different applications such as fame, spam, and trust is evaluated and compared with those of common sampling algorithms. According to the experiments done, biased sampling method based on learning automata outperforms all other sampling approaches including simple random walk, Metropolis-Hastings random walk, BFS, forest fire, degree, and uniform sampling in terms of all the evaluation measures. To the best of our knowledge, our method is the first and only biased sampling method which can be used in a multilayer activity network.