本文主要是介绍复杂网络社区结构发现算法-基于python networkx clique渗透算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
复杂网络社区结构发现算法-基于python networkx clique渗透算法
发表于2016/4/18 8:21:03 2217人阅读
分类: python 复杂网络
前言
最近因为业务数据分析的需要,看社区发现相关的东东稍多些,刚刚写过一篇基于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交互环境,测试一下
如果没有报错,就算准备好基础工作了。可以开始使用networkx这个网络分析包了。因为本文聚焦于网络中社区结构的发现,故而networkx的基础使用方法就略过了,各位看官可自行google之。
clique渗透算法简介
对于一个图G而言,如果其中有一个完全子图(任意两个节点之间均存在边),节点数是k,那么这个完全子图就可称为一个k-clique。
进而,如果两个k-clique之间存在k-1个共同的节点,那么就称这两个clique是“相邻”的。彼此相邻的这样一串clique构成最大集合,就可以称为一个社区(而且这样的社区是可以重叠的,即所谓的overlapping community,就是说有些节点可以同时属于多个社区)。下面第一组图表示两个3-clique形成了一个社区,第二组图是一个重叠社区的示意图。
-->
networkx中实现的clique渗透算法接口如下:
找社区(上代码)
以无向无权图为示例
算法输出及讨论
单机64G内存的机器上测试了几个不同规模的网络,相应的输出如下:
可见该算法在单机上适合于计算10万以下节点中小规模网络社区结构。对于大规模的社交网络,必须要用分布式集群才行啊。
转摘自:http://m.blog.csdn.net/article/details?id=51176977
这篇关于复杂网络社区结构发现算法-基于python networkx clique渗透算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!