大型在线社交网络的高效高代表性采样方法研究

发布时间：2024-03-24 11:12

　　在线社交网络(Online Social Network,OSN)已成为有效连接人们和促进信息传播的重要平台,这对我们的社会生活和社会至关重要。但是由于隐私问题和访问限制,研究者很难获得整个社交网络的数据并对其进行分析,因此通过采样得到一个具有代表性的子图至关重要。但是由于同样的原因,我们缺乏原始网络作为参照,这对评估抽样方法的无偏性(尤其是代表性)提出了巨大挑战。因此,用户均匀采样方法(Uniform sampling of user IDs,UNI)[Gjoka et al.2010]被提出以获得原始网络的节点拓扑特性的无偏分布,从而用来评估其他采样方法的无偏性。然而,UNI采样效率低下,并且很少研究由采样节点及其之间的连接所形成的子图的代表性和连通性。故在本文中,本文提出了一种自适应UNI采样(adpUNI)方法,该方法通过将用户ID空间划分为多个均匀间隔并使得各区间采样概率根据其命中率自适应地变化来克服UNI采样效率低下的缺点。基于adpUNI方法,我们进一步将每次采样命中节点的邻居节点也添加到样本集中,这样可以进一步提高采样效率,并获得更具连通性和代表性的子图,我们将该方法称...

【文章页数】：77 页

【学位级别】：硕士

【部分图文】：

图２－１拒绝釆样方法说明??Ｆｉｇ．２－１?Ｔｈｅ?ｉｎｓｔｒｕｃｔｉｏｎ?ｏｆ?ｒｅｊｅｃｔｉｏｎ?ｓａｍｐｌｉｎｇ??

?北京化工大学硕士学位???ＡＣＣＥＰＴＡＴＩＯＮ??’?ｆ?ｍｍ?ｙ??０?［ｘ；ｘ＋ｄｘ］?ｘ??图２－１拒绝釆样方法说明??Ｆｉｇ．２－１?Ｔｈｅ?ｉｎｓｔｒｕｃｔｉｏｎ?ｏｆ?ｒｅｊｅｃｔｉｏｎ?ｓａｍｐｌｉｎｇ??２．３．２?ＵＮＩ采样过程及均匀性证明??ＵＮＩ采样作为....

图３－３新浪微博用户ＩＤ在区间［０，５〇ｘｌ〇８）内的分布情况??Ｆｉｇ．３－３?Ｔｈｅ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｏｆ?ｖａｌｉｄ?ｕｓｅｒ?ＩＤｓ?ｏｆ?Ｓｉｎａ?Ｗｅｉｂｏ?

＜?ｄ＾??１〇３?［：?｜．．．．．．Ｉ?Ｔ７?＊?＾??厂１??１０?ｉ＾ＳｐＦｒ！?：?ｉ?Ｉ?：?？??？?？?？?＜？］？??攀?？?＾?？?？??〇?＾?‘?？?．?？?？?？?－?？?＊??１０?？－?＊?？?＊?？?？?＊??０?２６?５０?７５?１００?１２５?....

图５－１?ＵＮＩ，ＭＨＲＷ和ａｄｐＵＮＵｄｐＵＮＩ＋Ｎ?（在不同的区间划分下）对ＴｗｉｔｔｅｒＵｂ）和新浪微博（ｃ，ｄ）??

?第五章实验及结果分析???度差别不是很大，故不同区间数的划分对ａｄｐＵＮＩ在其上的采样效率的影响的差异不??会太大。从图５－１?（ｂ）和（ｄ）中可以看出ａｄｐＵＮＩ＋Ｎ的采样效率对区间划分数Ｉ有??较好的鲁棒性。??值得注意的是在图５－１和表５－１中／’ｓａｍｐｌｉｎｇ?ｔｉｍ....

图５－４各釆样方法对新浪微博的釆样子网与原网的度分布（ａ）、ｋ－ｃｏｒｅ分布（ｂ）??和聚类系数分布（ｃ）??－－

?第五章实验及结果分析???１〇０１．０－?ｋ?１．０???ｊ??（ａ）?Ｋ?（ｂ，?（ｃ，??Ｉ?〇．〇．?／?—－?ＢＦＳ??１０°?ｌ〇ｉ?ｌ〇２?ｉ〇３?１０４?ｌ〇〇?ｉ〇ｉ?１０２?〇？〇?０?２?０．４?０．６?０．８?１．０??ｄｅｇｒｅｅ?ｋ－ｃｏｒｅ?ｃｃ??....

本文编号：3937359