python 社区划分 - CSDN

　　算法来自论文：Fast unfolding of communities in large networks 是一种快速的非重叠的社团

　　算法 使用说明，直接调用BGLL函数，参数传入Graph类型的变量就可以得到结果，返回值第一个是所返回的

　　2在一些细节上会有所不同，希望广大读者注意。本博客以代码为主，代码中会有详细的注释。相关文章将会发布在我的个人博客专栏《

　　声明代码的运行环境为Python3。Python3与Python2在一些细节上会有所不同希望广大读者注意。本博客以代码为主代码中会有详细的注释。相关文章将会发布在我的个人博客专栏《Python从入门到深度学习》欢迎大家关注。

　　开篇之前先来一段很老套的开场白吧~ 随着经济的日益发展人们可以在社交网站上进行交流在这些交流的背后不仅存在着用户之间的社交关系还存在着用户之间的兴趣关系。为了能够对相关社交网站例如微博上的用户进行聚类可以使用社区划分的算法对用户进行聚类分析本文主要讲述Label Propagation社区划分算法。

　　社区通俗来讲就是网络中节点的集合为什么这么说呢因为社区结构指的是在网络中由一些节点构成特定的分组在同一个分组内的节点通过节点之间的边紧密的连在一起而分组与分组之间则连接比较松散称每一个分组称一个社区。

　　众所周知Fast Unfolding算法是基于模块度的算法不同于Fast Unfolding算法的是Label Propagation算法是基于标签传播的局部社区划分算法。在初始阶段Label Propagation算法给每一个节点设置一个唯一的标签在每一次迭代的过程中每一个节点选择与其相连的节点中所属标签最多的社区标签为自己的社区标签。随着社区标签的不断传播最终紧密连接的节点将有共同的标签。Label Propagation算法的计算过程比较简单Label Propagation算法利用网络的结构指导标签的传播过程在这个过程中无需优化任何函数。随着算法的迭代最终算法将自己决定社区的个数。

　　在标签传播的过程中节点的标签更新可以分为两种情况同步更新和异步更新。同步更新意思是某个节点在迭代第n次的时候会根据其所有邻接节点第n-1次迭代的标签结果进行标签更新。同步更新对于一个二分或者近似二分的网络来说会存在着社区标签震荡的情况。这里我们着重介绍异步更新。一部更新是指某个节点在迭代第n次的时候会根据已经迭代完第n次的标签结果和已经迭代完第n-1次的标签结果进行标签更新。

　　整个实现过程围绕着异步更新来完成以下是异步更新的方法

　　测试需要有测试数据测试数据可以为两列或三列的数据两列的数据均为节点三列的数据最后一列需为权重值。如下所示

　　这里需要一个加载数据的方法此方法在前面的文章中也提过不止一次了可以使用《Python两种方式加载文件内容》不限于这两种加载数据因为此次聚类算法用到节点和边的概念所以加载数据的方式与以往略有不同具体方式如下

　　此处需要有一个方法对测试得到的聚类结果即社区划分结果进行保存方法如下

　　你们在此过程中遇到了什么问题欢迎留言让我看看你们都遇到了哪些问题。

　　1.标签传播算法的具体实现过程由python的一个类库networkx完成。

　　2.建立一个典型的社交网络图Zachary的空手道俱乐部图表

　　在社区发现算法中几乎不可能先确定社区的数目于是必须有一种度量的方法可以在计算的过程中衡量每一个结果是不是相对最佳的结果。

　　模块度Modularity用来衡量一个社区的划分是不是相对比较好的结果。一个相对好的结果在社区内部的节点相似度较高而在社区外部节点的相似度较低。

　　假设cv和cw分别表示点v和点w所在的两个社区社区内部的边数和网络中总边数的比例

　　模块度的大小定义为社区内部的总边数和网络中总边数的比例减去一个期望值该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小于是模块度Q为

　　设eij表示社区i和社区j内部边数目的和与总边数的比例ai表示社区i内部的点所关联的所有的边的数目与总边数的比例。

　　在进行每次划分的时候计算Q值Q取值最大的时候则是此网路较理想的划分。Q值的范围在0-1之间Q值越大说明网络划分的社区结构准确度越高在实际的网络分析中Q值的最高点一般出现在0.3-0.7之间。

　　有时候可能不知道全网络的数据可以用局部社区的局部模块度的方式来检查社区的合理性。假设有一个已经检测出来的社区社区的节点的集合为V这些节点所有的邻接节点而加入到集合当中来形成新的集合V*。定义V的邻接矩阵为

　　于是和全局模块度相似的是可以用节点集V全部属于节点集V中的元素所占的比例的大小来衡量一个社区的好坏

　　局部模块度比全局模块度要快的多因为局部模块度的计算只需要用到局部的网络信息只需要在刚刚开始的时候扫描一下整个网络。对于中小规模的网络可能局部模块度的效果要低于全局模块度但是而且对于中等或者大规模的社会网络来说局部模块度的效果可能还要好一些。

　　PageRank的Page可是认为是网页表示网页排名也可以认为是Larry Page(google 产品经理)因为他是这个算法的发明者之一还是google CEO^_^。PageRank算法计算每一个网页的PageRank值然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者上网者首先随机选择一个网页打开然后在这个网页上呆了几分钟后跳转到该网页所指向的链接这样无所事事、漫无目的地在网页上跳来跳去PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

　　互联网中的网页可以看出是一个有向图其中网页是结点如果网页A有链接到网页B则存在一条有向边A-B下面是一个简单的示例

　　上述上网者的行为是一个马尔科夫过程的实例要满足收敛性需要具备一个条件

　　互联网上的网页不满足强连通的特性因为有一些网页不指向任何网页如果按照上面的计算上网者到达这样的网页后便走投无路、四顾茫然导致前面累计得到的转移概率被清零这样下去最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉C变成了一个终止点得到下面这个图

　　另外一个问题就是陷阱问题即有些网页不存在指向其他网页的链接但存在指向自己的链接。比如下面这个图

　　上网者跑到C网页后就像跳进了陷阱陷入了漩涡再也不能从C中出来将最终导致概率分布值全部转移到C上来这使得其他网页的概率分布值为0从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵为

Tags： python 社区 

转载：感谢您对网站平台的认可，以及对我们原创作品以及文章的青睐，非常欢迎各位朋友分享到个人站长或者朋友圈，但转载请说明文章出处。