大数据管理与应用系列丛书《复杂网络》（吕欣等著）读书笔记-网络抽样

在线开源学习地址https://github.com/XL-lab-bigdata/ComplexNetworks04网络抽样从原始网络中抽取一定数量的节点和边以利用这些样本的拓扑结构和属性信息来估计整个网络的总体特适用于数据量庞大或者无法获取全量数据的情况下能够有效节省存储空间、降低计算复杂度并且在隐藏群体特征挖掘等场景中具有广泛应用4.1统计抽样理论基础4.1.1 基本概念总体参数总体参数是指描述整个调查对象群体特征的数值常见的总体参数包括均值μ\muμ、方差σ2\sigma^2σ2等统计量通过对样本数据进行计算得出的量通常用来估计总体参数例如样本均值xˉ\bar{x}xˉ是用来估计总体均值μ\muμ的统计量样本方差s2s^2s2是用来估计总体方差σ2\sigma^2σ2的统计量估计值根据样本计算的具体数值用于估计总体参数例如总体均值μ\muμμ1N∑i1NXi \mu \frac{1}{N} \sum_{i1}^{N} X_iμN1​i1∑N​Xi​样本均值xˉ\bar{x}xˉxˉ1n∑i1nxi \bar{x} \frac{1}{n} \sum_{i1}^{n} x_ixˉn1​i1∑n​xi​4.1.2 概率抽样方法指在抽样过程中每个个体被选中的概率是已知的且通常是相同的。这种方法确保了样本具有代表性从而可以较为准确地推断总体特征。其关键特征是每个样本单位的选取是随机的避免了主观偏差因此其结果在统计学上较为可信简单随机抽样Simple Random Sampling基本的抽样方法从总体中随机抽取样本每个个体被选中的概率是相同的假设一个学校有500名学生想从中抽取10个学生进行问卷调查。通过简单随机抽样方法可以通过抽签的方式从这500名学生中选取10名学生每个学生的被选中概率是相等的即每个学生有( \frac{1}{500} )的机会被选中分层随机抽样Stratified Random Sampling当总体由几个明显不同的子群层组成时分层随机抽样通过先将总体划分为几个互不重叠的子群层然后在每个子群内进行简单随机抽样来确保每个子群都被适当代表假设在一个学校进行调查学校有500名学生其中200名是男生300名是女生。为了确保调查结果能充分代表男生和女生的比例可以进行分层抽样分别从男生和女生两层中抽取样本并且比例为2:3整群抽样Cluster Sampling将总体分成若干群体群后随机抽取若干个群体并对其中的所有个体进行调查假设要对一个大的城市中的居民进行调查这个城市有多个社区,不可能去调查所有社区的每个居民于是可以随机选择一些社区群体然后对选中的社区的所有居民进行调查系统抽样Systematic Sampling总体首先被按照某种顺序排列然后从第一个单位开始按照固定的间隔选择样本单位假设要从一个有1000名员工的公司中抽取100名进行调查首先可以将所有员工按顺序排列然后选择第1名、11名、21名……直到1000名员工中的第100名多阶段抽样Multistage Sampling将总体分阶段进行抽样,在每个阶段抽样单位从上一阶段选出的单位中选取多阶段抽样通常涉及多次抽样例如:第一阶段从总体中抽取若干子总体;第二阶段从每个子总体中抽取样本;第三阶段对每个子总体继续抽样假设我们要对一个国家进行人口调查。首先从全国各省中随机抽取几个省第一阶段。然后在每个选中的省中随机抽取几个城市第二阶段。最后在这些城市中抽取若干个村庄第三阶段最终从每个村庄选取若干人作为样本4.1.3 非概率抽样方法指在抽样过程中并没有严格控制每个个体被选中的概率也就是说不同个体的被选中机会可能是不相同的其常常依赖于研究者的主观判断或便利性适用于一些在时间、资源上受限的研究便利抽样Convenience Sampling选择容易接触到的个体来构成样本假设我们在商场做顾客满意度调查。我们站在商场的入口处随机选择经过的顾客进行采访这样的样本容易偏向于某一类特定顾客例如常常在该商场购物的人判断抽样Purposive Sampling判断抽样是一种“有目的”的抽样方法研究者基于他们的知识和经验选择那些符合研究目的的个体或单位进行调查假设我们正在研究特定疾病的患者群体。我们选择只采访那些已经确诊并正在治疗的人群而不是随机选择所有病人配额抽样Quota Sampling将总体按某些特定的标准如性别、年龄、收入等进行分层然后根据比例在每个层内选择样本。不同于分层随机抽样配额抽样是非随机的研究者自行决定每一层抽取多少个样本假设我们想对某城市的居民进行消费行为调查考虑到年龄段对消费习惯的影响我们决定将总体按照年龄分为三个层次18-30岁、31-50岁、50岁以上并在每个层次中选择一定比例的样本进行调查这个选择过程是由我们自己决定的链式抽样Chain-referral Sampling又称为滚雪球抽样是一种通过已选择的样本再去选择其他样本的抽样方法。它通常用于调查隐藏群体如特定职业群体、少数族群等因为这些群体的成员不易接触到假设我们正在调查吸毒人群的特征且无法通过常规的渠道获得这些人的信息于是我们选择一个已知的吸毒者作为“种子”样本然后请他介绍其他吸毒者参与调查依此类推4.2网络抽样方法指按特定规则从待研究的网络总体中抽取一定数量节点和边并利用抽取的样本信息估计原网络总体信息如结构特征、节点属性等的过程是一种链式抽样方法当网络总体信息已知时可通过抽取一定数量节点和边达到保留原网络特征、简化运算等目的当网络中部分节点或连边未知时可以采取不依靠全网络信息的遍历式网络抽样方法实现对网络数据的抽取和估计随机节点抽样Random Node SamplingRNS从网络中随机选取一定数量的节点并记录这些节点的相关属性信息如节点的度、标签等,组成入样节点集合V节点均在集合V中的连边组成入样边集合E假设我们在社交网络中选择10个用户进行调查。如果我们随机选择10个节点收集这些用户的属性例如年龄、职业那么我们可以估计整个社交网络中不同年龄或职业群体的分布随机边抽样Random Edge SamplingRES随机边抽样是从网络中随机抽取一定数量的边进而收集边的两端节点的属性信息。通过这种方式我们可以估计网络中连边属性的分布假设我们要研究一个社交网络中的朋友关系抽样100条好友关系并收集每对好友的年龄和兴趣爱好,够帮助我们估计在社交网络中好友之间的共同兴趣的分布情况广度优先抽样Breadth First Search SamplingBFS从一个初始节点出发依次访问其邻居节点并将这些邻居节点加入样本集合中。然后继续从已访问节点中选择新的节点进行扩展直到满足样本量要求假设我们研究一个公司内部的社交网络目标是了解某个项目团队的成员分布情况。我们从一个已知的团队成员开始逐步通过他们的同事扩展直到我们找到足够的团队成员并进行调查,通过层层探索能够捕捉团队的人员构成深度优先抽样Depth First Search SamplingDFS深度优先抽样与广度优先抽样类似但其选取节点的顺序不同。从初始节点开始DFS会选择最后被访问的邻居节点作为新的访问节点并继续深入探索直到达到样本量要求假设我们要研究一个新闻网站中用户之间的互动结构。我们可以选择从一个活跃用户开始深入探索其互动的朋友和评论者直到我们覆盖了足够多的用户。由于DFS探索路径较长它能够捕捉到更深层次的社交关系森林着火抽样Forest Fire SamplingFFS从网络中的一个随机节点开始按照概率 “点燃”该节点的所有边进而“传播火焰”不断选择这些点燃节点的邻居进行扩展直到达到设定的样本量滚雪球抽样Snowball SamplingSNS滚雪球抽样是一种链式抽样方法我们从一个初始样本开始以一定规则选取其邻居节点作为新的样本并不断扩展样本直到满足样本量要求值得我们主要的是当入样节点选取所有邻居节点此时 SNS 等同于 BFS入样节点选取邻居节点数量与其度值正比入样节点选取邻居节点数量为固定值此时 SNS 等同于同伴驱动抽样。特别地当入样节点选择 1 个邻居节点时SNS 等同于随机游走抽样假设我们要研究某个特定兴趣群体比如健身爱好者的行为。我们可以从一个已知的健身爱好者开始让他推荐其他健身爱好者逐步扩大样本这样可以有效获取该群体的特征随机游走抽样Random Walk SamplingRWS从一个随机节点开始然后按照一定的概率规则随机选择下一个邻居节点依此类推。每个节点在每一步的选择都基于上一节点的随机性直到达到所需的样本数量选择一个网络中的节点作为随机游走的起始节点。这可以是任意节点通常我们从网络中一个随机节点开始从当前节点出发随机选择一个相邻节点邻居节点作为下一个节点。每个邻居节点的被选择概率通常是相等的在新节点上重复步骤2从当前节点继续随机选择其邻居作为下一个节点直到达到设定的停止条件。这些节点组成了随机游走的路径同伴驱动抽样Respondent-Driven SamplingRDS是一种改进的滚雪球抽样方法通常用于研究难以接触的群体如隐性群体、少数群体。与传统滚雪球抽样不同RDS通过向每个样本节点提供一定数量的“邀请劵”并要求他们推荐其他人参与调查从而形成一个更为广泛的样本链假设我们想研究某城市中的吸毒人群特征。传统方法无法接触到这一群体但通过同伴驱动抽样我们可以从一个吸毒者开始给他3张“邀请劵”让他邀请其他吸毒者加入调查。这样样本的逐步扩展有助于我们更好地了解该群体的特征4.3无向网络抽样与统计推断V-H 估计量用来估计节点或边属性的无偏估计量尤其是在我们无法获取整个网络数据时其通过对样本数据的推断来估计网络的总体特征其定义为对于有放回不等概率抽样若是y1,y2,...,yn{y_1,y_2,...,y_n}y1​,y2​,...,yn​按入样概率z1,z2,...,zn{z_1,z_2,...,z_n}z1​,z2​,...,zn​得到的样本特征则对于总体 的 Hansen-Hurwitz估计量表示为y~HH1n∑i1nyizi\tilde{y}_{HH} \frac{1}{n} \sum_{i1}^{n} \frac{y_i}{z_i}y~​HH​n1​i1∑n​zi​yi​​也就是说用样本的特征除以其入样概率再取平均得到对总体特征的估计当 RDS 等同于 RWS 抽样即入样概率与度成正比时以及 Hansen-Hurwitz 估计量任意总体特征y的估计值 可以表示为y^∑i∈Syi⋅1ki∑j∈S1kj\hat{y} \frac{\sum_{i \in S} y_i \cdot \frac{1}{k_i}}{\sum_{j \in S} \frac{1}{k_j}}y^​∑j∈S​kj​1​∑i∈S​yi​⋅ki​1​​这里将上面的概率用节点的度来表示因此我们可以用这一思想来估计网络的特征网络平均度估计当估计网络平均度时yiy_iyi​表示节点viv_ivi​的度kik_iki​上式可化简为:⟨k^⟩∑i∈Ski⋅1ki∑j∈Skjn∑j∈Skj−1\left\langle \hat{k} \right\rangle \frac{\sum_{i \in S} k_i \cdot \frac{1}{k_i}}{\sum_{j \in S} k_j} \frac{n}{\sum_{j \in S} k_j^{-1}}⟨k^⟩∑j∈S​kj​∑i∈S​ki​⋅ki​1​​∑j∈S​kj−1​n​网络节点比例估计假设网络中包含 A、B 两类节点θi\theta_iθi​表示节点是否属于 A 类节点的布尔值,为1表示节点属于 A 类否则为0则 A 类节点占比的样本均值和 V-H 估计量可分别表示为P^AnAN\hat{P}_A \frac{n_A}{N}P^A​NnA​​P^VHA∑i∈SAki−1∑j∈Skj−1\hat{P}_{VH_A} \frac{\sum_{i \in S_A} k_i^{-1}}{\sum_{j \in S} k_j^{-1}}P^VHA​​∑j∈S​kj−1​∑i∈SA​​ki−1​​