复杂网络社区结构发现算法-基于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的pip在命令行无法使用问题的解决方法

《Python的pip在命令行无法使用问题的解决方法》PIP是通用的Python包管理工具,提供了对Python包的查找、下载、安装、卸载、更新等功能,安装诸如Pygame、Pymysql等Pyt... 目录前言一. pip是什么?二. 为什么无法使用?1. 当我们在命令行输入指令并回车时,一般主要是出现以

Python解决雅努斯问题实例方案详解

《Python解决雅努斯问题实例方案详解》:本文主要介绍Python解决雅努斯问题实例方案,雅努斯问题是指AI生成的3D对象在不同视角下出现不一致性的问题,即从不同角度看物体时,物体的形状会出现不... 目录一、雅努斯简介二、雅努斯问题三、示例代码四、解决方案五、完整解决方案一、雅努斯简介雅努斯(Janu

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

使用Python和SQLAlchemy实现高效的邮件发送系统

《使用Python和SQLAlchemy实现高效的邮件发送系统》在现代Web应用中,邮件通知是不可或缺的功能之一,无论是订单确认、文件处理结果通知,还是系统告警,邮件都是最常用的通信方式之一,本文将详... 目录引言1. 需求分析2. 数据库设计2.1 User 表(存储用户信息)2.2 CustomerO

使用Python实现实时金价监控并自动提醒功能

《使用Python实现实时金价监控并自动提醒功能》在日常投资中,很多朋友喜欢在一些平台买点黄金,低买高卖赚点小差价,但黄金价格实时波动频繁,总是盯着手机太累了,于是我用Python写了一个实时金价监控... 目录工具能干啥?手把手教你用1、先装好这些"食材"2、代码实现讲解1. 用户输入参数2. 设置无头浏

一文教你如何解决Python开发总是import出错的问题

《一文教你如何解决Python开发总是import出错的问题》经常朋友碰到Python开发的过程中import包报错的问题,所以本文将和大家介绍一下可编辑安装(EditableInstall)模式,可... 目录摘要1. 可编辑安装(Editable Install)模式到底在解决什么问题?2. 原理3.

Python+wxPython构建图像编辑器

《Python+wxPython构建图像编辑器》图像编辑应用是学习GUI编程和图像处理的绝佳项目,本教程中,我们将使用wxPython,一个跨平台的PythonGUI工具包,构建一个简单的... 目录引言环境设置创建主窗口加载和显示图像实现绘制工具矩形绘制箭头绘制文字绘制临时绘制处理缩放和旋转缩放旋转保存编

Python 异步编程 asyncio简介及基本用法

《Python异步编程asyncio简介及基本用法》asyncio是Python的一个库,用于编写并发代码,使用协程、任务和Futures来处理I/O密集型和高延迟操作,本文给大家介绍Python... 目录1、asyncio是什么IO密集型任务特征2、怎么用1、基本用法2、关键字 async1、async

Python实现剪贴板历史管理器

《Python实现剪贴板历史管理器》在日常工作和编程中,剪贴板是我们使用最频繁的功能之一,本文将介绍如何使用Python和PyQt5开发一个功能强大的剪贴板历史管理器,感兴趣的可以了解下... 目录一、概述:为什么需要剪贴板历史管理二、功能特性全解析2.1 核心功能2.2 增强功能三、效果展示3.1 主界面

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