基于LFM的重叠社区发现算法python代码实现

2024-03-06 15:48

本文主要是介绍基于LFM的重叠社区发现算法python代码实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

基于LFM的重叠社区发现算法python代码实现

import random
import networkx as nx
import matplotlib.pyplot as plt
import zipfile
#import urllib.request as urllib
class Community():''' use set operation to optimize calculation '''def __init__(self,G,alpha=1.0):self._G = Gself._alpha = alphaself._nodes = set()self._k_in = 0self._k_out = 0def add_node(self,node):neighbors = set(self._G.neighbors(node))#print("添加令居节点",neighbors , self._nodes,neighbors & self._nodes)node_k_in = len(neighbors & self._nodes)#neighbor和self._nodes公有节点的数目存入node_k_in#print("node_k_in",node_k_in)node_k_out = len(neighbors) - node_k_in#print("node_k_out",node_k_out)self._nodes.add(node)self._k_in += 2*node_k_inself._k_out = self._k_out+node_k_out-node_k_indef remove_node(self,node):neighbors = set(self._G.neighbors(node))community_nodes = self._nodes#print("community_nodes",community_nodes)node_k_in = len(neighbors & community_nodes)node_k_out = len(neighbors) - node_k_inself._nodes.remove(node)self._k_in -= 2*node_k_inself._k_out = self._k_out - node_k_out+node_k_indef cal_add_fitness(self,node):#fitness适应度neighbors = set(self._G.neighbors(node))old_k_in = self._k_inold_k_out = self._k_outvertex_k_in = len(neighbors & self._nodes)#vertex顶点vertex_k_out = len(neighbors) - vertex_k_in new_k_in = old_k_in + 2*vertex_k_innew_k_out = old_k_out + vertex_k_out-vertex_k_innew_fitness = new_k_in/(new_k_in+new_k_out)**self._alpha#幂次old_fitness = old_k_in/(old_k_in+old_k_out)**self._alphareturn new_fitness-old_fitnessdef cal_remove_fitness(self,node):neighbors = set(self._G.neighbors(node))new_k_in = self._k_innew_k_out = self._k_outnode_k_in = len(neighbors & self._nodes)node_k_out = len(neighbors) - node_k_inold_k_in = new_k_in - 2*node_k_inold_k_out = new_k_out - node_k_out + node_k_inold_fitness = old_k_in/(old_k_in+old_k_out)**self._alpha new_fitness = new_k_in/(new_k_in+new_k_out)**self._alphareturn new_fitness-old_fitnessdef recalculate(self):for vid in self._nodes:fitness = self.cal_remove_fitness(vid)if fitness < 0.0:return vidreturn Nonedef get_neighbors(self):neighbors = set()for node in self._nodes:neighbors.update(set(self._G.neighbors(node)) - self._nodes)return neighborsdef get_fitness(self):return float(self._k_in)/((self._k_in+self._k_out) ** self._alpha)class LFM():def __init__(self, G, alpha):self._G = Gself._alpha = alphadef execute(self):communities = []print("嘿嘿",list(self._G.node.keys()))print("---------------------")node_not_include = list(self._G.node.keys())while(len(node_not_include) != 0):c = Community(self._G, self._alpha)#print("self._alpha",self._alpha)#0.9# randomly select a seed nodeseed = random.choice(node_not_include)c.add_node(seed)print("随机选取节点是:",seed)to_be_examined = c.get_neighbors()print("c.get_neighbors()",c.get_neighbors())while(to_be_examined):#largest fitness to be addedm = {}for node in to_be_examined:fitness = c.cal_add_fitness(node)#计算点的适应度》0加入,小于0删除m[node] = fitnessto_be_add = sorted(m.items(),key=lambda x:x[1],reverse = True)[0]#啥意思???#适应度降序排列#stop conditionif(to_be_add[1] < 0.0):breakc.add_node(to_be_add[0])to_be_remove = c.recalculate()while(to_be_remove != None):c.remove_node(to_be_remove)to_be_remove = c.recalculate()to_be_examined = c.get_neighbors()for node in c._nodes:if(node in node_not_include):node_not_include.remove(node)communities.append(c._nodes)return communitiesif(__name__ == "__main__"):#G = nx.karate_club_graph()#一个边集一个点集# G = nx.florentine_families_graph()zf = zipfile.ZipFile('football.zip')  # zipfile objecttxt = zf.read('football.txt').decode()  # read info filegml = zf.read('football.gml').decode()  # read gml data# throw away bogus first line with # from mejn filesgml = gml.split('\n')[1:]G = nx.parse_gml(gml)  # parse gml dataprint(txt)# print degree for each team - number of gamesfor n, d in G.degree():print('%s %d' % (n, d))options = {'node_color': 'red','node_size': 50,'line_color': 'grey','linewidths': 0,'width': 0.1,}nx.draw(G, **options)#networkx.draw(G, with_labels=True)plt.show()algorithm = LFM(G,0.9)communities = algorithm.execute()for c in communities:print (len(c),sorted(c))

社区网络:
初步社区网络结构图
重叠社区划分结果:
社区划分结果

这篇关于基于LFM的重叠社区发现算法python代码实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python FastMCP构建MCP服务端与客户端的详细步骤

《PythonFastMCP构建MCP服务端与客户端的详细步骤》MCP(Multi-ClientProtocol)是一种用于构建可扩展服务的通信协议框架,本文将使用FastMCP搭建一个支持St... 目录简介环境准备服务端实现(server.py)客户端实现(client.py)运行效果扩展方向常见问题结

IDEA如何实现远程断点调试jar包

《IDEA如何实现远程断点调试jar包》:本文主要介绍IDEA如何实现远程断点调试jar包的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录问题步骤总结问题以jar包的形式运行Spring Boot项目时报错,但是在IDEA开发环境javascript下编译

详解如何使用Python构建从数据到文档的自动化工作流

《详解如何使用Python构建从数据到文档的自动化工作流》这篇文章将通过真实工作场景拆解,为大家展示如何用Python构建自动化工作流,让工具代替人力完成这些数字苦力活,感兴趣的小伙伴可以跟随小编一起... 目录一、Excel处理:从数据搬运工到智能分析师二、PDF处理:文档工厂的智能生产线三、邮件自动化:

深入解析 Java Future 类及代码示例

《深入解析JavaFuture类及代码示例》JavaFuture是java.util.concurrent包中用于表示异步计算结果的核心接口,下面给大家介绍JavaFuture类及实例代码,感兴... 目录一、Future 类概述二、核心工作机制代码示例执行流程2. 状态机模型3. 核心方法解析行为总结:三

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷

Python数据分析与可视化的全面指南(从数据清洗到图表呈现)

《Python数据分析与可视化的全面指南(从数据清洗到图表呈现)》Python是数据分析与可视化领域中最受欢迎的编程语言之一,凭借其丰富的库和工具,Python能够帮助我们快速处理、分析数据并生成高质... 目录一、数据采集与初步探索二、数据清洗的七种武器1. 缺失值处理策略2. 异常值检测与修正3. 数据

Python中bisect_left 函数实现高效插入与有序列表管理

《Python中bisect_left函数实现高效插入与有序列表管理》Python的bisect_left函数通过二分查找高效定位有序列表插入位置,与bisect_right的区别在于处理重复元素时... 目录一、bisect_left 基本介绍1.1 函数定义1.2 核心功能二、bisect_left 与

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建:像搭积木一样组合控件二、菜单系统:给应用装上“控制中枢”三、事件驱动:让界面“活”