算法系列讲解之:社交网络之共同好友模型讲解

简介: 算法系列讲解之:社交网络之共同好友模型讲解

我们知道社交网络经常会看到共同好友,共同好友目前资料也非常的多,也有代码实现,可以依然很多老铁不知道它是怎么实现的,或则说比较模糊。这里给大家介绍下找共同好友的算法。


社交共同好友图



为什么感觉难度大:我们看下图:


1be3d426c943f442965dc88e2ce7e213.jpg

上面图示展示了好友之间的关系,那么我们的共同好友,该如何找到。面对如此复杂的图谱,我们只要认真分析,其实可以捋顺其中关系。


逻辑推理、解析


既然是共同好友,那么肯定是两个人,才算共同好友。也就是说我们面对如此复杂的图谱,我们只要以两个人为研究对象,然后找到两个人的共同好友,其它依次类推,找到更多的两个人的共同好友。


那么这个共同好友,我们该如何实现。


将业务需求转换为程序



两个人的共同好友,我们需要转换为我们的程序,这也是我们程序员的价值,也是我们跟非编程人员的价值区别。那么两个人我们可以转换为两个用户,这两个用户,我们可以通过用户id来表示。相信这个大家都能理解。


两个人我们使用两个用户id,那么这两个用户其实是有非常多好友的。既然有非常多的好友,那么这些好友其实也是用户,所以好友也可以使用用户id来表示。

那么我们可以这样表示了


逻辑图:



下面我们看到两个用户,互为好友,他们分别都有自己的好友。对于下面逻辑图,我们自己就可以找到好友。但是如果想通过程序该如何实现。


6f2bcd1da2c6802b8161571360d0017a.png程序图


这里我们把他转换为实现图,或则程序图

2b466ac1120528ad76754f17b722d398.png


我们将上面的逻辑关系,转换为底层的关系。


程序图转换为程序


上面图已经有了,可是我们该如何转换为程序结构,所以这里我们需要进一步转换为程序。该如何通过程序找到他们的共同好友。


我们人工可以找到他们的共同好友,那么程序该如何找到这些数据的共同好友。


数据在程序中,是需要装起来的。那么该如何装下这些数据,这时候我们就需要想到数据结构了。这时候就涉及到了我们的专业知识,都有哪些数据结构。比如有数组,list,map,树等,其实我们就用比较简单的数据结构即可。我们使用map。这时候就有key和value。


key其实就是我们的用户UserID1,那么他的朋友即为value list,也就是后面一系列的:UserID2,UserID3,UserID。。,UserIDN

用户UserID2,同样也是UserID1,UserID3,UserID。。,UserIDN等


这样我们剩下的该如何做了那?操作两个map,假设UserID1对应的为map1,UserID2对应map2找到他们的共同好友。该如何找到共同好友?

遍历两个map呀.我们通过两个for循环


这里写代码,只表示思路:

