前言
本篇博文主要讲解Graph中社群的概念,然后介绍了一种简单的社群发现算法Louvain Algorithm,最后提供可重叠的社群发现,提出BigCLAM算法,用来识别节点从属关系。
01 Granovetters theory
马克·格兰诺维特(Mark Granovetter,1943年10月20日-),美国社会学家,斯坦福大学教授。格兰诺维特是论文被引用最多的学者之一,根据 Web of Science 的数据,社会学论文被引数排名第一和第三的文章皆出自格兰诺维特之手。格兰诺维特因为对社会网络和经济社会学的研究而成名。其最著名成就是1974年提出的弱连接理论:与自己频繁接触的亲朋好友之间是一种“强连接”,通过这种连接获取到的往往是同质性的信息;但社会上更为广泛的是一种并不深入的人际关系,这种弱关系能够使个体获得通过强关系无法获取到的信息,从而在工作和事业上、在信息的扩散上起到决定作用。
格兰诺维特的研究认为如果两个人之间有共同的朋友,那他们成为朋友的可能性较大。
格兰诺维特的研究也在真实的数据上得到了验证:
1. Edge Overlap
简单解释下,Edge Overlap表示两个节点的邻居节点的重合程度(本身节点不在计算范围内),下图中右边部分右上图,N(i)=4,N(j)=4,去除本身i, j所以N(i)=4,N(