type
status
date
slug
summary
tags
category
icon
password
实验题目
输入：图的邻接矩阵（考察随机图和社会网络模拟图）
输出：
1）符合友谊悖论的节点占比
相关定义：
友谊悖论：是一种社会现象, 指大多数人认为, 自己的朋友比自己拥有更多的朋友。
实验可以考虑随机生成的图以及能模拟社会网络的图（自行设计算法生成），考察不同图结构下是否符合友谊悖论。
友谊悖论 Friendship Paradox
友谊悖论简介
朋友悖论最早是由社会学家斯科特·L·菲尔德（Scott L. Feld）于1991年首次观察到的一种现象，即平均而言你的朋友比你拥有更多的朋友。
这一现象可以解释为抽样偏差的一种表现形式，即拥有较多朋友的人更有可能同时是自己的朋友中的一位。换句话说，与朋友很少的人成为朋友的可能性较小。而感觉上，大多数人认为自己的朋友要比朋友的朋友要多。
假设社交网络有无向图表示，其中顶点集对应于社交网络中的人，边集对应于人与人之间的朋友关系。把社交网络中一个人的平均朋友数建模为该社交网络的平均度。
也就是说，若顶点有条边和它相连（代表拥有个朋友），则在社交网络中，一个随机选择的人所拥有平均朋友数为 （其中第二个等号来自握手定理）。
如果说一个人满足了"友谊悖论",当且仅当在图中, 他所对应的顶点满足
这里的为指示函数：
证明
下面模拟一个人的朋友的平均朋友数量，可以通过随机的选择一个人（至少有一个朋友），然后计算他的朋友平均有多少个朋友来实现。
这相当于随机地选择图的一条边（代表一对朋友）和该边的一个端点（一个朋友），然后再次计算所选端点的度。
选择某个端点的概率为：。式中分子对应于所选的边包含端点的可能性，当拥有更多朋友时，增加，分母是边数的两倍对应于每条边都有两个端点。因此随机选择的一个朋友的朋友数量的数学期望为。根据方差的定义有,其中是图的度的方差。于是上式中的期望可以写成
由于社交网络是顶点的度不相同的图，严格大于零，这意味着节点的朋友的平均度严格大于该节点的平均度。这便证明了结论。
随机图生成算法
上文的理论证明对所有无向图都符合，下面通过代码实现来随机生成一些无向图，模拟检验在不同网络结构下，符合友谊悖论的节点占比。
基本算法思想
- 生成节点数为n，每个节点度数为r的无向图网络。
- 根据给定的概率p，删除条边，并随机生成新的边来代替。
- 检验新生成得到的网络中，符合友谊悖论的点的数量，看是否超过半数。
- 同一组参数反复生成多次网络，看符合友谊悖论节点超过半数的网络占比多少、符合友谊悖论节点的节点占比多少。
- 更换参数多次实验，观察参数对友谊悖论效果的影响。
设置参数为：r=6, p=0.5, 修改n的值
初始设n=20
网络生成部分实现
一般的初始化方式是直接将节点与前后个点相关联，然后依靠边的删除更新来增加随机性。
随机扰动部分实现
对条边中的条依次删除并随机添加新边。
度数比较部分实现
对所有的节点计算：1）度数向量；2）邻居度数均值向量。
结果分析
将模拟生成num次随机网络并计算网络中符合友谊悖论的概率作为一次实验，重复多次实验，计算每次实验中的平均概率，绘制折线图，可以观察到概率基本稳定在0.55左右
后续还可以通过改变参数发现更多结论~
参考链接
- 作者:Rainnn
- 链接:https://tangly1024.com/article/3b658b0a-9823-436d-86bc-1ba12afca4d8
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。