for (Integer key : map1.keySet()) {
      for (Integer key : map2.keySet()) {
        if(map1.get(value)==map2.get(value))
         print("共同好友"+value)
   }


代码优化


上面只是实现了,对于两个集合,如果有的长,有的短,我们将小集合放到外层循环,这样可以效率更高。

如果map2是小集合我们可以采用下面方式

for (Integer key : map2keySet()) {
for (Integer key : map1.keySet()) {
if(map1.get(value)==map2.get(value))
print("共同好友"+value)
}


大数据实现


上面我们其实讲的是该如何实现,以及传统该如何实现,那么我们使用MapReduce或则spark该如何实现?

这个其实在《数据算法  Hadoop Spark大数据处理技巧》中是有的,这里给大家贴出来,然后对这里面比较难以理解的做个说明。

9efd24a41514517f71ed70b779f6cf19.jpg

对于map函数,其实是在分割的数据中,通过map找到用户的朋友列表,这里它把用户视为key,用户朋友视为value,但是这个value是为list的。


而且这里面比较难以理解的,其实也是重点,那就是在找到用户id视为key,用户列表视为value后,在输出到reduce时候,将key和value重新组合为key,然后将value视为value。本质其实如下

key value重新定义key2,value重新定义value2,也就是上面的(key2,value2)。那么reduce这时候接受到的数据格式为:

(key value,value)


那么为何这样做,我这里做一个简单的说明,而且下面遇到的时候,在给大家讲解。

3d047d8b661835ca7f1952453fcbfd74.png


我们看到下面每一个map重新定义后的(key value,value)输出内容,我们或许可能恍然大悟,key定义为两个userid其实是为了方便找到共同好友。也就是key包含了userid和它的value,也就是包含了自己和他的其中一个朋友,是为了方便找到他们的共同好友。但是我们看到其实map的作用只是组合了本人和它的好友。何谈共同好友?这是我们在reduce里面会更加明显的让我们看到共同好友。


如果说map只是简单的组合了自己的好友。我们继续往下看reduce。

3b75e85c9847d576e7493fd2b442ae9f.jpg

33f7b09efecbe35c5fa2c1c9a349f3df.jpg

我们看下面reduce讲userid为100和200之间找到共同好友。对于任何一个map来讲,它的作用其实就是找到自己的一个朋友,和他的朋友列表。对于另外一个朋友,其实也是一样,找到他的朋友和他的朋友列表。

这样比较绕口,这里我们看下面具体例子。比如还是100和200为例子。

原始数据是这样的

100和他的朋友,200和他的朋友。

进入map后,处理为:

100和200,然后100的朋友列表

另外被分割的数据,被map同样也处理格式为

100和200,然后200的朋友列表


这样在reduce的时候,就可以通过我们传统的思路比较,找到100和200的共同好友。

22421a528d288b6312092a5bb7906e25.jpg

28eeb11d327cafd7ad83b86e28bbceb0.jpg

7cbb40df2b42d919b9390844f56d731f.png我们明白了map的作用其实就是先配对,reduce其实就是找到配对朋友的共同好友。


上面其实我们明白了MapReduce,spark其实在这个思路下,其实就是API的应用。这里只是简单贴下思路。

5e500ed0c8e269eb3ec47f85bfa04369.jpg


当然如果明白了思路,其实我们也可以通过Flink来实现。

目录
相关文章
|
22天前
|
机器学习/深度学习 算法 调度
14种智能算法优化BP神经网络(14种方法)实现数据预测分类研究(Matlab代码实现)
14种智能算法优化BP神经网络(14种方法)实现数据预测分类研究(Matlab代码实现)
141 0
|
1月前
|
机器学习/深度学习 并行计算 算法
粒子群算法优化RBF神经网络的MATLAB实现
粒子群算法优化RBF神经网络的MATLAB实现
263 123
|
14天前
|
存储 算法 安全
即时通讯安全篇(三):一文读懂常用加解密算法与网络通讯安全
作为开发者,也会经常遇到用户对数据安全的需求,当我们碰到了这些需求后如何解决,如何何种方式保证数据安全,哪种方式最有效,这些问题经常困惑着我们。52im社区本次着重整理了常见的通讯安全问题和加解密算法知识与即时通讯/IM开发同行们一起分享和学习。
121 9
|
1月前
|
机器学习/深度学习 人工智能 JSON
微软rStar2-Agent:新的GRPO-RoC算法让14B模型在复杂推理时超越了前沿大模型
Microsoft Research最新推出的rStar2-Agent在AIME24数学基准测试中以80.6%的准确率超越超大规模模型DeepSeek-R1,展现“思考更聪明”而非“更长”的AI推理新方向。
112 8
微软rStar2-Agent:新的GRPO-RoC算法让14B模型在复杂推理时超越了前沿大模型
|
22天前
|
机器学习/深度学习 并行计算 算法
【CPOBP-NSWOA】基于豪冠猪优化BP神经网络模型的多目标鲸鱼寻优算法研究(Matlab代码实现)
【CPOBP-NSWOA】基于豪冠猪优化BP神经网络模型的多目标鲸鱼寻优算法研究(Matlab代码实现)
|
19天前
|
算法 数据挖掘 区块链
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
|
22天前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
|
22天前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用
|
22天前
|
机器学习/深度学习 运维 算法
基于粒子群优化算法的配电网光伏储能双层优化配置模型[IEEE33节点](选址定容)(Matlab代码实现)
基于粒子群优化算法的配电网光伏储能双层优化配置模型[IEEE33节点](选址定容)(Matlab代码实现)
|
1月前
|
机器学习/深度学习 传感器 算法
【表面粗糙度】基于粒子群PSO算法优化-BP神经网络的表面粗糙度研究(Matlab代码实现)
【表面粗糙度】基于粒子群PSO算法优化-BP神经网络的表面粗糙度研究(Matlab代码实现)
158 7

热门文章

最新文章