后使用我的收藏没有帐号？
所属分类： &
查看: 81|回复: 1
倚天屠龙记手游组队挂机好友度怎么算
倚天记手游组队挂机好友度怎么算
点这里&&&&
分享预约信息赢周边福利！qq空间里的亲密度怎么来的?_百度知道如何设计数据结构和算法，计算并存储六度好友关系？
假设用户总数是一千万，平均有好友 25 个。如何能够计算任意两个用户是否为六度之内的好友，度数是多少？此外，以下要求哪些容易实现，哪些无法实现：1. 能否快速获取任意两个用户的好友关系度数（最大为六）1a. 是否能够将度数最大为六的限制任意提高？如计算得到某两个用户的关系度数是 100，两个完全不连通的用户关系度数可定义为正无穷。2. 能否存储或快速获取任意两个用户之间的最短路径？2a. 能否同时存储多条最短路径？（最短距离为 2 时，即为快速获取全部共同好友；最短距离为 3 时，路径数量的上升应该会非常快）3. 当用户好友关系发生变化时，是否能增量更新之前的计算结果？抑或全局重新计算的效率比增量更新的效率更高？4. 「进阶」对于单向好友关系（如关注），六度理论的表述应该是什么？4a. 如果对于两个关注方向，分别计算关系度数，算法应该如何设计？我在其他网站见过，但是没有令人满意的回答，希望可以和大家在这里讨论一下。上面第 4 点中的单向关系可能需要对模型做较大修改，如果需要的话，可以分离出来单独提问。
不请自来，趁毕业论文间歇答一下这个问题。先说一下几个高票答主算法存在的问题。私以为目前最高票答主的回答并没有实质的解决问题，只是在阐述这个问题基于矩阵的运算模型，诸位若是想要深入了解这个算法不妨看看《算法导论》第25章“所有顶点最短路径问题（APSP）”第一节的内容，即计算 “两点之间有多少距离不超过m的路径” 这样问题的原理，不再赘述。矩阵计算模型的时间复杂度无疑是，空间复杂度也达到了，在此基础上做优化很难达到理想的效果。顺便说一句，这个矩阵乘法做路径统计还是很有趣的，还可以利用矩阵乘的结合律加速矩阵的幂运算。另一个高票回答里，缓存三度好友列表存在一个潜在的问题：三度好友的数量真的只有个吗？注意这个值只是节点的平均度数，而非最高度数。事实上，社交网络中用户的好友数量基本上是符合zipf定律，用户的好友数量和用户在社交网络中的排名（好友数量的排名）成反比。注意到这个问题之后，就会明白这个列表的长度并不会如答主之愿，只有不到个；相反，这个数字可能会到几万甚至几十万。再者，计算三度好友列表并存储，如果遇到修改操作很难做出实时的反馈，因为修改一条边，会影响到几万人的三度好友列表。=====================================================================其实这个问题并不复杂，三度好友列表不需要存储，因为重新计算和修改都会很麻烦。请不要用邻接矩阵，使用邻接表吧。搜索可以使用双向迭代加深搜索，算法如下：询问起点和终点之间距离：
1. 初始总搜索深度限制C = 0，起点搜索深度限制A = 0，终点搜索深度限制B = 0，
初始化一个当前时间戳标记。
2. 从终点开始深度优先搜索，搜索深度 & B则跳出，在所有遍历过的节点打时间戳标记。
3. 从起点开始深度优先搜索，搜索深度 & A则跳出，如果遍历到时间戳为当前时间戳的节点，跳6。
4. C = C + 1；若C & 6，跳6。
5. 从起点出发遍历过的节点数量 & 从终点出发遍历数量，则B = B + 1，否则A = A + 1。
6. 返回距离C。
几个工程上可行的优化：1. 把每个用户的好友列表按照他们各自的好友数量排序。2. 缓存2-限制搜索树 以及 3-限制搜索树。（3-限制搜索树的子树显然是2-限制搜索树）3. 缓存两棵搜索树之间是否存在交。4. 深度优先搜索时不必判断该点是否已经访问过，这一条可以保证2中以任意点为根的k-限制搜索树完全同构，又不影响算法正确性。当然，只是一些小trick，具体还要看实现。==============================================================说完算法，就可以正面回答题主的问题了：1. 能否快速获取任意两个用户的好友关系度数（最大为六）1a. 是否能够将度数最大为六的限制任意提高？如计算得到某两个用户的关系度数是 100，两个完全不连通的用户关系度数可定义为正无穷。度数超过6基本也就没有意义了。上述算法获取任意两个用户的好友关系度数，运算次数的阶应当不超过任一用户三度好友的数量。2. 能否存储或快速获取任意两个用户之间的最短路径？2a. 能否同时存储多条最短路径？（最短距离为 2 时，即为快速获取全部共同好友；最短距离为 3 时，路径数量的上升应该会非常快）需要注意到，深度优先搜索所遍历的是一棵搜索树，我们可以在遍历搜索树的过程中为每个节点记下它的父亲节点。当以起点、终点为根的两棵搜索树的叶子节点x重合，那么我们可以找到一条起点到终点的最短路径，起点~叶子x~终点。若想获取所有的最短路径，上述算法在第3步不直接跳出即可，时间复杂度不变。3. 当用户好友关系发生变化时，是否能增量更新之前的计算结果？抑或全局重新计算的效率比增量更新的效率更高？上述算法不需要重新计算。4. 「进阶」对于单向好友关系（如关注），六度理论的表述应该是什么？4a. 如果对于两个关注方向，分别计算关系度数，算法应该如何设计？单向好友关系相当于有向图，依然是从终点逆向搜索，从起点正向搜索。
路径长度限制的比较短时还是比较可做的1：对于长度不超过六的情况，求出每个点三步可达的点集作成有序表，每个点度期望为25的话，表的大小只有25^3，比较两个有序表是否有共同元素可以在线性时间内完成。（如果关系是有向边，除了该点三步可达的点集，还要将边反向求一个三步可达该点的点集）2：存储应该是不可行的，即时计算可能用A*比较合适，具体可以先用问题1存储的点集尝试建立一个非最优的初始解，迭代一下最短路径长度的上限大概会好些。3：与变化的关系两端的点不存在三步可达关系的点集不需要更新。4：六度理论的表述不清楚，不过这种情况下期望的步数似乎比十二少吧？------------------------------------------------------------------------------------------似乎可以查阅一下复杂网络的相关资料
我来抛砖引玉。以下讨论同时适用于无向关系和有向关系。一般社交产品中，主动的关注关系比被动的关注关系对用户更重要，因此以下只考虑主动关注。如果用特征矩阵存储用户的关注关系（好友关系表示相互关注，矩阵为对称矩阵）则使用逻辑运算求得的矩阵自乘结果就是用户间二度关系的特征矩阵矩阵元素间的乘法为逻辑与运算，元素间的加法为逻辑或运算令 D(i,j) 表示用户 i,j 之间关系的度数（距离），再定义
如下则有例子如下：设 N = 6，用户间有双向关注关系 (1,4) (2,4) (2,5) (3,6) (5,6) 表示成特征矩阵即为（用户默认关注自己）则有所有二度关系有 (1,2) (2,6) (3,5) (4,5)三度关系有 (1,5) (2,3) (4,6)继续计算得到
所有人都在四度关系内相连通对于单向关系，计算是类似的，而且不用考虑矩阵的左乘右乘问题，因为二度好友的一度好友和一度好友的二度好友都是你的三度好友，左乘与右乘是完全等价的。对于一千万用户平均关注 25 人的实际问题，只需要一种数据结构，实现稀疏逻辑矩阵的高效存储和矩阵逻辑加法、逻辑乘法、代数减法的高效计算，即可较高效的计算用户间的关系度数。在常用的稀疏矩阵模型(CSR/CSC)基础之上，由于只需要做逻辑运算，数据结构显然有巨大的优化空间。而且用户并非随机关注，一个圈子内的用户会互相关注，也许可以找到合适的矩阵分区方法，简化计算。基于以上说明，比起重新设计数据结构，挑选一个稀疏矩阵模型做优化更可取。这一点在
之前的回答里也提到了。若最多计算到 k=6 则令
即表示用户 i,j 之间的距离C 仍然是一个稀疏矩阵（但不再是逻辑矩阵）存储 C 之后即可实现用户关系度数的快速查询如果让 k 进一步提高，C 会越来越稠密，主要的瓶颈应该是存储，计算的代价也会增加。希望能有高手给出详细的分析。然后是 2，计算用户间的关系路径如果存储，当用户间的距离较大时，空间代价极高，不可取。即使只对距离为 2 的用户预计算并存储共同好友，代价目测也比较高，不易实现。我特地看了一下 LinkedIn，访问了一些明显和我没有交集，关系度数不会太低的用户，但在首次访问对方页面时 LinkedIn 就显示出了我们的关系路径，页面加载只要几百 ms，也没有 Ajax。如下图我想了一下，要实现这个效果，还是有可能的。如前面叙述，现在我们已经有了快速获取任意两个用户间距离的方法（除非用户之间的距离太大），所以在我的好友中找到所有到目标用户的距离是我到目标用户距离减一的人，即可显示出上图中的结果。如果只需要找一条最短路径，每次从好友中取出到目标用户距离比我少一的人，几步之内就可以得出结果。这个计算应该无法在线实时进行，但是耗时应该不会太长。前提还是大部分用户之间的距离已经事先经过计算和存储。所以为了实现快速获取最短路径的功能，在第 1 步的稀疏矩阵模型基础上，除了单个元素的高效读取和高效的矩阵运算之外，还需要能够高效地基于行/列进行检索。接下来是 3当新的关注关系建立时，可以增量更新受影响的节点，但是原有关系删除时，则无法高效的增量更新。同时考虑到每个新关系建立时，需要计算和修改的关系量都会很大（），增量更新也许得不偿失。最后是 4前文说明中的所有矩阵运算，对于无向关系和有向关系都是适用的。只要选定一种关系方向作为「关注」，所有的讨论都直接成立。上面的运算中应该没有能用到矩阵对称性的地方，所以计算复杂度也不会增加。而且如果不做增量更新，不需要额外计算反向关系。以上为抛砖，并没有真正解决这个问题的核心，也就是支持逻辑运算的系数矩阵的数据结构设计，也无法确定这是不是正确的方向。希望能引得玉来。
这是一个非常有趣的问题, 现实工程中也被人实现较多, 其实不是那么的难! 最关键的优化点其实是:
1. 双向广搜, 把 六度 直接降为 三度, 计算量一下就减化非常非常的多了, 虽然其实还是指数级的复杂度. 2. 缓存 二度/三度 好友的结果, 用空间换时间1. 能否快速获取任意两个用户的好友关系度数（最大为六）能, 假设最坏的情况, 即 两个用户刚好是 六度, (如果是三度, 四度, 更容易算出来): 一度好友是 25个, 那三度好友最多是:
15625 个好友,
由于现实数据一定有很多的交集, 可能最终是 8000, 甚至不到5000个好友.
两个用户都先算出他的 5000 个三度好友, 然后相交一下, 看有无交集? 如果有交集, 那就是 六度好友(其实也可能是 四度, 甚至 二度好友, 所以要先把这种情况算出来), 如果没有, 那一定不是 六度好友. 如何求 三度好友?
对于 1kw 用户来说, 其实预计算 缓存三度的结果也挺简单的, 数据量没有多大. 5000个用户id, 压缩压缩10K肯定能搞定, 乘以1kw, 也就是 不到100GB的数据. 按用户去做hash存储, 大多数据用不到, 缓存命中率能很高, 真这个数据规模的话, 单机已经基本能够做到了 准实时的查询了(50ms以内返回).
预处理的时候, 确实需要一些时间. 1a. 是否能够将度数最大为六的限制任意提高？如计算得到某两个用户的关系度数是 100，两个完全不连通的用户关系度数可定义为正无穷。这个我的理解是不可能的, 好在这是指数的增长, 所以现实中, 超过 6度, 到 8度, 甚至更高的几乎完全没有意义, 几乎一定互联!
允许一定误差的话, 不计算, 直接告诉互联就OK了! 特殊场景, 或者 刻意构造数据是有可能的, 但是类似 孤岛 数据, 链式数据... 这个可以特殊处理, 一般线上系统就是舍弃这种精度了.
2. 能否存储或快速获取任意两个用户之间的最短路径？能, 类似 1.
的解法, 还是 双向广搜, 记路径, 存储空间会适当增加, 或者得到中间人后, 重新算到每个中间人的最短路径, 得到最终的最短路径.
计算时间和存储空间肯定要增加不少.
但是量级应该不变! 3. 当用户好友关系发生变化时，是否能增量更新之前的计算结果？抑或全局重新计算的效率比增量更新的效率更高？前面的方案是 缓存一度, 二度, 甚至是直接缓存三度的关系, 所以一条关系改变, 修改量会放大几千倍,
对于修改量不是特别夸张的, 也能接受, 否则的话, 不如 定期 重新计算效率高. 工程中更多的折衷后的结果很可能是:
缓存二度 的好友关系, 三度好友实时算. 好友关系变化时, 更新一度好友列表的同时, 也立即更新二度好友.
4. 「进阶」对于单向好友关系（如关注），六度理论的表述应该是什么？这个更多的像是一个 环, 就不能直接用 前面说的 双向广搜的优化了.
因为他依赖于两边关系是一样的. 但是适当变形, 其实也能做, 就是
A 关注的人列表
B的 粉丝列表 去算...
双向遍历好友并缓存，优先遍历好友少的那个人，如果找到共同好友或遍历达到6次，结束。
很多答主将“人际关系距离”这个问题抽象成了无向图上的最短路问题，题主或许也有这样的想法。我分两个角度回答你的问题。首先不考虑你给出的数据规模，仅仅在算法复杂度上的度量。你的1和2问题即是图上的最短路问题，对于单个query，复杂度为的算法可以解决你的问题。同时由于图上存在最小环为6的特性，一个最多迭代6次的广搜算法在这个数据规模上也是可以接受的。而对于给定图的多个query，复杂度为的算法可以一次给出所有pairwise的最短路，之后的查询即是的。你的3问题是fully dynamic ASAP problem, 是众多dynamic graph问题中的一个重要部分: 最粗暴的想法是，如果在insert new edge or vertex后用Floyd暴力更新所有点对的最短路径长，需要的时间复杂度至少是的。这个问题的tight lower bound至今仍是open problem。一个较好的approach中给出了一种动态规划算法，提供了的更新复杂度（以及的query复杂度）: 注意虽然我们有对于单个query 的查询算法，但是对于大量query少量update的情况，一个slitly slower的更新算法是prefer的。当然，上述是在算法层面做的复杂度分析，具体去做最短路，实际开发环境中还或多或少需要常数优化与稀疏矩阵等等的应用，上面的朋友们都提到了具体的步骤，不加赘述。但是回过头来，在千万乃至上亿规模的“大数据”背景下，将这个问题归结到传统算法中的最短路问题，是否合适呢？复杂度分析已经显示，在大数据规模下，传统的确定性算法很难efficient的解决问题。的算法在千万级别下已经会有明显的处理延迟，这样的时间cost是常数优化无法解决的。题主手上的这1000万数据，不可能仅仅只是两两人之间是朋友而已----这样的数据中，往往包括了人的姓名、地址、年龄、喜好，甚至他们在社交网络上的互动，他们的特别关注，他们偷偷摸摸点开的链接，等等等等，非常丰富的信息。显然，两个上过同所学校的人很有可能是相识，两个在同一领域工作的人或许会相互了解。这样的数据，往往将人们“聚集成类”，比如小学同学圈，大学同学圈，职场圈子，等等等等。这时考量一个人的“人际关系距离”，可以考察他到一个“圈子”的距离，再考察跑到这个“圈子”里距离。“人”是千万上亿的，但“人”的聚类----这样“圈子”一般的东西的规模是可接受的。上述的就是数据的聚类(cluster)思想与量化(quantization)方法。草草找到一篇same background的文章，欢饮参考当然，大数据下有很多的工具可以处理你的问题。或许你也发现了，这些方法可以回答你的问题，但是他们似乎没有精确回答你的问题：这样的抽象不是有“误差”嘛？然而这就需要一个思想的转变：在大数据下，确定性的思维或许需要调整。我是学生，如果有说的不对，不严谨的地方，大家帮我指出来。
1 建立无向图，连线表示有关系，点表示每个用户。 出于存储空间节省的考虑，使用连接表。 执行宽度优先搜索即可，或迭代加深搜索。2 估计空间撑不住，如果提前存了各个用户之间的关系，1kw * 1kw太大了3 可以，参考spfa算法吧，这个具体怎么做还是要设计。4 用有向图应该可以了吧？
".......只有大部分圈子成员对某一个圈子成员都使用严格相同的备注名，这个备注名才会被聚合出来。而且这个备注名也仅仅只展现给这个圈子中的核心成员……"1，既然是通过少部分核心节点链接的，那就用链表好了吧。2，为了限制搜索量，将用户预先按照来源（像人人那样的学校？地区？单位？）排序好。
传赢分析得很全面了，在纯算法上这个问题没有难度了八（因为可以有很多近似方法，不需要实时计算，圈子结构微观上几乎是稳定的，否则就是姜粉哈哈）。挑战在于工程上，微博提供类似功能的API每秒的调用次数可能是5000W/s，都要保证50ms的SLA，所以用redis实现了多级cache，再者 地理/ISP上也是分布的，为了保证健壮性还有更多更多考虑。。我臆测下可能有70%的代码是这方面的。。应该让daoru和企盼说说这部分
已有帐号？
无法登录？
社交帐号登录