社区发现算法 python源码,复杂网络社区结构发现算法-基于python networkx clique渗透算法...

前言

最近因为业务数据分析的需要，看社区发现相关的东东稍多些，刚刚写过一篇基于igraph C library的方法(http://km.oa.com/group/22323/articles/show/240332)，然后想用kclique衍生的clique渗透算法时发现igraph

C library 并未提供现成的api，对于懒人来说，这很不幸。既而发现networkx这个python包中是有的(且是唯一一个用于社区发现的算法)，故而折腾折腾，记录下处理过程，供同道朋友们参考吧。

准备工作

networkx安装的时候，会依赖 decorator、setuptools 这样的包，所以全部需要安装

安装好之后，进入python交互环境，测试一下

import networkx as nx

如果没有报错，就算准备好基础工作了。可以开始使用networkx这个网络分析包了。因为本文聚焦于网络中社区结构的发现，故而networkx的基础使用方法就略过了，各位看官可自行google之。

clique渗透算法简介

对于一个图G而言，如果其中有一个完全子图(任意两个节点之间均存在边)，节点数是k，那么这个完全子图就可称为一个k-clique。

进而，如果两个k-clique之间存在k-1个共同的节点，那么就称这两个clique是“相邻”的。彼此相邻的这样一串clique构成最大集合，就可以称为一个社区(而且这样的社区是可以重叠的，即所谓的overlapping community，就是说有些节点可以同时属于多个社区)。下面第一组图表示两个3-clique形成了一个社区，第二组图是一个重叠社区的示意图。

 -->  

networkx中实现的clique渗透算法接口如下：

找社区(上代码)

以无向无权图为示例

#!/usr/bin/python

#coding:utf-8

import sys

import networkx as nx

import time

def find_community(graph,k):

return list(nx.k_clique_communities(graph,k))

if __name__ == ‘__main__‘:

if len(sys.argv) < 2:

print "Usage: %s " % sys.argv[0]

sys.exit(1)

#创建一个无向、无权图

edge_list_file = sys.argv[1]

wbNetwork = nx.read_edgelist(edge_list_file,delimiter=‘\t‘)

print "图的节点数：%d" % wbNetwork.number_of_nodes()

print "图的边数：%d" % wbNetwork.number_of_edges()

#调用kclique社区算法

for k in xrange(3,6):

print "############# k值: %d ################" % k

start_time = time.clock()

rst_com = find_community(wbNetwork,k)

end_time = time.clock()

print "计算耗时(秒)：%.3f" % (end_time-start_time)

print "生成的社区数：%d" % len(rst_com)

算法输出及讨论

单机64G内存的机器上测试了几个不同规模的网络，相应的输出如下：

  

可见该算法在单机上适合于计算10万以下节点中小规模网络社区结构。对于大规模的社交网络，必须要用分布式集群才行啊。

时间： 04-17