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

本文主要是介绍复杂网络社区结构发现算法-基于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交互环境,测试一下

 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

这篇关于复杂网络社区结构发现算法-基于python networkx clique渗透算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/239010

相关文章

Python调用Orator ORM进行数据库操作

《Python调用OratorORM进行数据库操作》OratorORM是一个功能丰富且灵活的PythonORM库,旨在简化数据库操作,它支持多种数据库并提供了简洁且直观的API,下面我们就... 目录Orator ORM 主要特点安装使用示例总结Orator ORM 是一个功能丰富且灵活的 python O

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今,数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import

Python Jupyter Notebook导包报错问题及解决

《PythonJupyterNotebook导包报错问题及解决》在conda环境中安装包后,JupyterNotebook导入时出现ImportError,可能是由于包版本不对应或版本太高,解决方... 目录问题解决方法重新安装Jupyter NoteBook 更改Kernel总结问题在conda上安装了

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》:本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

Python安装时常见报错以及解决方案

《Python安装时常见报错以及解决方案》:本文主要介绍在安装Python、配置环境变量、使用pip以及运行Python脚本时常见的错误及其解决方案,文中介绍的非常详细,需要的朋友可以参考下... 目录一、安装 python 时常见报错及解决方案(一)安装包下载失败(二)权限不足二、配置环境变量时常见报错及