社交推荐对网络多样性的影响

主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂923社交网络社会推荐对网络多样性的影响Ana-Andreea Stoica美国纽约哥伦比亚大学astoica@cs.columbia.eduChristopher Riederer哥伦比亚大学美国纽约mani@cs.columbia.eduAugustin Chaintreau哥伦比亚大学纽约，美国augustin@cs.columbia.edu摘要随着诸如朋友建议和要跟随的人之类的社交推荐变得越来越受欢迎并且对社交媒体的增长具有影响力，我们发现，突出的社交推荐算法可能会加剧处于社交层级顶部的某些人口统计群体为了研究这种在线平等机会的不平衡，我们利用新的英斯特格拉姆数据，并首次提供一项分析，研究社会建议下性别，同质性和增长动态的影响。我们的数学分析表明，存在一种算法玻璃天花板，它展示了隐喻性社会障碍的所有属性，这些障碍阻碍了妇女或有色人种等群体获得平等的代表权。令人担忧的是，我们的证明表明，在固定的少数和同质参数下，算法效应系统地大于社会网络自发增长所产生的玻璃天花板。我们将讨论如何在未来的设计中解决这一问题关键词社会推荐，公平性，随机游走，同质性ACM参考格式：Ana-Andreea Stoica、Christopher Riederer和Augustin Chaintreau。2018.社交网络中的算法玻璃天花板：社交推荐对网络多样性的影响。 在WWW 2018：2018年网络会议，2018年4月23日至27日，法国里昂。ACM，NewYork，NY，USA，10页。https://doi.org/10.1145/3178876.31861401介绍地理距离和社会偏见阻碍公平获取信息和商业交易的历史由来已久一个联系日益紧密的世界的一个希望是，通过消除其中一些障碍，至少向平等机会迈出一步但是，在如今支配着人们所能寻求的知识、工作和交易的社交网络中，如今最重要的是一个人这些连接需要时间来建立和维护。推荐系统在帮助个人指导他们的社会分享方面起着关键作用本材料是基于美国国家科学基金会资助的工作，资助号为1254035和1514437。本文在知识共享署名4.0国际（CC BY 4.0）许可下发布。作者保留在其个人和公司网站上以适当的归属方式传播作品的权利WWW 2018，2018年4月23日©2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.3186140最有价值的资源和合作伙伴。但是，在什么条件下，我们才能确保这些建议不会重现，或者更糟的是，不会强化我们的历史偏见，并伴随着客观性的模糊幻觉？ 人们会先验地期望相似性度量，通常是推荐系统的基础，有助于维持不同群体之间的差异。我们展示了更多：使用Instagram上新收集的数据和数学模型的严格分析的经验证据，我们证明了突出的推荐算法加强了差异增长的速度。虽然引入的问题影响了无数的情况下，建议是算法产生的，我们专注于具体的基本情况：建议建立一个新的优势与另一个参与 者 。 像 “ 你 可 能 认 识 的 人 ” （ Facebook ） 、 “ 关 注 谁 ”（Twitter）、“建议帐户”（In-stagram）这样的功能现在在大多数流行的社交网络服务中普遍存在。它们对连接图演化的影响已经被证明[16]。 引用FATREC研讨会（2017年）主席的开幕词，“如果推荐申请没有改变参与者的行为，这些申请就不会存在”。作为思想实验，可以描绘连接图的有机生长（即， 在没有任何建议的情况下出现的边的添加）作为参考点。相比之下，算法的增长是由暗示产生的确定要建议的新边的算法通常经由其预测能力（即，它是否预期有机增长？），或其命中率（即，其建议是否获得广泛接受？）。 我们问一个不同的问题：是否存在安全（分别不安全）的条件下，一个众所周知的度量不同的影响是不差（分别严格差）算法的增长比有机增长？不幸的是，我们的研究表明，没有安全的条件存在以外的琐碎的情况下，经常使用的算法和三个定义的不同的影响。然而，我们很快注意到，未来的建议算法可以被设计为解释和纠正这种偏见，并提供了一个简短的讨论，在未来的设计中解决这个问题的简单方法。本文的贡献如下为了更好地调查性别在社交网络的有机和人工增长中的作用，我们对Instagram服务及其活跃关系（评论和喜欢）进行了大规模的抓取。图中女性比例适中，但明显占多数。尽管如此，在统计学高度一致的情况下，我们捕获的有机增长显示出所谓的玻璃天花板的痕迹，阻止女性上升到最受评论和喜爱的配置文件。但是，与使用两种众所周知的算法时观察到的算法玻璃天花板相比，这就相形见绌了：只有在这种情况·主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂924我们是否观察到在性别的学位分布中出现了巨大的差距。随之而来的是女性在高层的代表性突然下降（第3节）。我们遵循随机游走对动态图的影响的数学分析，以研究创建算法玻璃天花板的条件。以前的研究强调了在偏好依恋的典型有机增长中，不均衡的人口与同质性的结合是如何为玻璃天花板做准备的。我们的方法允许一个研究最终的扰动效应的推荐算法作为一个新的多项式不动点方程的结果。 这被用来证明两个主要结果：首先，利用随机游走的简单推荐算法不仅受到一些偏见的影响，它还加强了性别差距出现的速度。其次，我们证明了数值，这种效果总是明显的观察参数（第4节）。我们提供了两个重要的理论后续行动。首先，我们解决了经验观察（显示玻璃天花板对女性多数）和数学结果（预测玻璃天花板在牺牲少数）之间的明显矛盾。这两个是调和上述模型的扩展，我们称之为差异同质性，其中两个群体表现出不同的倾向，有利于自己的同龄人。我们证明，这可以翻转玻璃天花板效应来牺牲多数。我们记录到，事实上，与女性账户相比，Instagram上的男性账户在彼此之间表现出更强的同质性。最后，作为概念的证明，我们快速描述了一个简单的“拒绝方法”的改进的随机游走推荐算法。这种方法作出了严格的假设，但其优点是使算法增长比有机增长更公平（第6节）。正如我们在下文中所详述的那样，通过算法对玻璃天花板效应的急剧放大是一个全新的结果，这是我们所知道的没有等价物的结果。 这是一个广泛开放的问题的特殊情况：如何纠正一个看似中立的算法，当它利用的结构是不公平的开始。有些人可能会认为该算法是合法的，因为它利用了合理的度量标准，而不仅仅是对系统中发现的不公平负责然而，对于任何希望人人享有更平等机会的人来说，这仍然是不能令人满意的。 那些遵守严格公平要求的人（例如，定义为统计学上的均等[18]或机会均等），可以建议应用校正步骤。不幸的是，如果没有对偏见的原因和反响的深刻理解，任何事后纠正都可能受到激烈的争论。我们的论文提供了一种替代方法：确定新出现的不公平的一些结构性原因，并要求算法以一种利用结构的方式设计，同时在存在上述条件的2相关工作我们的工作解决了最近提出的关于大数据上运行的算法所告知的决策的公平性问题即使没有明确的歧视意图，也无法获得性别和种族等敏感属性，这些算法也可能会产生不适当的偏见[2]。关于这个问题的大多数相关工作都集中在二进制分类任务，如贷款审批，目标是在平等待遇或机会的各种条件下保持运营效率[4]。同样，研究了单词嵌入[3]和节点排名[17]的公平性。但据我们所知，社交推荐和图算法的效果分析尚未进行。 主要区别在于必须分析网络结构的影响。越 来 越 多 的 证 据 表 明 ， 在 线 服 务 （ 包 括 Twitter[14] ，TaskRabbit [8]和Airbnb [7]）可以重现对历史上代表性不足的群体的众所周知的偏见。提出的问题包括不同的待遇和隐喻的玻璃天花板的证据。 后者是指一个无形的障碍，阻止特定的人口（最常见的是女性）达到较高的认可水平。 这表现在以下情况：（1）该人口群体的成员晋升到更高级别的机会不均衡;（2）与任务相关的特征不能解释这种情况;（3）这种不平等随着级别的提高而加剧。我们观察到这三个条件适用于Instagram数据集，特别是对于喜欢和评论他人帖子的人此外，我们首次收集了在我们的爬行中连接个人的图这让我们观察算法（在这种情况下，配置文件推荐）是否会缓解或加强这种趋势。最近的研究表明，Twitter的增长也受到了建议的影响[16]。将这些先前的结果与我们的结果相结合，人们担心当前社交媒体的工程化增长最终可能会系统地歪曲整个人口群体同质性，个人倾向于与相似的同龄人进行互动与我们最相关的结果是最近的一个证据，即富得更富的动态与同质性相结合，自然会加剧多数群体的优势[1]。 这个模型可以解释为什么像其他服务一样，Instagram上的有机互动会对一些参与者表现出上述偏见。另一方面，我们引入随机游走动态，密切捕捉推荐系统的运作方式。3有机生长与算法生长3.1数据收集Instagram活动图。 我们从Instagram的创始人Kevin Sys- trom开始抓取Instagram的公共资料。通过Instagram API，我们收集了个人资料信息，并递归地跟踪关注者列表。 对于每个个人资料，我们收集了名称，用户名，唯一ID，并为每张照片抓取了元数据，其中包括：唯一照片ID，喜欢的数量，评论的数量，标签，位置，时间戳，标记的用户，以及3-5个喜欢的随机子集和评论。对于每个用户，我们汇总了这些信息，以获得点赞总数，评论，标签，第一张和最后一张照片的时间戳以及使用的主题标签集。在2014年和2015年的几个月里，我们总共从245038个不同的用户那里收集了115796284张虽然这些数据可能不包含Instagram用户的全部多样性，但在大多数情况下，它足以获得统计上显著的结果。··主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂925表1：男性与女性泊松回归的程度，Instagram的活动，没有控制变量。全部底部25%底部25 - 50%顶部50 - 25%顶部25%顶部10%顶部1% 顶部0. 百分之一观察值：553，628 138，407 138，407 138，407 138，407 55，363 5，537 553表2：男性与Adamic-Adar推荐频率的女性Poisson回归，无控制变量。全部底部25%底部25 - 50%顶部50 - 25%顶部25%顶部10%顶部1%顶部0. 百分之一性别推断。我们的性别推断方法改编自[13]表3：初始图表的性别比例利用名字和社会保障数据。Mislove等推断性别平衡使用了1890年至2015年社会保障数据中的姓名数据集。我们只包括1940年至2007年之间的姓名数据，因为报告的人口统计数据预测，在此之前出生的Instagram用户不到4%。我们过滤了报告的男性或女性至少出现50次的姓名，其中至少95%为单一性别。这就产生了32676个独一无二的名字，我们用它们来标记92935个 Instagram用户。这大约占人口的38%其中49，583或53%被标记为女性，43，352或47%被标记为男性。我们测试了一个小样本的分类名称的手，获得97%的准确率。我们称这个图为Instagram标记的核心喜欢和评论的图表Instagram标记为core的用户总共发布了44，725，840张照片，我们从中抽取了100万张照片。对于这组中的每张照片，我们查看了收到的3-5个喜欢和评论，并提取了所有作者，只有当他们的性别可以如上所述标记时才保留这些我们在图片的作者和点赞或评论的作者之间创建了一个边缘。 我们选择关注喜欢和评论作为互动，因为它们是一种比粉丝更复杂的在线连接方式。这创建了一个由553，628个节点和652，931条边组成的图形，其中每个人都有一个标记的性别。在这里，我们得到了54。43%的用户被标记为女性，45。56%的用户被标记为男性，显示性别平衡与上述情况相同这个图表被称为Instagram活动，是我们将在本文其余部分使用的主要图表。请注意，它要大得多，评论的作者可能不在原始抓取中，因此我们没有关于他们的活动和追随者的所有元数据。 构建图意味着用户的度计数有多少不同的（和标记的）用户接收或给出评论或喜欢她的图片之一。DBLP图。 我们根据DBLP合著数据集[10]的选择验证了我们的结果，证实了Avin等人的分析。 [1]这表明男性和女性研究人员在他们拥有的受指导者数量方面存在性别差异。男女男性57%（1. 2x）43%（0. 8 x）女性40%（0. 9x）60%（1. 1x）我们从DBLP数据集的最新版本中抽取前200，000篇文章，从中提取作者并执行性别推断。我们进一步创建了一个图的作者之间的合著者，我们的推理方法发现一个性别。得到的图DBLP图由102，263个节点组成，其中80个节点是由一个节点组成的。7%被标记为男性和19. 3%为女性，199，679条边。由于在该数据集中证明存在对男性研究人员的现有偏见[ 1 ]，我们分析了推荐算法对这种差距的影响。3.2有机增长下的偏差Instagram的“建议帐户”功能是在我们的数据抓取之后引入的。因此，我们收集的数据是有机增长的代表性视图，这是网络如何在没有算法建议的情况下从交互中演变而来。大量文献关注性别在网络世界中获得可见性和影响力的影响[14][15][1]，其中财富的衡量标准被重新定义为用户-用户互动的数量（例如我们上面定义的程度我们进行了多重分析，复制了上述论文中的方法，出于篇幅原因，我们简要总结了这些方法。首先，在Instagram活动图中，我们使用没有控制变量的泊松回归。 该分析显示，在包含最突出账户的最后四分位数中，男性用户的发病率比（IRR）为1.09*（增加9%，其中 * 表示统计置信度p <<0.05）。001）对于评论/喜欢程度。所有其他四分位数均未显示性别效应然而，效果相对较小，并且在顶部0处最突出。1%，包含5000个节点（见表1）。事实上，在前5,000名或前1%的人中，妇女的学历在统计上很重要，高达12%。图1进一步说明了Instagram活动图和DBLP图中的这种效果。对于Instagram数据集（a），我们男性0.011*-3.6e-17* 4.4e-17*-3.6e-17* 0.08-0.05*-0.12* 0.13*男性IRR 1.11* 0.99* 1 *0.99* 1.09*0.94*** 1.14**公0.08*-2e-16*-2e-16 * 0 *0.11*0.14*0.14*0.21*男性IRR 1.08* 0.99 * 0.99* 1 *1.12*1.15*1.15*1.23*观察值：295，919 73，980 73，980 73，98073,97929,5922,959295主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂926||（没有表现出特别性别失衡的子集）和45%Γ（））1个510501005005000一二五十二十50 100 200推荐程度/频率（一）推荐程度/频率（b）第（1）款图1：（a）对于Instagram活动图，分别在原始图（蓝色）和推荐下的图（绿色和红色）中表示推荐度或频率至少为x的节点节点虚线提醒我们数据集中女性的实际百分比;（b）DBLP图同上。观察到，虽然在初始图表中，两性之间的差距不是很大（蓝点和圆圈），但仍然存在。虽然女性占总人口的54%，但在学位>10的人中，她们只占48%（大致相当于10%）。推荐度高的节点。我们自己对最大公共邻居的分析表明，这确实是不切实际的，而且过于简单化，无法获得合理的结果，因为建议是在有限的集合中选择的。我们定义Adamic-Adar指数前1%的最有联系的用户），54%的人拥有度>100两个节点u和v为（u，v）→w∈联合∩v1/log|Γ（w）|，whe re2000级以上总之，我们观察到的有机生长证实了性别的显著影响当控制内容生产率时，我们获得了类似的结果（此处省略）。总体而言，妇女在高层的代表性似乎不足，尽管她们构成了最大的群体，但并没有完全被排除在大的认可水平之外。这促使我们研究当Instagram的有机增长得到推荐的补充时，这些偏见如何改变3.3推荐算法推荐算法通常利用结构来在相似但尚未连接的个体之间找到兼容的匹配。已经提出了许多启发式算法，并且选择其中的代表性子集是具有挑战性的。有两个从先前的全面比较中脱颖而出：亚当-阿达指数 我们首先注意到，如果算法是完全预测的，并且只建议节点在有机增长中会产生的边缘，我们不应该观察到显着的效果。因此，我们包括基于Adamic-Adar指数的社会推荐，因为它在[11]中被示出为在预测中是最准确的，因此从扰动的角度来看是保守的选择。 Adamic-Adar索引采用了一个简单的规则，“选择具有最大公共邻居的节点”来避免总是Γ（u）表示u[11]的所有邻居注意，在该索引中，非常流行的共同邻居将比具有较小度的共同邻居携带较小的权重。 对于每个节点，通过找到具有最大索引的另一个节点v来计算社交推荐，该另一个节点v不是邻居（随机打破联系）。随机漫步另一个有趣的比较点是一种算法，它最好地再现了今天实际给出的建议。 这是一项艰巨的任务，因为目前部署的许多算法都很复杂，并且通常保密以防止竞争者和作弊者。为了最好地满足这一需求，我们选择了一种基于长度为2的随机游走的算法，因为它被认为与我们所知的唯一一篇可以访问此专有数据的文章中的真实建议相似[16]。 该算法与Adamic-Adar指数算法不同，它通过在点X1= u开始随机游走并以概率返回v，为每个节点u返回一个随机推荐P（X3=v|X1=u）。（一）我们注意到，我们得到的结果似乎独立于所选择的算法。这可能是因为这两种算法，实际上是大多数建议，更有可能选择一个节点，该节点具有多个小度的公共邻居，不同之处仅在于它们如何组合这些特征。原图Adamic-Adar随机游动原图Adamic-Adar随机游动至少有x级学历的女性用户百分比0.00.20.40.60.8至少有x级学位的研究人员中女性研究人员的百分比0.000.050.100.150.200.250.30（主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂927CCDF•--–不联系我们125102050100200500建议频率图2：在Adamic/Adar算法下，推荐频率分布为CCDF，分别针对女性（红色）和男性（蓝色）以及Instagram数据集（实线）和DBLP数据集（虚线）绘制。3.4算法增长在推荐下，程度作为识别或财富的衡量标准的自然等价物是被推荐与您联系的用户数量，即，推荐的频率。 对于Instagram活动图和DBLP图中的每个节点，我们计算了单个推荐，并收集了各种节点出现为建议的频率，这与这种动态下的度增长有关。我们首先在表2中给出了允许与有机生长直接我们使用泊松回归，其中因变量作为Adamic-Adar下Instagram活动图的推荐频率（注意，在这种情况下，总人口为295，919，即至少被推荐过一次的人）。 随机游走算法的省略结果是类似的。在这里，人们看到了更明显和一致的玻璃天花板效应。最后四分位数的所有人口都以更高的频率看到男性，并且这种趋势总是随着学位的增加而增长。有助于解释选定组的相对大小与类似的有机增长统计数据（蓝色部分）的对比非常明显。由于即使在推荐用户的集合中女性也是大多数，因此推荐中的性别差异的影响放大，因为简单的同质性将表明女性应该被更多地推荐。这表明，仅凭学位并不足以创造财富，同质性也发挥了作用，甚至可以扭转不平等。表3示出了针对初始图的这种分析，具有作为行的整个节点集合（按男性和女性划分），以及作为列的节点所连接到的用户对于每一行，我们显示了男性和女性的百分比，括号中分别显示了男性和女性实际百分比的比例 我们观察到，标记为男性的用户比标记为女性的用户更同性恋，表现出分化的同性恋的实例。4模型和定义现在，我们介绍一个模型的算法增长下的建议，mendation算法再现了观察到的加强偏见。这有两个目的：首先，它验证了我们的结果不仅限于Instagram上的活动和性别，而且适用范围更广。其次，它提供了一个起点，调查其原因，这可能有助于减轻偏见，在未来的设计。我们建立在偏好连接动力学（或线性复制模型，等价地）的扩展上[1，9]。4.1有机增长我们介绍的第一个模型是从现有模型改编而来的，它再现了网络少数-多数划分：新节点X0进入网络，并以概率r接收标签R，以概率1 r接收标签B（对于0 r 1/2）。随机性：以概率η，新节点X0随机选择现有节点X1（图3（a））。优先连接（富人越富）：以概率1 η，X0随机均匀选择一个节点并复制其一条边。这相当于新节点连接与结束节点的度成比例虽然有机增长为每个性别产生的度分布很难区分，但很明显δt（v）/u。∈Vδt（u），其中reδt（x）表示节点的度Adamic-Adar算法的推荐分布频率在Instagram数据集和所选DBLP数据集上都这证实并扩展了Avin等人[1]获得的结果，其中在DBLP网络中观察到性别偏见这种差距，表现出增长的对数-对数规模，是不同的权力系数的统计机会，达到至少x的建议，这取决于性别的迹象。随着人们逐渐选择只保留最成功的个体，上述效应转化为观察到的女性比例的突然和加速下降女性代表性的下降在图1中以红色表示Adamic-Adar建议，绿色表示随机游走，其中绘制的圆圈的大小x在时间t和Vt是在时间t的图中的节点的集合（图3（b））。同质性：如果新节点的标签与它选择连接的节点不同，则以概率ρ接受该连接，并重复该过程，直到形成边。同质性参数0ρ 1捕捉到一个不太相似的人最终被选择为同类人的可能性较小因此，当网络根据该模型增长时，在每个时间步长处恰好添加一个节点和一个有向边我们称这个过程为网络的“有机生长”，即个体在不受任何外力影响的情况下进入网络并形成新的联系。InstagramDBLP1e-061e-041e-021e+00···主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂928X1X1x0的x0的ηX21 -ηX3X1x0的X2--–--•--→→–.→∞δ（v）v∈Bn）的方式--ρζ1 -ζ(a)(b)（c）图3：有机和推荐模型的增长 在这三种情况下，都会出现一个新节点X0（本例中为红色）。在有机生长模型中，X 0以概率η连接到随机项目X1（a），并且以概率1 η根据优先连接选择X1（b）。在推荐增长模型中，以概率ζ，它遵循有机增长模型，并且以概率1 ζ，创建幻影节点X0，随机选择节点X1，并从该项目（c）通过粗体箭头遵循长度为2的随机游走X1X2X3。最后，X1连接到X3.在每种情况下，如果连接节点具有相同的颜色，则它们连接;如果不是，则它们以概率ρ连接。4.2推荐算法递增函数k（n）（简称k）使得我们通过添加稀疏推荐来扩展有机增长模型利姆托普（B）=∞和limtopk（R）=0，（3）现有节点之间的差异。大多数推荐算法n→∞kn→∞topk（B）[11]依赖于将节点与距离为2的邻居或朋友的朋友（例如， 公共邻居、Adamic-Adar、Jac-卡、随机游走）。 为了这个理论分析的目的，我们专注于长度为2的随机游走（见上面的等式1），因为它包含了这些算法的一般性质，并使理论分析易于处理。 我们假设网络在推荐算法下以如下方式增长：少数-多数划分：新节点X0进入网络，并以概率r接收标签R，以概率1 r接收标签B（对于0 r 1/2）。有机增长：概率为ζ，X0通过有机增长连接。推荐：以概率1ζ，X1被均匀地随机选择，并且遵循长度为2的随机游走：X1X2X3。最后，X1连接到X3（如果颜色相同，则连接;如果颜色不同，则以概率ρ连接）。在这种情况，X0可以被认为是一个虚拟节点，因为它没有接收任何连接而消失（图3（c））。我们分析的效果，推荐渐近，suming网络的大小趋于无穷大。4.3定义定义4.1（权力不平等）。如果图序列G（n）中的红色节点的平均功率低于蓝色（或随机）节点的平均功率，则图序列G（n）中的红色节点具有功率不等式效应。1个其中topk（R）、topk（B）分别表示度至少为kAvin等人[1]证明了有机增长导致两个子种群的度分布遵循两个幂律，具有不同的系数，这反过来证明了根据上述定义的玻璃天花板效应5证明算法的玻璃天花板我们的理论贡献是一个新的分析如何推荐算法可以产生一个甚至更高的偏见比有机增长在我们的分析中，我们注意到，我们分析的算法不会凭空产生偏见，而只是放大了网络中存在的偏见。 基于这个原因，我们将重点放在有偏偏好依恋模型上，并通过随机游走增加了随机性和推荐的影响。我们首先提供了一个新的分析的方式长度为2的随机游走影响网络中的节点的度分布的演变，并表明度分布遵循幂律与不同的系数为红色和蓝色的节点，分别。 我们分析了入度，因为图是有向的，而出度是常数的建设。我们使用Avin等人对玻璃天花板效应的正式定义。 [1]，它依赖于将个人财富定义为节点的度，将集体财富定义为个人财富值的总和。因此，我们用R表示红色节点的集合，用B表示蓝色节点的集合，βi，t是红色节点的数量，ui，t（R）是塞普茨< 1，则limn（R）。v∈Rδ（v）≤（二）t个推荐后所有R个节点的度n1（B）其中n（R）是红色节点的数量，δ（u）是u定义4.2（尾部玻璃天花板效应）。 图序列G（n）对于红色节点表现出尾部玻璃天花板效应，如果存在有机模型（i=1）的行走（对于蓝色节点也是如此以及推荐模型（i=2）。由于在每一步都添加了一条边因此对于有机模型引入 ut（R）=tαt和ut（B）=t（1αt）是有意义的，其中αt等价地定义为红色节点的度之和1 -η··C.主题：Web与社会WWW 2018，2018年4月23日至27日，法国里昂929P|P|P|联系我们P|− P |P|− P|--–P|·P|−·P|+t+1·α·P阿尔法βtβt除以度的总和，或者简单地除以在推荐动态下朝向R个节点创建的边的分数。对于推荐模型，我们类似地定义α2，t。最后，我们引入一些有用的符号：i（A B），其中i=1， 2， 3作为颜色B的节点分别通过随机性、优先附着和推荐连接到颜色A的节点我们观察到P（X3是R）P（X3是B）β2，tρβ2，tP 1（R|R）=β2，t+ρ（1 −β2，t），P 1（R|B）=ρβ2，t+1 −β2，t，α2，tρα2，t图4：推荐模型的演变每个P 2（R|R）= α2，t + ρ（1 − α2，t），P 1（R|B）=ρα2，t +1 − α2，t，3（R R）=P（X3∈R|X1 ∈ R），P（X3 ∈ R|X1 ∈ R）+ ρ·P（X3 ∈ B|X1 ∈ R）3（RB）=ρ·P（X3∈ R|X1∈ B）。P（X3 ∈ B|X1 ∈ B）+ ρ·P（X3 ∈ R|X1 ∈ B）（四）假设长度为2的随机游走的边（右）是通过有机生长产生的：通过随机连接（左上）或优先连接（左下）。结束节点可以是红色或蓝色，并带有不同的概率，随机连接中的（r，1−r），优先连接中的（α，1−α），以及注意i（B R）=1i（R1R）和i（B B）=1i（R B）对于所有i1， 2， 3 .每种情况下的分母表示节点在通过随机游走LemmA5.1. E[αt1|αt]=αt+F（αt）−αt，其中计算这些概率中的每一个的重要步骤是分析红色（分别为蓝色）节点接收连接的概率，这取决于连接的动态性。图4显示了这种分析的一个实例，其中随机游走X1X2X3被分解为边X1X2和X2X3为了计算X1X2形成的概率，我们看到它可能是通过随机连接或通过优先连接创建的，在图4中被包围在圆圈中。由于随机游动可分解为两条独立的边，P（X3∈R|X1∈R）可以写成P（X3 ∈ R|X2 ∈ R，X1 ∈ R）·P（X2 ∈ R|X1 ∈ R）（5）F（αt）= ηr·P1（R|R）+ ζη（1 − r）·P1（R|B）+（1 − η）r·P2（R|R）+ ζ（1 − η）（1 − r）·P2（R|B）。由于空间的限制和方法的相似性，我们省略了这里的证明，为推荐模型的分析保留空间。我们注意到α是函数F的不动点。度分布 我们注意到，两个总体的入度分布遵循具有不同系数的幂律，类似于[1]，稍微增加了随机因子。用mk，t（B）和mk，t（R）表示在时间t时度为k的蓝色和红色节点的数量，并定义+P（X3 ∈ R|X2 ∈ B，X1 ∈ R）·P（X2 ∈ B|X1 ∈ R）。然后，对于任意两种颜色A和B，用~（A B）=η 1（A B）+（1η）2（A B）表示。使用类似的推理，我们得到Mk（x）=limt→∞E（mk，t（x））。（七）不P（X3 ∈ R|X1 ∈ R）= P~（R|R）2 + P~（R|B）·P~（B|R），定理5.2.对于有机增长模型，入度分布红色和蓝色群体的分布也遵循幂律，即，Mk（R）k−β（R）和Mk（B）k−β（B），其中系数β（R）=1+1P~1CR（X3∈B|X1∈R）=P（R|R）·P（B|R）+P（B|B）·P（B|B），P（X3 ∈ R|X1 ∈ B）= P~（R|B）·P~（R|R）+P~（B|B）·P~（R|B），P（X3 ∈ B|X1 ∈ B）= P~（B|B）2 + P~（R|B）·P~（B|R）。（六）且β（B）=1+CB，其中CR=（1 −η）。 r2 （R|R）+1 −r·P2（R|B）对于k> 0，Σ，5.1有机增长模型中的玻璃天花板为了证明有机增长模型具有玻璃天花板效应，我们采用了与[1]类似的技术，并增加了CR = η·。 r·P1（R|R）+1 −r·P1（R|B）Σ，k = 0。随机连接的影响，除了优先连接。然而，随机性不影响度分布系数（除了度为0的节点），而只影响向红色种群的边的增长率。我们首先注意到，向红色布居的边的增长率向常数αr收敛。<为了看到这一点，我们使用以下引理，其中函数F对边缘向R的增长进行建模：对蓝色群体进行了类似的分析5.2玻璃天花板推荐模型中的红色财富汇聚节点。我们首先证明红色节点的度数之和收敛于一个常数小于r，甚至小于有机物的情况：lim α2，t=α2<α

下载后可阅读完整内容，剩余1页未读，立即下载