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

前言

    最近因为业务数据分析的需要，看社区发现相关的东东稍多些，刚刚写过一篇基于igraph C library的方法（http://blog.csdn.net/a_step_further/article/details/51176973），然后想用kclique衍生的clique渗透算法时发现igraph C library 并未提供现成的api，对于懒人来说，这很不幸。既而发现networkx这个python包中是有的（且是唯一一个用于社区发现的算法），故而折腾折腾，记录下处理过程，供同道朋友们参考吧。

准备工作

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

• networkx   https://networkx.github.io
• decorator  https://pypi.python.org/pypi/decorator
• setuptools  https://pypi.python.org/pypi/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 timedef find_community(graph,k):return list(nx.k_clique_communities(graph,k))if __name__ == '__main__':if len(sys.argv) < 2:print "Usage: %s <InputEdgeListFile>" % 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 ################" % kstart_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万以下节点中小规模网络社区结构。对于大规模的社交网络，必须要用分布式集群才行啊。

转摘自：http://m.blog.csdn.net/article/details?id=51176977