靠谱人生茶话会#1 - 2017-2-24 23:03
君寻 (已淡出bgm38)
最近好友功能很是火热，于是产生了一个脑洞：Bangumi上离你最遥远的那个人是谁？
假定你与你的好友的距离为1
（忽然想到还有广义的情况）
（1）狭义上“离你最远的人”
你的好友集合记为A，你的好友中的某人，他的好友集合记为B，如果一个人属于B，而不属于A，那么他与你的距离为2
同理，B中的某人有好友集合C，对于一个人属于C，且不属于A、B，与你的距离则为3
以此类推，从你的好友集合出发，完成一次遍历所形成的所有人的集合，不妨简称为“你的世界”
那么在你的世界里，一定存在一个离你距离最远的那些人，称之为“Bangumi上离你最遥远的人”（狭义）
（2）广义上“离你最远的人”
考虑进“加你为好友的人”的集合，假定这些人与你的距离也为1，在上述遍历过程中同样考虑“加对方为好友”的人的集合，这样得到的离你距离最远的那些人，称之为“Bangumi上离你最遥远的人”（广义）
一个好友也不加的孤立个体不在“你的世界”中，所以不算在内
由于我是小白一只，对于python完全不懂，如果有感兴趣的菊苣愿意做出这个功能就好了Y(^o^)Y
假定你与你的好友的距离为1
（忽然想到还有广义的情况）
（1）狭义上“离你最远的人”
你的好友集合记为A，你的好友中的某人，他的好友集合记为B，如果一个人属于B，而不属于A，那么他与你的距离为2
同理，B中的某人有好友集合C，对于一个人属于C，且不属于A、B，与你的距离则为3
以此类推，从你的好友集合出发，完成一次遍历所形成的所有人的集合，不妨简称为“你的世界”
那么在你的世界里，一定存在一个离你距离最远的那些人，称之为“Bangumi上离你最遥远的人”（狭义）
（2）广义上“离你最远的人”
考虑进“加你为好友的人”的集合，假定这些人与你的距离也为1，在上述遍历过程中同样考虑“加对方为好友”的人的集合，这样得到的离你距离最远的那些人，称之为“Bangumi上离你最遥远的人”（广义）
一个好友也不加的孤立个体不在“你的世界”中，所以不算在内
由于我是小白一只，对于python完全不懂，如果有感兴趣的菊苣愿意做出这个功能就好了Y(^o^)Y
不太能捋顺这中间的结构呀
另外地址是 http://wattlebird.github.io/2014 ... %E7%9B%B4%E5%BE%84/（BGM 的鏈接判定不行……）
对了，你老婆挺漂亮的
第一步：不告诉任何人
第二步：脑补
第三步：用纸巾收拾一下
第四步：该干嘛干嘛去
这是一个形式理论，我不清楚推导过程，你去看wiki吧
这个好玩，好像维基百科词条的度也为6
好像是friends后面加rev什么的
找到了原来是 /rev_friends
而且你要是光算3700人之间任意两人之间的距离的话Dijkstra算一遍就好了，更大的数据的话也许一些message passing的方法会有用些
ps：message passing在没有loop的情况下是精确的，有loop会导致oscillation，虽然可以简单的增加damping来使算法稳定，不过我现在不太看好这个点子了
要是你想计算自己和用户x的距离，要是x和你不在同一个connected component的话，用BFS不加以限制会跑完整个“我的世界”，这样非常浪费时间
如果每一次新的遍历都要很长时间的话，我觉得这事儿得等这阵加好友风潮过了之后比较好
从数据结构的角度上说，保留一定的缓存进行增量式的更新确实省一定时间，然而这不是最慢的地方，目前的bottleneck在你不得不访问并分析大量页面上
0的好友集A里面有1，而1的好友集B里面必然有0，也就是说相邻的两个用户必然互为好友
问题出在了定义“距离2”上面
x有一个好友y，而假设互粉，y的好友集里面必然有x
x的好友集里面必不包含x
所以x在好友y的好友集，却不在x自己的好友集里
因此按照定义，x对于自己的距离是2
你对 d(x,y) 的定义是
d(x,y) = min { k > 0 | x = x_0, x_1, ..., x_{k-1}, x_k = y, where x_i x_{i+1} \in E, for all i = 0,...k-1 }
么？注意这里因为限制了 k > 0，而且我们考虑的graph里没有self-loop，所以按照这个定义，如果x至少有一个互粉好友y的话，那么d(x,x)=2，如果x没有互粉好友 d(x,x)=+\infty
但是，这个定义并不是一个metric，因为metric第一个条件就是
d(x,y) \ge 0 for all x,y and d(x,y) = 0 iff x = y
我的图论和组合都快忘光了... 你提到了 graph 我才突然想起来。我刚去读了wiki，里面写着 connected undirected graph 的 geodesic distance 就是一个 metric （然而我依然找不到证明）... 根据定义，没有关联的用户不在“你的世界”里，所以 connected，然后假设自动互为好友，所以 undirected，所以是 metric 没错；这样看来，lz所说的那个距离就等价于geodesic distance，所以最远的距离也就是 eccentricity
1, 74, 3114, 9221, 5843, 2204, 698, 168, 43, 6, 3, 1, 2
你可以看出来后面其实是有一个长长的链条，应该是某个和你距离为8的人加了一个独立小团体的人为好友