Social Network Sampling
Social Network Sampling
复制标题
DOI：
10.1007/978-3-030-10767-3_4
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Alireza Rezvanian;Behnaz Moradabadi;Mina Ghavipour;M. D. Khomami;M. Meybodi
中科院分区：
文献类型：
--
作者：
Alireza Rezvanian;Behnaz Moradabadi;Mina Ghavipour;M. D. Khomami;M. Meybodi
在本章中，我们重点关注对代表性子图进行缩小采样的目标，以解决从社交网络中采样子图的问题，并回顾文献中最近的社交网络采样方法。然后，我们介绍了四种采样算法，包括 DLAS、EDLAS、ICLA-NS 和 FLAS，它们利用学习自动机从在线社交网络中生成代表性子图。 DLAS 和 EDLAS 分别针对确定性网络和随机网络使用分布式学习自动机和扩展分布式学习自动机。 ICLA-NS算法是一种具有后处理阶段的扩展采样算法，它利用不规则元胞学习自动机（ICLA）来保证经典节点采样方法初始采样的子图中的连通性和高度节点的包含性。由于之前大多数关于网络采样的研究要么假设网络图是静态的并且在任何步骤都完全可访问，要么考虑到流演化并没有解决从原始图中采样代表性子图的问题，因此引入了FLAS算法作为基于固定结构学习自动机的流采样算法，目的是从边流随时间不断演化的活动网络中进行采样 （即网络是高度动态的并且包含大量边缘）。
In this chapter, we focus on the goal of sampling a representative subgraph as scale-down sampling to addressing the problem of sampling subgraphs from social networks and reviewing recent social network sampling methods in the literature. Then, we introduce four sampling algorithms including DLAS, EDLAS, ICLA-NS and FLAS which utilize learning automata for producing representative subgraphs from online social networks. The DLAS and EDLAS use distributed learning automata and extended distributed learning automata, respectively for both deterministic and stochastic networks. The algorithm ICLA-NS is an extended sampling algorithm with post-processing phase, since it utilizes an irregular cellular learning automaton (ICLA) to guarantee the connectivity and the inclusion of the high degree nodes in subgraphs initially sampled by classic node sampling method. Since most previous studies on sampling from networks either has assumed the network graph is static and fully accessible at any step, or despite considering the stream evolution has not addressed the problem of sampling a representative subgraph from the original graph, the algorithm FLAS as a streaming sampling algorithm based on fixed structure learning automata is introduced with the aim of sampling from activity networks in which the stream of edges continuously evolves over time (i.e. networks are highly dynamic and include a massive volume of edges).