A streaming sampling algorithm for social activity networks using fixed structure learning automata

摘要

Social activity networks are formed from activities among users (such as wall posts, tweets, emails, and etc.), where any activity between two users results in an addition of an edge to the network graph. These networks are streaming and include massive volume of edges. A streaming graph is considered to be a stream of edges that continuously evolves over time. This paper proposes a sampling algorithm for social activity networks, implemented in a streaming fashion. The proposed algorithm utilizes a set of fixed structure learning automata. Each node of the original activity graph is equipped with a learning automaton which decides whether its corresponding node should be added to the sample set or not. The proposed algorithm is compared with the best streaming sampling algorithm reported so far in terms of Kolmogorov-Smirnov (KS) test and normalized L-1 and L-2 distances over real-world activity networks and synthetic networks presented as a sequence of edges. The experimental results show the superiority of the proposed algorithm.